POJ 2311 Cutting Game 题解

前置芝士

Cutting Game

给定一张 \(N\times M\) 的矩形网格纸,两名玩家轮流行动。

在每一次行动中,可以任选一张矩形网格纸,沿着某一行或某一列的格线,把它剪成两部分。

首先剪出 \(1\times 1\) 的格纸的玩家获胜。

两名玩家都采取最优策略行动,求先手是否能获胜。

\(2\leq N,M\leq 200\)。

题目链接:POJ 2311 Cutting GameACWing 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;
}
上一篇:面向对象(15):形式参数和返回值问题案例


下一篇:Study Blazor .NET(二)安装