一、题目
两个人玩博弈游戏，要求说出字符串在给定字典中，并且满足前三位是上一个字符串的后三位。一个字符串可以被重复说出，不能说出字符串者输，问第一个人先说出第 (i) 个字符串是结果是先手必胜(/)平局(/)先手必败。
(nleq 2 imes 10^5,3leq |s_i|leq 8)，字符串区分大小写。
二、解法
我以为把给定字符串当点，但是这样边数爆炸。其实是建 (52^3) 个点，每个字符串当成边，从前三位连向后三位，那么问题就变成了在一个图上走，不能走的人输。
这是经典问题，可以建出原图的反图，然后跑拓扑排序，此时入度为 (0) 的点肯定是终状态，这相当于一个从终状态考虑到起始状态的过程，我们先把所有点的状态定成平局，如果一个点的后继状态有必败，这个点必胜。如果一个点的边全部访问完还不确定的话，这个点必败。
三、总结
又是思维定式！一定要思考图论中边和点的关系，弄清楚什么是边？什么是点？
如果有平局，并且可以访问到先前状态的博弈论，可以考虑用拓扑排序解决。
#include <cstdio>
#include <vector>
#include <cstring>
#include <queue>
using namespace std;
const int M = 300005;
int read()
{
int x=0,f=1;char c;
while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x*f;
}
int n,l,ans[M],cnt[M];char s[100];vector<int> g[M];
struct node
{
int x,y;
}a[M];
int get(char x)
{
if('A'<=x && x<='Z') return x-'A';
return x-'a'+26;
}
int hs(char x,char y,char z)
{
return 52*52*get(x)+52*get(y)+get(z);
}
signed main()
{
n=read();
for(int i=1;i<=n;i++)
{
scanf("%s",s),l=strlen(s);
a[i]=node{hs(s[0],s[1],s[2]),
hs(s[l-3],s[l-2],s[l-1])};
cnt[a[i].x]++;
g[a[i].y].push_back(a[i].x);
}
queue<int> q;
memset(ans,-1,sizeof ans);
for(int i=0;i<M;i++)
if(!cnt[i])
ans[i]=0,q.push(i);
while(!q.empty())
{
int u=q.front();q.pop();
for(int i=0;i<g[u].size();i++)
{
int v=g[u][i];
if(ans[v]==-1)
{
cnt[v]--;
if(ans[u]==0)
ans[v]=1,q.push(v);
else if(cnt[v]==0)
ans[v]=0,q.push(v);
}
}
}
for(int i=1;i<=n;i++)
{
if(ans[a[i].y]==-1) puts("Draw");
if(ans[a[i].y]==0) puts("Takahashi");
if(ans[a[i].y]==1) puts("Aoki");
}
}