作者:lucky2502882647 | 来源:互联网 | 2023-10-11 13:53
题目【题目描述】pure和dirty决定玩$T$局游戏。对于每一局游戏,有$n$个字符串,并且每一局游戏由$K$轮组成。具体规则如下:在每一轮游戏中,最开始有一个空串,两者轮流向串
题目
【题目描述】
pure 和 dirty 决定玩 $T$ 局游戏。对于每一局游戏,有 $n$ 个字符串,并且每一局游戏由 $K$ 轮组成。具体规则如下:在每一轮游戏中,最开始有一个空串,两者轮流向串的末尾添加一个字符,并且需要保证该串为 $n$ 个字符串中任意一个串的前缀,不能操作的人输掉这一轮,并且在下一轮游戏中由该轮输掉的人先手。另外为了遵循女士优先的原则,在每一局游戏的第一轮均由 pure 先手。
玩家的目标是获得整局游戏的胜利,一局游戏的胜利条件是:对手输掉最后一轮游戏。我们可以假定 pure 和 dirty 都足够聪明。
现在,对于每一局游戏,pure 想知道获胜者是谁。
【输入格式】
第一行一个整数 $T$,表示游戏局数。
接下来 $T$ 组数据,每组数据第一行两个整数 $n,K$,表示字符串数和轮数,接下来$n$行,每行一个字符串。
【输出格式】
对于每一局游戏,输出一行 `Pure` 或者 `Dirty` 表示获胜者。
【样例输入】
2
2 3
a
b
1 2
ab
【样例输出】
Pure
Dirty
【数据范围与提示】
对于 $10\%$ 的数据,字符串总长不超过$5$,且 $K \le 2$ ;
对于 $20\%$ 的数据,字符串总长不超过$5$;
对于另外 $20\%$ 的数据,$K = 1$;
对于 $100\%$ 的数据,$1 \le n \le 10^5; 1 \le K \le 10^9; 1 \le T \le 10$,每局游戏字符串总长不超过 $10^5$,其中字符串非空且均为小写英文字母。
题解
考虑如何博弈最优
如果先手有办法控制自己必胜和必败,那么无论多少轮都能必胜(前面都必败保证先手,最后一轮必胜)
如果只能控制必胜,那么奇数轮的时候都能赢(后手抵消先手)
剩下的则后手必胜
那么把字符串建一棵 tire 树,dp 必胜和必败态即可
代码
其实两个状态是可以压在一起的
1 #include
2 #define LL long long
3 #define _(d) while (d(isdigit(ch = getchar())))
4 using namespace std;
5 int R() {
6 int x;
7 bool f = 1;
8 char ch;
9 _(!) if (ch == ‘-‘) f = 0;
10 x = ch ^ 48;
11 _() x = (x <<3) + (x <<1) + (ch ^ 48);
12 return f ? x : -x;
13 }
14 const int N = 2e5 + 5;
15 int n, K, tr[N][28], tot, dep[N];
16 bool f[N], g[N]; // f[x] ±Ø°Ü g[x] ±Øʤ
17 char ch[N];
18 void insert() {
19 int x = 0, len = strlen(ch + 1);
20 for (int i = 1, c; i <= len; i++) {
21 if (!tr[x][c = ch[i] - ‘a‘])
22 tr[x][c] = ++tot;
23 x = tr[x][c];
24 }
25 return;
26 }
27 void dfs(int x) {
28 bool flag = 1;
29 for (int i = 0, v; i <26; i++)
30 if (v = tr[x][i])
31 flag = 0, dep[v] = dep[x] + 1, dfs(v);
32 if (flag) {
33 if (dep[x] & 1)
34 g[x] = 1;
35 else
36 f[x] = 1;
37 return;
38 }
39 if (dep[x] & 1) {
40 g[x] = 1, f[x] = 1;
41 for (int i = 0; i <26; i++) {
42 if (tr[x][i] && !g[tr[x][i]])
43 g[x] = 0;
44 if (tr[x][i] && !f[tr[x][i]])
45 f[x] = 0;
46 }
47 } else {
48 for (int i = 0; i <26; i++) {
49 if (tr[x][i] && f[tr[x][i]])
50 f[x] = 1;
51 if (tr[x][i] && g[tr[x][i]])
52 g[x] = 1;
53 }
54 }
55 return;
56 }
57 void clean() {
58 memset(f, 0, sizeof f);
59 memset(g, 0, sizeof g);
60 memset(tr, 0, sizeof tr);
61 tot = 0;
62 }
63 int main() {
64 for (int T = R(); T--;) {
65 clean(), n = R(), K = R();
66 for (int i = 1; i <= n; i++) scanf("%s", ch + 1), insert();
67 dfs(0);
68 if (f[0] && g[0] || g[0] && (K & 1))
69 puts("Pure");
70 else
71 puts("Dirty");
72 }
73 return 0;
74 }
View Code
字符串游戏(strgame)——博弈