Cutting Game

最近博弈论专题,感觉自己没了。。。(果然借了智商高利贷迟早是要还的

首先我们发现,切割过后的纸片是可以单独考虑的。

我们再分析一下题意。

首先,面对只要有一边长为1的纸片,我就一定会赢。

而且,题目说的是切割出的任意纸片!!!这就意味着假设一张纸被切成了1和2,后手切了1,我还可以继续切2!!!(我在这个地方理解了半天才懂,这就是语文考D的人呐

这就符合我们的sg函数。(其实是因为我知道这是sg

既然是二维的sg,就枚举行与列的分界线就行了。

等等先别走。当你开开心心码完发现,,,样例都过不了??

我们还忽略了一点:当你的分割中出现了一边长为1的纸片就赢不了了。其实这是因为这道题与基本模型有点点不一样:取石子是强制要求石子全取完的,也就是如果有两个必胜态,先手反而会输。但这道题是只要割到\((1,1)\)就直接结束了,就像是你本来在做活动时想攒很多钱买辅xiaohuang 书,但攒完后发现活动没辽。因为根本不符合性质,显然我们就不能从一边为1的状态转移了。

上马吗?马比车快哟。

#include<cstdio>
#include<cstring>

int n, m;
bool vis[1002];
int sg[205][205];

int read() {
	int x = 0, f = 1; char s;
	while((s = getchar()) > '9' || s < '0') if(s == '-') f = -1;
	while(s >= '0' && s <= '9') {
		x = (x << 1) + (x << 3) + (s ^ 48);
		s = getchar();
	}
	return x * f;
}

int main() {
	for(int i = 1; i <= 200; ++ i) {
		for(int j = 1; j <= 200; ++ j) {
			memset(vis, 0, sizeof vis);
			for(int k = 2; k <= j - 2; ++ k) vis[sg[i][k] ^ sg[i][j - k]] = 1;
			for(int k = 2; k <= i - 2; ++ k) vis[sg[k][j] ^ sg[i - k][j]] = 1;
			for(int k = 0; ; ++ k) if(! vis[k]) {sg[i][j] = k; break;}
		}
	}
	while(scanf("%d %d", &n, &m) != EOF) {
		puts(sg[n][m] ? "WIN" : "LOSE");
	}
	return 0;
}
原文地址:https://www.cnblogs.com/AWhiteWall/p/12326530.html