题目来源：POJ2311 Cutting Game
题意
给定一张 \(N*M\) 的矩形网格纸，两名玩家轮流行动。在每一次行动中，可以任选一张矩形网格纸，沿着某一行或者某一列的格线，把它剪成两部分。首先剪出 \(1*1\) 的玩家获胜。两名玩家都采取最优策略行动，求先手是否必胜。
\[1 \leqslant N,M \leqslant 200
\]
Solution
可以任选一张矩形网格纸，显然是一个独立的有向图游戏。
考虑SG函数的构造方式，需要找出一个必败的局面作为有向图有向图的起点。
因为剪出 \(1 * 1\) 的获胜，那么显然根据最优策略原则，不会剪出 \(1 * X\) 的部分，那么必败局面为 \(2 * 2, 2 * 3, 3 * 3\) 。
对于一张独立的网格纸，其SG函数是固定的，可以通过记忆化来快速求解。
考虑如何计算 \(SG(N, M)\)， 根据SG函数的定义：
\[SG(N, M) = mex(\{SG(i, M) \ \text{xor} \ SG(N - i, M)\} \cup \{SG(N, i) \ \text{xor} \ SG(N, M - i)\})
\]
通过记忆化搜索便可以求出答案，考虑总体时间复杂度为 \(O(n^3)\)
Code
点击查看代码
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
#include <cmath>
using namespace std;
const int N = 250;
typedef long long lld;
inline int read() {
register int w = 0, f = 1;
register char c = getchar();
while (c > '9' || c < '0') {
if (c == '-') f = -1;
c = getchar();
}
while (c >= '0' && c <= '9') {
w = w * 10 + c - '0';
c = getchar();
}
return w * f;
}
int n, m;
int sg[N][N];
inline int SG(register int x, register int y) {
if (sg[x][y] != -1) return sg[x][y];
register bool f[N];
memset(f, 0, sizeof (f));
for (int i = 2; i <= x - i; ++i) f[SG(i, y) ^ SG(x - i, y)] = 1;
for (int i = 2; i <= y - i; ++i) f[SG(x, i) ^ SG(x, y - i)] = 1;
register int t = 0;
while (f[t]) t++;
return sg[x][y] = t;
}
int main() {
memset(sg, -1, sizeof (sg));
sg[2][2] = sg[2][3] = sg[3][2] = 0;
while (~scanf("%d%d", &n, &m)) puts(SG(n, m) ? "WIN" : "LOSE");
return 0;
}