POJ2311 Cutting Game 博弈論

題目連結

http://poj.org/problem?id=2311

分析

和Nim遊戲有異曲同工之妙，隻不過最終局面的勝負規定不同，是以需要一步轉化，

易知，若長或寬為 1 1 1，則先手必勝，而 2 × 2 2 \times 2 2×2、 2 × 3 2 \times 3 2×3 和 3 × 2 3 \times 2 3×2 則是必敗；

故設上面三個必敗态的SG函數為 0 0 0，

而某張紙對應的SG函數則是來源于将其剪開後兩張紙的SG函數的異或和。

AC代碼

#include <cstdio>
#include <cstring>

const int maxn = 205;

int sg[maxn][maxn];

inline int judge(int a, int b) {
	if (sg[a][b] != -1) return sg[a][b];
	int vis[maxn * maxn];
	memset(vis, 0, sizeof(vis));
	for (int i = 2; 2 * i <= a; ++i) vis[judge(i, b) ^ judge(a - i, b)] = 1;
	for (int i = 2; 2 * i <= b; ++i) vis[judge(a, i) ^ judge(a, b - i)] = 1;
	for (int i = 0; ; ++i) if (!vis[i]) return sg[a][b] = i;
}

int main() {
	memset(sg, -1, sizeof(sg));
	sg[2][2] = sg[2][3] = sg[3][2] = 0;
	int w, h;
	while (scanf("%d%d", &w, &h) == 2) {
		if (judge(w, h)) printf("WIN\n");
		else printf("LOSE\n");
	}
	return 0;
}