【2010集训队出题】单词争霸

by AmanoKumiko

Description

农夫约翰(Farmer John)的奶牛们平时喜好一起学习英文单词。奶牛Bessie是其中最聪明的牛，她发明了一个游戏，叫做《单词争霸》。　　

这个游戏是由两个人来玩，两人轮流进行。轮到每个人时，他要说出一个正确的单词（即字典中的单词），要求这个单词在之前没有被他或他的对手说过，并且这个单词不是之前他或他的对手说过的某个单词的前缀。如果轮到一个人，他无法说出这样的单词，那么他被判败。　　

显然，拥有词汇量较多的奶牛玩起这个游戏来更有优势，因为他有更多的单词可以说。这样，奶牛们天天玩这个游戏，他们的词汇量越来越大…… 　　

直到有一天，Bessie发现他们已经把世界上所有的英文单词学会了，因此她再也无法依赖自己较大的词汇量取胜了。她是记忆单词的天才，但并不是游戏好手，所以她来请教聪明的你。　　

她告诉你，这个世界上一共有N个英文单词，每个单词的长度不超过maxLen。她将这些单词按字典序排列，并输入。她想知道如果她是先手，那么她是否能取得胜利。　　

你需要做的是，判断在给定字典的情况下，先手是否有必胜策略。如果没有，那么告诉Bessie:“Can’t win at all!!”，否则，你需要确定先手在第一回合可以说出哪些单词，为了让Bessie多一些思考的乐趣，你决定不把这些单词一一列举。你把这些单词按某个排列连接起来，组成一个大的字符串，当然，不同的排列可能得到不同的串，你要告诉Bessie那个字典序最先的串，记作answerString。　　

为了使输出更加美观，如果那个串的长度大于50,你要分行输出，除了最后一行以外，其他行每行50个字符，最后一行不多于50个字符。

Input

输入的第一行包含两个整数,N和maxLen,用一个空格隔开。　　

接下来的N行，每行为一个长度不大于maxLen的字符串。

Output

按题目描述中的要求输出：　　

可能为一行,“Can’t win at all!!”(不包含引号) 　　或者多行，除了最后一行之外每行50个字符，最后一行不超过50个字符，将所有行的字符连接起来是answerString。

Sample Input

5 9
ac
car
care
careful
carefully

Sample Output

careful

Data Constraint

输入数据中的所有单词均由小写字母构成。

输入数据保证所有单词按字典序排列。

输入数据保证所有单词互不相同。

100%的数据中N≤100000,maxLen≤100。

Solution

考虑直接上\(SG\)函数

选择一个字符串，相当于删除这个串和其所有前缀

那么我们找出每个串的父亲，即它最长的前缀串，然后建出一棵树

对于每个节点，求出其所有后继状态的\(SG\)值，然后，枚举值求出\(mex\)

设\(f_{i,j}\)表示节点\(i\)的后继状态中，是否存在\(SG\)值为\(j\)

那么可以用儿子的状态求出父亲的

令\(all=\bigoplus_{v∈son(u)} SG(v)\)

第一种情况：选择串\(u\)，那么\(SG\)为\(all\)

第二种情况：选择儿子，那么\(SG\)为\(k\bigoplus all\bigoplus SG(u)\)，当且仅当\(f_{u,v}=1\)

这时，瓶颈就在于枚举\(k\)

我们考虑重新计算复杂度

引理：一个点的\(SG\)值一定不大于以它为根的子树大小

证明：可以归纳证明

那么复杂度为\(\sum size_i=\sum deep_i\le Maxlen·N\)

最后遍历一遍求出答案即可

Code

#include
using namespace std;
#define F(i,a,b) for(int i=a;i<=b;i++)
#define Fd(i,a,b) for(int i=a;i>=b;i--)
#define N 100010
#define M 110

char s[N][M],fuck[N*M];
vectorson[N],f[N];
int n,m,st[N],top,fa[N],lcs[N],l[N],SG[N],size[N],SA,ans[N],sum[N],tot;

void dfs(int x){
	size[x]=1;
	for(auto y:son[x])dfs(y),size[x]+=size[y],sum[x]^=SG[y];
	F(i,0,size[x])f[x].push_back(0);
	if(size[x]==1){
		f[x][0]=SG[x]=1;
		return;
	}
	f[x][sum[x]]=1;
	for(auto y:son[x]){
		F(i,0,size[y])if(f[y][i])f[x][sum[x]^SG[y]^i]=1;
	}
	F(i,0,size[x])if(!f[x][i]){SG[x]=i;break;}
}

void calc(int x,int rt,int fs){
	if((SA^rt^fs^sum[x])==0)ans[++ans[0]]=x;
	for(auto y:son[x])calc(y,rt,fs^sum[x]^SG[y]);
}

int main(){
	scanf("%d%d",&n,&m);
	F(i,1,n){
		scanf("%s",s[i]+1);
		l[i]=strlen(s[i]+1);
		F(j,1,min(l[i-1],l[i])){
			if(s[i][j]==s[i-1][j])lcs[i]++;
			else break;
		}
		int p=i-1;
		while(l[p]>lcs[i])p=fa[p];
		fa[i]=p;
		son[p].push_back(i);
	}
	F(i,1,n)if(!fa[i])dfs(i),SA^=SG[i];
	if(SA==0){
		printf("Can't win at all!!");
		return 0;
	}
	F(i,1,n)if(!fa[i])calc(i,SG[i],0);
	sort(ans+1,ans+ans[0]+1);
	F(i,1,ans[0]) F(j,1,l[ans[i]])fuck[++tot]=s[ans[i]][j];
	F(i,1,tot){
		printf("%c",fuck[i]);
		if(!(i%50))printf("\n");
	}
	return 0;
}

题解博弈论 NOI

【2010集训队出题】单词争霸