\(\sf E-Shiritori\)
博主的 \(\rm bibi\) 时间
“怎么会有人连 \(\rm abc\) 都不会做啊？”
解法
设每个串前三位为 \(u\)，后三位为 \(v\)。
先开始想的是从 \(u\) 向 \(v\) 连边，但是判 Draw 即判环会很难。因为环上某点可能有非 Draw 解。
反着建边就行了。
代码
#include <bits/stdc++.h>
using namespace std;
#define rep(i,_l,_r) for(register signed i=(_l),_end=(_r);i<=_end;++i)
#define print(x,y) write(x),putchar(y)
template <class T> inline T read(const T sample) {
T x=0; int f=1; char s;
while((s=getchar())>‘9‘||s<‘0‘) if(s==‘-‘) f=-1;
while(s>=‘0‘&&s<=‘9‘) x=(x<<1)+(x<<3)+(s^48),s=getchar();
return x*f;
}
template <class T> inline void write(const T x) {
if(x<0) return (void) (putchar(‘-‘),write(-x));
if(x>9) write(x/10);
putchar(x%10^48);
}
const int maxn=4e5+5;
int n,len,idx,in[maxn],ans[maxn];
char s[maxn][10];
map <string,int> mp;
vector <int> e[maxn];
queue <int> q;
void Go() {
rep(i,1,idx) {
ans[i]=-1;
if(!in[i]) q.push(i),ans[i]=0;
}
while(!q.empty()) {
int t=q.front(); q.pop();
for(int i=0;i<e[t].size();++i) {
int v=e[t][i];
if(ans[v]==-1) {
--in[v];
if(!ans[t]) ans[v]=1,q.push(v);
else if(!in[v]) ans[v]=0,q.push(v);
}
}
}
}
int main() {
string u,v; int x,y;
n=read(9);
rep(i,1,n) {
scanf("%s",s[i]+1); len=strlen(s[i]+1);
u=""; u+=s[i][1];
u+=s[i][2],u+=s[i][3];
v=""; v+=s[i][len-2];
v+=s[i][len-1],v+=s[i][len];
if(!mp[u]) mp[u]=++idx;
if(!mp[v]) mp[v]=++idx;
x=mp[u],y=mp[v];
e[y].push_back(x); ++in[x];
}
Go();
rep(i,1,n) {
len=strlen(s[i]+1);
v=""; v+=s[i][len-2];
v+=s[i][len-1],v+=s[i][len];
y=mp[v];
if(ans[y]==-1) puts("Draw");
else if(ans[y]) puts("Aoki");
else puts("Takahashi");
}
return 0;
}