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;
}