题意

给一个字符串\(s\)，和\(n\)个子串\(t[i]\)，两个人博弈，每次取出一个串\(t[i]\)，在后面加入一个字符，保证新字符串仍然是\(s\)的子串，无法操作的人输。

分析

n个子串，类比于n堆石子，如果把子串\(t[i]\)在后面加若干字符能生成的子串看出一个状态，用一个数表示，那每次状态的变化，就类比于对一堆石子取走若干个，无法操作，就类比于没有石子可以取。
多堆取石子游戏的做法就是把每堆石子的SG值(sg(x)=x)异或起来，不为零就先手赢，否则后手赢。
所以可以将题目转化为求每个子串\(t[i]\)对应状态的SG值。
然后就是后缀自动机的套路，每个子串就可以对应SAM上的一个节点，所以可以直接dfs记忆化搜索SG值。

代码

#include <bits/stdc++.h>

using namespace std;

const int N=1e5+50;

char s[N];

int n;

struct SAM{

    int nex[N*2][26],fa[N*2],len[N*2],num[N*2];

    int cnt,lst;

    int sg[N*2];

    int newnode(int l,int s){

        for(int i=0;i<26;i++){

            nex[cnt][i]=0;

        }

        len[cnt]=l;

        num[cnt]=s;

        return cnt++;

    }

    void init(){

        cnt=0;

        lst=newnode(0,0);

        fa[lst]=-1;

        memset(sg,-1,sizeof(sg));

    }

    void add(int c){

        c-='a';

        int p=lst;

        int cur=newnode(len[p]+1,1);

        while(p!=-1 && !nex[p][c]){

            nex[p][c]=cur;

            p=fa[p];

        }

        if(p==-1){

            fa[cur]=0;

        }else{

            int q=nex[p][c];

            if(len[q]==len[p]+1){

                fa[cur]=q;

            }else{

                int cl=newnode(len[p]+1,0);

                fa[cl]=fa[q];

                memcpy(nex[cl],nex[q],sizeof(nex[cl]));

                while(p!=-1 && nex[p][c]==q){

                    nex[p][c]=cl;

                    p=fa[p];

                }

                fa[q]=fa[cur]=cl;

            }

        }

        lst=cur;

    }

    int w[N*2],tp[N*2];

    void dfs(int u){

        int vis[30]={0};

        if(sg[u]!=-1){

            return;

        }

        for(int i=0;i<26;i++){

            int v=nex[u][i];

            if(v){

                dfs(v);

                vis[sg[v]]=1;

            }

        }

        for(int i=0;i<26;i++){

            if(!vis[i]){

                sg[u]=i;

                break;

            }

        }

    }

    void sfd(int l){

        for(int i=0;i<=l;i++){

            w[i]=0;

        }

        for(int i=1;i<=cnt;i++){

            w[len[i]]++;

        }

        for(int i=2;i<=l;i++){

            w[i]+=w[i-1];

        }

        for(int i=cnt-1;i>=1;i--){

            tp[w[len[i]]--]=i;

        }

        sg[lst]=0;

        int vis[30]={0};

        for(int i=cnt-1;i>=0;i--){

            int u=tp[i];

            memset(vis,0,sizeof(vis));

            for(int j=0;j<26;j++){

                int v=nex[u][j];

                if(v){

                    vis[sg[v]]=1;

                }

            }

            for(int j=0;j<26;j++){

                if(!vis[j]){

                    sg[u]=j;

                    break;

                }

            }

        }

    }

    int solve(char *s){

        int rt=0;

        int l=strlen(s);

        for(int j=0;j<l;j++){

            rt=nex[rt][s[j]-'a'];

        }

        return sg[rt];

    }

}ac;

int main(){

    // freopen("in.txt","r",stdin);

    while(~scanf("%s",s)){

        ac.init();

        int len=strlen(s);

        for(int i=0;i<len;i++){

            ac.add(s[i]);

        }

        //dfs或者拓扑排序求sg函数

        // ac.dfs(0);

        ac.sfd(len);

        scanf("%d",&n);

        int ans=0;

        for(int i=1;i<=n;i++){

            scanf("%s",s);

            ans^=ac.solve(s);

        }

        if(ans){

            printf("Alice\n");

        }else{

            printf("Bob\n");

        }

    }

    return 0;

}

巴特西

是男人就过八题A_A String Game题解

题意

分析

代码

最新文章

热门文章