字符串游戏（strgame）—

题目

【题目描述】

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 必胜和必败态即可

代码

其实两个状态是可以压在一起的

 #include <bits/stdc++.h>

 #define LL long long

 #define _(d) while (d(isdigit(ch = getchar())))

 using namespace std;

 int R() {

     int x;

     bool f = ;

     char ch;

     _(!) if (ch == '-') f = ;

     x = ch ^ ;

     _() x = (x << ) + (x << ) + (ch ^ );

     return f ? x : -x;

 }

 const int N = 2e5 + ;

 int n, K, tr[N][], tot, dep[N];

 bool f[N], g[N];  // f[x] ±Ø°Ü g[x] ±ØÊ¤

 char ch[N];

 void insert() {

     int x = , len = strlen(ch + );

     for (int i = , c; i <= len; i++) {

         if (!tr[x][c = ch[i] - 'a'])

             tr[x][c] = ++tot;

         x = tr[x][c];

     }

     return;

 }

 void dfs(int x) {

     bool flag = ;

     for (int i = , v; i < ; i++)

         if (v = tr[x][i])

             flag = , dep[v] = dep[x] + , dfs(v);

     if (flag) {

         if (dep[x] & )

             g[x] = ;

         else

             f[x] = ;

         return;

     }

     if (dep[x] & ) {

         g[x] = , f[x] = ;

         for (int i = ; i < ; i++) {

             if (tr[x][i] && !g[tr[x][i]])

                 g[x] = ;

             if (tr[x][i] && !f[tr[x][i]])

                 f[x] = ;

         }

     } else {

         for (int i = ; i < ; i++) {

             if (tr[x][i] && f[tr[x][i]])

                 f[x] = ;

             if (tr[x][i] && g[tr[x][i]])

                 g[x] = ;

         }

     }

     return;

 }

 void clean() {

     memset(f, , sizeof f);

     memset(g, , sizeof g);

     memset(tr, , sizeof tr);

     tot = ;

 }

 int main() {

     for (int T = R(); T--;) {

         clean(), n = R(), K = R();

         for (int i = ; i <= n; i++) scanf("%s", ch + ), insert();

         dfs();

         if (f[] && g[] || g[] && (K & ))

             puts("Pure");

         else

             puts("Dirty");

     }

     return ;

 }

巴特西

字符串游戏（strgame）——博弈

题目

题解

代码

最新文章

热门文章