Description
题意：给定 \(n\) 个单词，一个单词的后三位若和另一个单词的前三位相同，则可以连一条有向边，问每次从第 \(i\) 个单词开始，两人交替说出单词，说不出的人输，问每次的结果，\(1\leq n\leq2\times10^5\)。
Solution：
大体思路便是建返图后倒推每个点的状态，不过实现有一些细节。
整篇题解中：
-1表示平手。
0表示必败。
1表示必胜。
因为建的返图，所以胜负均为下一个人的角度。
连边
暴力连边的时间复杂度是 \(\omicron(n^2)\),我们需要改变连边方式。
我最开先的思路是建中转点，但这样会让之后树上的操作很麻烦，题解的方法是自连。
比如：abcd和bcda。设bcd为1，abc为2，cda为3。按照自连，我们得到以下这张图。
原本的连边应该是\(<2,1>\) \(\rightarrow\) \(<1,3>\)，因为abcd的尾和bcda的头相同，所以这两个点实则是一个。这样连边的复杂度降到了 \(\omicron(n)\)。不过保存答案时要把 \(i\) 当做 \(i\) 的后三个字符进行操作。
比如上面这张图，\(ans[2]=0\)，\(ans[1]=1\)，\(ans[3]=0\)，把abcd的答案设为 \(ans[1]\),bcda的答案当做 \(ans[3]\)，与直接两者相连的答案相同。以此类推。
Code:
for(int i=1,x,y;i<=n;i++)
{
cin>>s;
int len=s.length();
string tmp;
tmp=s.substr(0,3);
if(!mp[tmp])
{
mp[tmp]=++cnt;
}
x=mp[tmp];//前三个。
tmp.clear();
tmp=s.substr(len-3,3);
if(!mp[tmp])
{
mp[tmp]=++cnt;
}
y=mp[tmp];//后三个。
in[x]++;
add(y,x);//这两行是在建反图。
vis[i]=y;//用来转移答案。
}
转移
一个比较显然的地方是选择的奇偶会影响结果。
设当前点为 \(i\)，下一个点为 \(v\)，初始所有点都为平局，0入度的点为必败。
请看下面这幅图：
Takahashi下1，Aoki若下4，Takahashi败；Aoki下2，Takahashi胜。但Aoki很明显会选择下4。
由此我们得出最短链的奇偶性决定结果。这就解决了多入度的胜负情况。
再考虑上环，如下图：
\(ans[5]\)=0，\(ans[4]=1\),此时入环，环内其他点均不能由4转移到，因为 \(i=4\) 时，下一个人必定走5，取得胜利。
也就是说环上的点除直接与环外连接的那些外，其他均为平局。
既然我不进环，从环出去的那些点(正图是入环)也不会被更新，故会保持平局。
怎么入环退出呢？这个好办，判断入入度个数就行。
所以只有 \(ans[i]\) 为1或0，且 \(v\) 不在环内时可以更新。
Code：
int now=q.front();
q.pop();
for(int i=0;i<vv[now].size();i++)
{
int v=vv[now][i];
if(ans[v]!=-1) continue;//胜 负 已 分------->拥有最短链的人获胜。
in[v]--;
if(!ans[now])//当前为败。
{
ans[v]=1;
q.push(v);
continue;
}
if(!in[v])//否则便是当前为胜，且避免了卡环。
{
ans[v]=0;q.push(v);
}
}
注意存的是top序，所以用 \(\operatorname{vector}\) 存边。
手写队列挂了。。。
完整代码
#include<iostream>
#include<cstring>
#include<map>
#include<vector>
#include<queue>
using namespace std;
map<string,int> mp;
const int MAXN=2e5+5;
int n,in[MAXN<<1],head[MAXN<<1],ans[MAXN<<1],cnt;//-1为平，0为败，1为胜 ------>这里胜负都是指后手的胜负,因为连的反向边。
int vis[MAXN<<1];//实在想不过来画画图~
string s;
struct ren{
int to,next;
}a[MAXN<<1];
vector<int> vv[MAXN];
void add(int x,int y)
{
vv[x].push_back(y);
}
queue<int> q;
int main()
{
scanf("%d",&n);
for(int i=1,x,y;i<=n;i++)
{
cin>>s;
int len=s.length();
string tmp;
tmp=s.substr(0,3);
if(!mp[tmp])
{
mp[tmp]=++cnt;
}
x=mp[tmp];//前三个。
tmp.clear();
tmp=s.substr(len-3,3);
if(!mp[tmp])
{
mp[tmp]=++cnt;
}
y=mp[tmp];//后三个。
in[x]++;
add(y,x);//注意，这两行是在建反图，从而倒推得到每个点的胜负关系。
vis[i]=y;
}
for(int i=1;i<=cnt;i++)
{
ans[i]=-1;
if(!in[i])
{
q.push(i);
ans[i]=0;
}
}
while(q.size())
{
int now=q.front();
q.pop();
for(int i=0;i<vv[now].size();i++)
{
int v=vv[now][i];
if(ans[v]!=-1) continue;//胜 负 已 分------->拥有最短链的人获胜。
in[v]--;
if(!ans[now])
{
ans[v]=1;
q.push(v);
continue;
}
if(!in[v])//避免了卡环。
{
ans[v]=0;q.push(v);
}
}
}
for(int i=1;i<=n;i++)
{
if(!ans[vis[i]]) printf("Takahashi\n");
if(ans[vis[i]]==1) printf("Aoki\n");
if(ans[vis[i]]==-1) printf("Draw\n");
}
return 0;
}//冰汽时代