Cutting Game
给定一张 \(N\times M\) 的矩形网格纸,两名玩家轮流行动。
在每一次行动中,可以任选一张矩形网格纸,沿着某一行或某一列的格线,把它剪成两部分。
首先剪出 \(1\times 1\) 的格纸的玩家获胜。
两名玩家都采取最优策略行动,求先手是否能获胜。
\(2\leq N,M\leq 200\)。
题目链接:POJ 2311 Cutting Game,ACWing 219. 剪纸游戏
Solution
最后终止条件为剪出 \(1\times 1\) 的获胜,不符公平组合游戏中的 "终止的局面为必败点" 的性质,但可以转化终止的局面,使得终止的局面为必败点。
能剪出 \(1\times 1\) 的纸片当且仅当当前为 \(1\times x\) 或 \(x\times 1,x>1\) 的纸片,这些纸片一定是必败点。
那么把终点定义成当前局面为 \(1\times x\) 或 \(x\times 1,x>1\),就满足了公平组合游戏的性质。
设 \(SG(x,y)\) 为 \(x\times y\) 的局面的 SG 函数值。一刀可以横着切也可以竖着切,切完一刀后是分成了两个局面,由 SG 定理,如果这样切当前 SG 函数的值就为分成的两个局面的 SG 函数值的异或值。
所以有:
\[SG(x,y)=\text{mex}(\{SG(i,y)\oplus SG(x-i,y)\mid 2\leq x-2\}\cup \{SG(x,i)\oplus SG(x,y-i)\mid 2\leq i\leq y-2\}) \]注意到 \(SG\) 不会超过 \(N,M\),则可以在 \(\mathcal{O}(N^3)\) 的复杂度内求解,也就是 \(\mathcal{O}(N^2)\) 枚举,单次 \(\mathcal{O}(N)\) 转移。
Code
int n, m;
int SG[210][210], vis[210];
void pre() {
for(int x = 2; x <= 200; ++x)
for(int y = 2; y <= 200; ++y) {
for(int i = 0; i <= 200; ++i) vis[i] = 0;
for(int i = 2; x - i >= 2; ++i) vis[SG[i][y] ^ SG[x-i][y]] = 1;
for(int i = 2; y - i >= 2; ++i) vis[SG[x][i] ^ SG[x][y-i]] = 1;
for(int i = 0; i <= 200; ++i)
if(!vis[i]) {
SG[x][y] = i;
break;
}
}
}
signed main() {
pre();
while(scanf("%d%d", &n, &m) != EOF)
printf("%s\n", SG[n][m] == 0 ? "LOSE" : "WIN");
return 0;
}