「POJ 2311」Cutting Game - 博弈论 + SG 函数

发表于 分类于 ， 阅读次数： Disqus：

题意描述

POJ 链接

有一张 \(w \times h (2 \le w, h \le 200)\) 大小的矩形网格纸片，两名玩家轮流行动。在每一次行动中，任选一张纸片，沿着某一行或某一列的格线剪成两部分。首先剪出 \(1 \times 1\) 大小纸片的玩家获胜。两名玩家均以最优策略行动，问先手是否有必胜策略。

解题思路

这个问题不好直接问题，我们可以转化以下。我们可以发现剪出 \(1 \times n\) 或 \(n \times 1\) 的玩家必输。于是问题转化为了先剪出 \(1 \times n\) 或 \(n \times 1\) 的玩家输。这样我们就可以用 SG 函数解决。

我们设 \(\operatorname{SG}(x, y)\) 表示 \(x \times y\) 纸片的 SG 函数值。我们可以先初始化 \(\operatorname{SG}(2, 2) = \operatorname{SG}(2, 3) = \operatorname{SG}(3, 2) = 0\)。接下来我们需要考虑状态转移。

我们可以发现，对于 \(x \times y\) 这种纸片，可以拆分成 \((i \times y, (x - i) \times y)\) 以及 \((x \times i, x \times (y - i))\) 这若干种情况。将这若干种情况的 SG 函数值求 \(\operatorname{mex}\) 即可。然后对于每种情况就将该情况的两个状态异或即可。等价于下列等式：

\[ \begin{align*} \operatorname{SG}(x, y) = \operatorname{mex}(&\{t | t = \operatorname{SG}(i, y) \oplus \operatorname{SG}(x - i, y), i > 2, i \le x - i\} \cup \\ &\{t | t = \operatorname{SG}(x, i) \oplus \operatorname{SG}(x, y - i), i > 2, i \le y - i\}) \end{align*} \]

最后答案为当 \(\operatorname{SG}(w, h) > 0\) 时先手必胜，否则先手必败。

代码演示

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
#include <cstdio>
#include <cstring>
#include <vector>

const int MAXN = 200;

int w, h;
int sg[MAXN + 1][MAXN + 1];

int SG(int x, int y) {
    if (sg[x][y] != -1) return sg[x][y];

    std::vector<bool> vis(std::max(w, h) + 1, false);
    for (int i = 2; i <= x - i; i++) vis[SG(i, y) ^ SG(x - i, y)] = 1;
    for (int i = 2; i <= y - i; i++) vis[SG(x, i) ^ SG(x, y - i)] = 1;

    sg[x][y] = 0;
    while (vis[sg[x][y]]) sg[x][y]++;

    return sg[x][y];
}

void prepare() {
    memset(sg, -1, sizeof(sg));
    sg[2][2] = sg[2][3] = sg[3][2] = 0;
}

int main() {
    prepare();

    while (scanf("%d %d", &w, &h) != EOF) {
        puts(SG(w, h) ? "WIN" : "LOSE");
    }

    return 0;
}