给出一个串t和n个t的子串 s[1..n] s [ 1.. n ] 。两个人轮流操作，每次可以选择一个串 s[i] s [ i ] ，然后在 s[i] s [ i ] 的最后添上一个字符串，满足得到的新串仍然是t的子串。不能操作者输，问先手必胜还是后手必胜。 t≤105,∑|s[i]|≤3∗107 t ≤ 10 5 , ∑ | s [ i ] | ≤ 3 ∗ 107
省选前复一波模版…… sam+sg裸题。 code：
#include<cstdio> #include<cstdlib> #include<iostream> #include<cstring> struct SAM{ int a[26],max,par; }sam[200010];int tot=1,root,tail,sg[200010]; int check[20][200010],tim=0; void addsam(int c,int len) { int p=tail,np=++tot; sam[np].max=len; for(;p&&!sam[p].a[c];p=sam[p].par) sam[p].a[c]=np; tail=np; if(!p) sam[np].par=root; else { int q=sam[p].a[c]; if(sam[q].max==sam[p].max+1) sam[np].par=q; else { int nq=++tot;sam[nq]=sam[q]; sam[nq].max=sam[p].max+1; sam[q].par=sam[np].par=nq; for(;p&&sam[p].a[c]==q;p=sam[p].par) sam[p].a[c]=nq; } } } char s[100010]; void solve(int x) { if(sg[x]!=-1) return; int tmp=++tim; for(int i=0;i<26;i++) if(sam[x].a[i]) solve(sam[x].a[i]),check[sg[sam[x].a[i]]][x]=tmp; for(int i=0;i<=27;i++) if(check[i][x]!=tmp) {sg[x]=i;break;} } int main() { while(scanf("%s",s+1)!=EOF) { int len=strlen(s+1); for(int i=1;i<=tot;i++) for(int j=0;j<26;j++) sam[i].a[j]=0; tot=root=tail=1; for(int i=1;i<=len;i++) addsam(s[i]-'a',i); for(int i=1;i<=tot;i++) sg[i]=-1; solve(root); int n;scanf("%d",&n); int ans=0; while(n--) { scanf("%s",s+1); len=strlen(s+1);int x=root; for(int i=1;i<=len;i++) x=sam[x].a[s[i]-'a']; ans^=sg[x]; } if(ans) puts("Alice"); else puts("Bob"); } }