「AT1726」「CODE FESTIVAL 2015 OKINAWA OPEN」Dictionary for Shiritori Game
题目传送门
题意
给定大小为 \(n\) 的字符集和 \(m\) 个单词，第 \(i\) 个单词以字符 \(a_i\) 开头，以字符 \(b_i\) 结尾。
Snuke 和 Sothe 轮流玩单词接龙游戏（Snuke 先手）。每次游戏那个人必须说出一个以上个单词的末尾字符开头的单词，第一个人必须说出一个以字符 1 开头的单词。若轮到该人进行游戏时，说不出符合条件的单词，则该人失败。
假设两人绝对聪明，判断谁是胜者或者游戏会永远进行下去。
\(n\le 10^5,m\le 2\times 10^5\)
题解
每个字符当作一个状态，建出游戏图（\(a_i\to b_i\)）。若游戏图中某个点的所有儿子都是必胜态，则当前点必败；若当前点的所有儿子中有一个状态是必败，则当前点必胜；否则为平局。
直接用 dfs 会因为有环而变得很难搞（求助路过的 dalao 帮蒟蒻看一下 代码，WA 3个点 QAQ），所以考虑建反图，倒着推。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| #include <cstdio>
#include <cctype>
#include <cstring>
int read(){
register int x = 0, ch = getchar();
for (; !isdigit(ch); ch = getchar()) ;
for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ '0');
return x;
}
#define N 100005
#define M 200005
int n, m, f[N], h, t, Q[N], d[N];
int edge, to[M], pr[M], hd[N];
void addedge(int u, int v){
to[++edge] = v, pr[edge] = hd[u], hd[u] = edge;
}
int main(){
n = read(), m = read();
for (register int i = 1, x, y; i <= m; ++i)
x = read(), y = read(), addedge(y, x), ++d[x];
h = 0, t = 0;
for (register int i = 1; i <= n; ++i) if (!d[i]) Q[++t] = i, f[i] = 2;
while (h < t){
int u = Q[++h];
if (f[u] == 2)
for (register int i = hd[u]; i; i = pr[i])
!f[to[i]] ? Q[++t] = to[i] : 0, f[to[i]] = 1;
else
for (register int i = hd[u]; i; i = pr[i])
if (!(--d[to[i]])) Q[++t] = to[i], f[to[i]] = 2;
}
if (f[1] == 0) printf("Draw\n");
else if (f[1] == 1) printf("Snuke\n");
else if (f[1] == 2) printf("Sothe\n");
}
|
