SG 函数的简单题目。
1. 题意
两人交替在开始为空字符串的后面加入字符，要求必须随时为给定的字符串集的某一个串的前缀。将会进行 $k$ 次游戏，上一局输的人作为下一局的先手，最后一局胜利的人获得最终的胜利。在足够聪明的情况下，问第一局的先手是否会赢。
字符串的总个数 $\leq10^5$，字符串的总字符数 $\leq10^5$，$k\leq10^9$。
2. 思路
首先，我们可以转化为一个在 Trie 上走，不能走者输的情况。
考虑 $k=1$ 的情况：这不就是一个 SG 函数的应用吗？
遍历一遍 Trie，叶节点为先手必败，如果一个节点的某个儿子是先手必败，那么该节点先手必胜，否则先手必败。
那么，我们可以简单的写出代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| void get_trie(int u)
{
bool has_son = 0;
for (int i = 0; i < 26; ++ i)
if (son[u][i]) has_son = 1, get_trie(son[u][i]);
if (!has_son){
sg[u] = 0;
return;
}
for (int i = 0; i < 26; ++ i)
if (son[u][i] && !sg[son[u][i]])
{
sg[u] = true;
return;
}
sg[u] = false;
return;
}
|
接着，我们考虑 $k=2$ 的情况。
如果先手 $k=1$ 是一定会胜而不可能输的（注意，这里指即使先手想输也不可能），那么，先手一定会在前一局的时候尽一切可能去输（感觉有点不合常理），这样他就会获得下一局的先手，而获得最后的胜利。
所以，我们在 $k>1$ 的时候，不仅要考虑先手能否可以胜利，还要考虑先手能否失败。
怎样计算先手能否失败呢？我们将前面叶节点的时候设为必胜（是指一定可以输掉游戏，不是原来的游戏的必胜），那么如果最后根节点是必胜的话，那么他一定可以在走到叶节点为必胜状态，也就是可以输掉。
接着，我们发现先手有四种情况了：可胜可败，只能胜，只能败，不能胜也不能败（由后手控制力）。
可胜可败：发现先手可以操控答案的走向，一定是可以赢的。
只能胜：最开始的先手和后手会交替先走，所以现在要看 $k$ 的奇偶，奇就是先手胜，偶就是后者胜。
- 只能败：先手每次都会败，也因为每次都败，每次都是先手，所以最后先手败。
- 不能胜也不能败：后手操控答案的走向，所以一定是输的。
那么，我们就可以写出了最后的判断代码：
1
2
3
4
| if ((able_win && able_lose)) puts("First");
else if (able_win) puts(k & 1 ? "First" : "Second");
else if (able_lose) puts("Second");
else puts("Second");
|
3. Code
前面基本已经展示了，这里给一个完整代码。
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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
| #include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int son[N][26], rt = 1, tot = 1;
int id[N], n, k, flag, sg[N], able_lose, able_win;
char str[N];
void insert(int i, char *s)
{
int u = rt;
for (int i = 1; s[i]; ++ i)
{
if (!son[u][s[i] - 'a']) son[u][s[i] - 'a'] = ++ tot;
u = son[u][s[i] - 'a'];
}
id[i] = u;
}
void get_trie(int u)
{
bool has_son = 0;
for (int i = 0; i < 26; ++ i)
if (son[u][i]) has_son = 1, get_trie(son[u][i]);
if (!has_son){
sg[u] = flag;
return;
}
for (int i = 0; i < 26; ++ i)
if (son[u][i] && !sg[son[u][i]])
{
sg[u] = true;
return;
}
sg[u] = false;
return;
}
int main()
{
cin >> n >> k;
for (int i = 1; i <= n; ++ i)
{
scanf("%s", str + 1);
insert(i, str);
}
flag = 1, get_trie(1);
able_lose = sg[1];
flag = 0, get_trie(1);
able_win = sg[1];
if ((able_win && able_lose)) puts("First");
else if (able_win) puts(k & 1 ? "First" : "Second");
else if (able_lose) puts("Second");
else puts("Second");
return 0;
}
|