【Foreign】Game [博弈论][DP]
Game
Time Limit: 20 Sec Memory Limit: 512 MB
Description
从前有个游戏。游戏分为 k 轮。
给定一个由小写英文字母组成的字符串的集合 S，
在每轮游戏开始时，双方会得到一个空的字符串，
然后两人轮流在该串的末尾添加字符，并且需要保证新的字符串是 S 中某个串的前缀，直到有一方不能操作，则不能操作的一方输掉这一轮。
新的一轮由上一轮输的人先手，最后一轮赢的人获得游戏胜利。
假定双方都采取最优策略，求第一轮先手的一方能否获胜。
Input
输入包含多组数据。
每组数据的第一行包含两个整数 n,k，分别表示字符串的数量和游戏的轮数。
接下来 n 行，每行一个由小写英文字母组成的字符串。
Output
对于每组数据输出一行，若先手能获胜输出 HY wins!，否则输出 Teacher wins!
Sample Input
2 3
a
b
3 1
a
b
c
Sample Output
HY wins!
HY wins!
HINT
1 ≤ n ≤ 1e5,1 ≤ k ≤ 1e9，保证所有字符串长度不超过 1e5，数据组数不超过 10。
Solution
显然Trie上这个DP显然就是为了求：一轮中，先手是否必胜或者必败。显然，一个点如果可以走向必败点那么就可以必胜。
Code
1 #include<iostream>
2 #include<string>
3 #include<algorithm>
4 #include<cstdio>
5 #include<cstring>
6 #include<cstdlib>
7 #include<cmath>
8 using namespace std;
9 typedef long long s64;
10 typedef unsigned int u32;
11
12 const int ONE = 1e6 + 5;
13
14 int n, k;
15 char s[ONE];
16 int next[ONE][27], total, root = 1;
17 int f[ONE], g[ONE];
18
19 int get()
20 {
21 int res=1,Q=1;char c;
22 while( (c=getchar())<48 || c>57 )
23 if(c==\'-\')Q=-1;
24 res=c-48;
25 while( (c=getchar())>=48 && c<=57 )
26 res=res*10+c-48;
27 return res*Q;
28 }
29
30 void Insert()
31 {
32 scanf("%s", s + 1);
33 int u = root, n = strlen(s + 1);
34 for(int i = 1; i <= n; i++)
35 {
36 int c = s[i] - \'a\' + 1;
37 if(!next[u][c]) next[u][c] = ++total;
38 u = next[u][c];
39 }
40 }
41
42 void Dfs_f(int u)
43 {
44 if(!u) return;
45 int PD = 1;
46 for(int c = 1; c <= 26; c++) if(next[u][c]) {PD = 0; break;}
47 if(PD) {g[u] = 0; return;}
48
49 PD = 0;
50 for(int c = 1; c <= 26; c++)
51 {
52 Dfs_f(next[u][c]);
53 if(next[u][c] && f[next[u][c]] == 0) PD = 1;
54 }
55 f[u] = PD;
56 }
57
58 void Dfs_g(int u)
59 {
60 if(!u) return;
61 int PD = 1;
62 for(int c = 1; c <= 26; c++) if(next[u][c]) {PD = 0; break;}
63 if(PD) {g[u] = 1; return;}
64
65 PD = 0;
66 for(int c = 1; c <= 26; c++)
67 {
68 Dfs_g(next[u][c]);
69 if(next[u][c] && g[next[u][c]] == 0) PD = 1;
70 }
71 g[u] = PD;
72 }
73
74 int main()
75 {
76 while(scanf("%d %d", &n, &k) != EOF)
77 {
78 memset(f, 0, sizeof(f));
79 memset(g, 0, sizeof(g));
80 memset(next, 0, sizeof(next));
81 total = 1;
82 for(int i = 1; i <= n; i++)
83 Insert();
84 Dfs_f(1); Dfs_g(1);
85 if(f[1] == 1 && g[1] == 1) printf("HY wins!\n");
86 else
87 if(f[1] == 1)
88 k % 2 == 1 ? printf("HY wins!\n") : printf("Teacher wins!\n");
89 else
90 printf("Teacher wins!\n");
91 }
92 }
View Code
版权声明：本文为BearChild原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。