计蒜客 A String Game

题目传送门

这道题是那场比赛里唯一一道比较容易的题目,也是我唯一那道AC的题……

由于要在si后加字母,而且要保持si为t的子串,这很明显要用到SAM。任何这题就变成了在一张DAG中的某些点上有若干棋子,每次操作要把其中一个棋子沿着DAG的边移动一格,不能操作者负。这就是一个非常裸的博弈论问题了,求出DAG上每个点的SG函数,然后对每个棋子所在的点的SG函数求异或和,如果结果为0则Bob获胜,否则Alice获胜。

code

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdlib>
using namespace std;
int n,len,last,cnt,maxlen[2000005],minlen[2000005],slink[2000005],trans[200005][26],vis[200005],sg[200005];
long long ans;
char s[1000005];
int extand(int u,char ch){
    int c=ch-'a',z=++cnt,v=u;
    maxlen[z]=maxlen[u]+1;
    while(v&&!trans[v][c]){
        trans[v][c]=z;
        v=slink[v];
    }
    if(!v){
        slink[z]=1;
        minlen[z]=1;
        return z;
    }
    int x=trans[v][c];
    if(maxlen[v]+1==maxlen[x]){
        slink[z]=x;
        minlen[z]=maxlen[slink[z]]+1;
        return z;
    }
    int y=++cnt;
    for(int i=0;i<26;i++)
        trans[y][i]=trans[x][i];
    maxlen[y]=maxlen[v]+1;
    slink[y]=slink[x];
    minlen[y]=maxlen[slink[y]]+1;
    slink[x]=y;
    minlen[x]=maxlen[slink[x]]+1;
    slink[z]=y;
    minlen[z]=maxlen[slink[z]]+1;
    int w=v;
    while(w&&trans[w][c]==x){
        trans[w][c]=y;
        w=slink[w]; 
    }
    return z;
}
void dfs(int u){
    bool flag[27];
    memset(flag,0,sizeof(flag));
    for(int i=0;i<26;i++)
        if(trans[u][i]) {
            int v=trans[u][i];
            if(!vis[v]){
                vis[u]=true;
                dfs(v);
            }
            flag[sg[v]]=true;
        }
    for(int i=0;i<=26;i++)
        if(!flag[i]){
            sg[u]=i;
            break;
        }
}
int main(){
    while(scanf("%s",s)!=EOF){
        last=cnt=1;
        scanf("%d",&n);
        len=strlen(s);
        memset(sg,0,sizeof(sg));
        memset(trans,0,sizeof(trans));
        memset(slink,0,sizeof(slink)); 
        memset(vis,0,sizeof(vis));
        for(int i=0;i<len;i++)
            last=extand(last,s[i]);
        dfs(1);
        int ans=0;
        while(n--){
            scanf("%s",s);
            int x=1;
            len=strlen(s);
            for(int i=0;i<len;i++)
                x=trans[x][s[i]-'a'];
            ans^=sg[x];
        }
        if(ans)
            puts("Alice");
        else
            puts("Bob");
    }
    return 0;
}

还没有评论,快来抢沙发!

发表评论