【问题描述】
hy 抄题解又被老师抓住了，现在老师把他叫到了办公室。 老师要 hy 和他 玩一个游戏。如果 hy 输了，老师就要把他开除信息组； 游戏分为 k 轮。在游戏开始之前，老师会将 n 个由英文字母组成的字符串放 入箱子。
每局开始，字符串为空串，然后两人轮流在末尾追加字符，保证新的字 符串为箱子中某字符串的前缀，直到有一个人不能操作，不能操作的那个人就输 掉当前的一轮。新一轮由上一句输的人先手。最后一局赢的人获胜。
假定老师和 hy 都能采取最优的策略，且老师为了彰显自己的大度让 hy 先手， 求 hy 能否获胜。
【输入格式】 输入包括多组数据，输入以文字流结尾（EOF）为结束。 每组数据的第一行包含两个整数 n, k，分别表示放入箱子字符串的数量和游 戏的轮数。 接下来 n 行，每行一个字符串表示由英文字母组成的句子。
【输出格式】 每组数据第一行，输出 hy 是否能赢，若能赢输出”HY wins!“，否则输出” Teacher wins!”。
【样例输入 1】 2 3
a b
3 1
a b c
【样例输出 1】 HY wins!
HY wins!
【样例输入 2】 1 2
ab
【样例输出 2】 Teacher wins!
全国信息学奥林匹克联赛（NOIP2017）模拟赛 提高组
【评测用例规模与约定】 对于 40%的评测用例，1≤n≤10，1≤k≤10 4； 对于 100%的评测用例，1≤n≤10 5，1≤k≤10 9，保证所有字符串总长度不超过 10 5， 数据组数不超过 10
题解：
博弈论+递推+字典树
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int num,ch[][],n,k;
bool f[][],p,p2;
char s[];
void build()
{int len,x,i;
len=strlen(s);
x=;
for (i=;i<len;i++)
if (ch[x][s[i]-'a']==)
{
num++;
ch[x][s[i]-'a']=num;
x=num;
}
else x=ch[x][s[i]-'a'];
}
bool dfs(int x,bool y,bool z)
{int i,k1=,k2=;
for (i=;i<;i++)
if (ch[x][i])
{
if (x)
dfs(ch[x][i],!y,z);
else dfs(ch[x][i],y,z);
}
for (i=;i<;i++)
if (ch[x][i])
{
if (x==)
{
if (f[ch[x][i]][y])
k1++;
else k2++;
}
if (x!=)
{
if (f[ch[x][i]][!y])
k1++;
else k2++;
}
}
if (x==&&y==&&k1!=)
{
if (k2==) p=;
else p=;
}
if (x==&&y==)
{
if (k1!=) return ;
else return ;
}
if (x==&&y==)
{
if (k2!=) return ;
else return ;
}
if (k1==&&k2==)
{
if (y==) p=;
f[x][y]=y;
return y;
}
if (y==&&k2!=)
{
f[x][y]=;
return ;
}
if (y==&&k1==)
{
f[x][y]=;
return ;
}
if (y==&&k2==)
{
f[x][y]=;
return ;
}
if (y==&&k1!=)
{
if (k2!=) p=;
f[x][y]=;
return ;
}
}
int main()
{int i,j;
bool b1,b2;
freopen("amerce.in","r",stdin);
freopen("amerce.out","w",stdout);
while (cin>>n>>k)
{
memset(ch,,sizeof(ch));
num=;
memset(f,,sizeof(f));
p=;
for (i=;i<=n;i++)
{
scanf("%s",s);
build();
}
b1=dfs(,,);//先手
b2=dfs(,,);//后手
//cout<<b1<<' '<<b2<<endl;
if (b1&&b2) printf("HY wins!\n");
if (b1&&!b2)
{
if (k%==)
{
if (p==)
printf("Teacher wins!\n");
else printf("HY wins!\n");
}
if (k%==) printf("HY wins!\n");
}
if (!b1&&b2)
{
printf("Teacher wins!\n");
}
if (!b1&&!b2) printf("Teacher wins!\n");
}
}