poj3537 Crosses and Crosses 博弈论

大意：

给定一个\(1 * n\)的棋盘，你和对手轮流在上面画"X"

当出现三个连续的X时，最后一步操作的人胜利

不难发现，在棋盘中画了一个X之后

问题等价于两个一样的子游戏

然后暴力求\(sg\)函数即可

复杂度\(O(n^2)\)

#include <bitset>

#include <cstdio>

#include <cstring>

#include <iostream>

using namespace std;

#define ri register int

#define rep(io, st, ed) for(ri io = st; io <= ed; io ++)

#define drep(io, ed, st) for(ri io = ed; io >= st; io --)

const int sid = 2e3 + 50;

int n, sg[sid];

bitset <sid> ex;

inline void Init() {

	rep(i, 1, 2000) {

		ex.reset();

		rep(j, 1, i) {

			int tmp = 0;

			if(j - 3 >= 0) tmp ^= sg[j - 3];

			if(i - j - 2 >= 0) tmp ^= sg[i - j - 2];

			ex[tmp] = 1;

		}

		rep(j, 0, 2000)

		if(!ex[j]) {

			sg[i] = j;

			break;

		}

	}

}

int main() {

	Init();

	while(scanf("%d", &n) == 1)

	printf("%d\n", (sg[n]) ? 1 : 2);

	return 0;

}

巴特西

poj3537 Crosses and Crosses 博弈论

最新文章

热门文章