【题目】

【题意】给定目标串S和n个子串Ti，Alice和Bob轮流选择一个子串操作，必须且只能在子串末尾添加一个字符使得新串也是S的子串，不能操作即输，求胜利者。|S|<=10^5,n<=100。多组数据，保证Σ|S|<=3*10^7。

【算法】后缀自动机+博弈论SG函数

【题解】对S建SAM，每次子串操作相当于沿SAM的实边走，所以可以对SAM进行DAG上的sg函数计算，最后多个子串的sg值的异或和就是答案，非0先手必胜。

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #define ll long long#define lowbit(x) x&-xusing namespace std;int read(){ char c;int s=0,t=1; while(!isdigit(c=getchar()))if(c=='-')t=-1; do{s=s*10+c-'0';}while(isdigit(c=getchar())); return s*t;}int min(int a,int b){ return a
               
                0?x:-x;}//int MO(int x){return x>=MOD?x-MOD:x;}//void insert(int u,int v){tot++;e[tot].v=v;e[tot].from=first[u];first[u]=tot;}/*------------------------------------------------------------*/const int inf=0x3f3f3f3f,maxn=100010;int n,last,root,size,sg[maxn*2];struct st{ int len,fa,t[30];}t[maxn*2];void insert(int c){ int np=++size; for(int i=0;i<26;i++)t[np].t[i]=0; t[np].len=t[last].len+1; int x=last; while(x&&!t[x].t[c])t[x].t[c]=np,x=t[x].fa; last=np; if(!x)t[np].fa=root;else{ int y=t[x].t[c]; if(t[y].len==t[x].len+1)t[np].fa=y;else{ int nq=++size; t[nq]=t[y]; t[nq].len=t[x].len+1; t[nq].fa=t[y].fa;t[y].fa=t[np].fa=nq; while(x&&t[x].t[c]==y)t[x].t[c]=nq,x=t[x].fa; } }}void dfs(int x){ bool vis[28];// if(~sg[x])return; memset(vis,0,sizeof(vis)); for(int c=0;c<26;c++)if(t[x].t[c]){ dfs(t[x].t[c]); vis[sg[t[x].t[c]]]=1; } for(int i=0;i<=26;i++)if(!vis[i]){sg[x]=i;break;}}char s[maxn];int main(){ while(~scanf("%s",s)){ int m=strlen(s); last=size=root=1; for(int c=0;c<26;c++)t[1].t[c]=0; for(int i=0;i
               
              
             
            
           
          
         
        
       
      

 

这破题说明我是八分之一男人，哈哈哈嗝。

。。。