Atcoder Beginner Contest 209 E Shiritori
题目链接:https://atcoder.jp/contests/abc209/tasks/abc209_e
? 很容易想到这是一幅图。我们将每个单词的前三个字母向后三个字母连一条边。然后就构成了一幅有向的图。对于这幅图来说，如果一个人走到了一个没有出度的点，那么他就赢了，因为另一个人不能再说出任何一个单词（走到另外一个点）。我们用一个 \(dp\) 数组表示从这个点开始游戏的输赢情况，0 表示平局，1 表示 Takahashi 赢，2 表示 Aoki 赢。那么显然，所有出度为 0 的点的 \(dp\) 值都为1。
? 现在我们考虑 \(dp\) 数组的转移。如果一个点所有能走到的点当中，有一个点的 \(dp\) 值为 1。那么这个点的 \(dp\) 值肯定为 2。因为 Aoki 只要往这个点上走，那么他就赢了。如果这个点能到达的所有点的 \(dp\) 值为 2，那么这个点的 \(dp\) 值才能为 1。如果一个点不符合上述的两种情况，那么它的 \(dp\) 值就是 0 了，因为能更新状态为 1,2，的只有上述两种情况，然后这个点一定是 0,1,2 中的一个，只有可能是 0了。
? 然后我们反向连边，将所有入度为 0 的点的 \(dp\) 值设置为 1。然后跑一趟拓扑排序就好了。当然，这里的拓扑排序要魔改一下，如果一个点的 \(dp\) 值被确定为 1 或 2 了，可以立马扔进队列中，因为根据我们上面的转移，它不可能再被更改了。这样操作可以让拓扑排序渗透到一些环中。对于一些环来说，环的某一部分是可以被更新到的，一部分又是无法被更新到的，而可以被更新到的点中它们被更新的状态是不同的，简而言之，一个环中所有点的 \(dp\) 值是不同的，所以我们不能缩点进行拓扑，而是直接进行拓扑，对于更新不到的点，那么就是平局了。建议手搓几组样例更好的理解（文笔不好，讲不清楚）
代码如下:
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 2e5+5;
int n,dp[MAXN],in[MAXN],tot,p[MAXN];
char s[10];
map <string,int> mp;
vector <int> edge[MAXN];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;++i)
{
scanf("%s",s+1);
int len=strlen(s+1);
string u="",v="";
for(int j=1;j<=3;++j) u+=s[j];
for(int j=len-2;j<=len;++j) v+=s[j];
if(!mp.count(u)) mp[u]=++tot;
if(!mp.count(v)) mp[v]=++tot;
p[i]=mp[v];in[mp[u]]++;
edge[mp[v]].push_back(mp[u]);
}
queue <int> q;
for(int i=1;i<=tot;++i)
{
if(!in[i])
{
dp[i]=1;
q.push(i);
}
}
while(!q.empty())
{
int now=q.front();
q.pop();
for(int i=0;i<edge[now].size();++i)
{
int to=edge[now][i];
if(dp[to]==0)
{
in[to]--;
if(dp[now]==1) dp[to]=2,q.push(to);
else if(in[to]==0)
{
dp[to]=1;
q.push(to);
}
}
}
}
for(int i=1;i<=n;++i)
{
if(dp[p[i]]==1) printf("Takahashi\n");
else if(dp[p[i]]==2) printf("Aoki\n");
else printf("Draw\n");
}
}
? 像这种题目，平局的转移不好判定，那么我们将另外两种判定出来，其他情况就是平局了。换句话说，如果一个集合的子集不好求，我们可以求这个子集的补集，从而得到这个子集。这在某些题目中也是一种优秀的方法。