NOIP提高组模拟赛2

A. 匹配

kmp板子,用A的前缀匹配B的后缀,就是用AB求next数组,答案就是\(next[min(la,lb+1)]\)

注意坑点,kmp匹配是除了本身以外的最大前缀和后缀,需要特判B恰好是A前缀的情况,本题数据诡异,特判有90pts

#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=1000005;
char a[maxn],b[maxn];
int net[maxn];
void kmp(int la,int lb){
    memset(net,0,sizeof(net));
    int j=0;
    for(int i=2;i<=lb;++i){
        while(j&&b[j+1]!=b[i])j=net[j];
        if(b[j+1]==b[i])j++;
        net[i]=j;
    }
    printf("%d\n",net[lb]);
}
int main(){
    int T;scanf("%d",&T);
    for(int ask=1;ask<=T;++ask){
        int la,lb;scanf("%d%d",&la,&lb);
        scanf("%s",a+1);
        for(int i=1;i<=lb;++i)b[i]=a[i];
        ++lb;scanf("%c",&b[lb]);
        while(b[lb]<'a'||b[lb]>'z')scanf("%c",&b[lb]);
        if(lb<=la&&b[lb]==a[lb])printf("%d\n",lb);
        else kmp(la,lb);
    }
    return 0;
}

B. 回家

算法一: DFS记录路径 每次删去一个路径上的点,再DFS看是否能到n 得分30pts(考试时候想特判树的情况结果判错了,可恶)

优化:不用每次删去点,dfs寻找路径,如果有一条从i-j(i,j为1-n路径上的点)非1-n路径的路径,那么i-j之间的点就不是必须经过的点,考场上想到了,但是时间(码力)不够,题解说有80-100pts

正解:
考试时候也想到了,但是由于蒟蒻tarjan没学完(没学)无奈打爆力。。

可以想到1-n必须经过的点必定是图的一个割点,但割点并不一定是路径上的点

tarjan割点时记录一下是否在路径上即可,即该点的子树内是否有n

:这个故事告诉我们,不要留坑

代码

留坑

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int read(){
    char c;int x=0;
    c=getchar();
    while(c<'0'||c>'9')c=getchar();
    while(c>='0'&&c<='9'){x*=10;x+=c-'0';c=getchar();}
    return x;
}
const int maxn=200005;
int n,m;
struct edge{
    int to,net;
}e[maxn<<2|1];
int head[maxn],tot;
void add(int u,int v){
    e[++tot].net=head[u];
    head[u]=tot;
    e[tot].to=v;
}
int low[maxn],dfn[maxn],tim;
bool flag[maxn];
bool vis[maxn];
bool lv[maxn];
bool tarjan(int x,int fx){
    dfn[x]=low[x]=++tim;lv[x]=1;
    for(int i=head[x];i;i=e[i].net){
        int v=e[i].to;if(v==fx)continue;
        if(!dfn[v]){
            vis[x]|=tarjan(v,x);
            low[x]=min(low[x],low[v]);
            if(low[v]>=dfn[x]&&vis[v])flag[x]=1;
        }
        else if(lv[v])low[x]=min(low[x],dfn[v]);
    }
    lv[x]=0;
    if(x==n||vis[x])return vis[x]=1;
    return 0;
}

int main(){
///  freopen("home.in","r",stdin);
//    freopen("home.out","w",stdout);
    int T;T=read();
    for(int ask=1;ask<=T;++ask){
        n=read();m=read();
        memset(head,0,sizeof(head));
        memset(vis,0,sizeof(vis));
        memset(flag,0,sizeof(flag));
        memset(dfn,0,sizeof(dfn));
        memset(low,0,sizeof(low));
        tim=0,tot=0;
        for(int i=1;i<=m;++i){
            int u,v;u=read();v=read();
            add(u,v);add(v,u);
        }
        tarjan(1,0);
        int cnt=0;
        for(int i=2;i<n;++i)if(vis[i]&&flag[i])cnt++;
        printf("%d\n",cnt);
        for(int i=2;i<n;++i)if(vis[i]&&flag[i])printf("%d ",i);
        printf("\n");
    }
    return 0;
}

C. 寿司

题面成功将我误导,以为是考数据结构(还是因为菜),甚至想打线段树(只会这个

显然是个DP,环形DP,可以想到至少有一盘寿司不用动,否则相当于把环转了一下没有意义。可以断环成链。

考虑R或B其一即可,在环上连续等价于在链的两端或中间,两边比较好考虑。

容易发现一定是靠左的向左边走,靠右的一定向右走,中间一定有一个分界点p,p左边的向左,p右边的向右,而区间右移,即相当于环上顺时针(也可能是逆时针)转了一下,p也一定同方向移动或者不动,就是说p有单调性,这样一来直接\(O(n)\)扫一遍就行了

具体一点

预处理出从i跳到左和右的步数l[i],r[i],即到左或右有几个与i颜色不同的寿司个数,枚举区间时l[i]减去左界l[],r[i]减去右界r[],就是i向两端走的步数

移动区间,考虑将左边的R还是B移到了右边,对向左走和向右走的有什么影响,在移动p时记录一下几个向左走的几个向右走的

思路比较清晰,代码实现还是很有细节的(还是我太菜),容易算出负数

还有记得开longlong

#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=2000005;
long long min(long long x,long long y){return x<y?x:y;}
char c[maxn];
long long l[maxn],r[maxn];
int main(){
   int T;scanf("%d",&T);
   for(int ask=1;ask<=T;++ask){
       memset(l,0,sizeof(l));memset(r,0,sizeof(r));
       scanf("%s",c+1);int s=strlen(c+1),p;
       for(int i=1;i<=s;++i)c[i+s]=c[i];
       p=0;for(int i=1;i<=s<<1;++i){if(c[i]=='B')++p;l[i]=p;} 
       p=0;for(int i=s<<1;i>=1;--i){if(c[i]=='B')++p;r[i]=p;}
       p=0;long long ans=1e18,sum=0,ls=0,rs=0;
       for(int i=1;i<=s;++i)if(c[i]=='R'){sum+=r[i]-r[s+1];rs++;}
       for(int i=1;i<=s;++i){
           while(p+1<=i+s-1){
               if(c[p+1]=='B'){
                   p++;
               }else{
                   if(l[p+1]-l[i-1]<r[p+1]-r[i+s]){
                       p++;ls++;rs--;
                       sum=sum-r[p]+r[i+s]+l[p]-l[i-1];
                   }else break;
               }
           }         ans=min(ans,sum);
           if(c[i]=='B')sum=sum-ls+rs;
           else {--ls;++rs;}
       }
       printf("%lld\n",ans);
   }
   return 0;
}
上一篇:NOIP 2002普及组 选数


下一篇:2021-10-30