link

题目大意

有一 $W\times H$ 的矩阵，两人博弈，每次可以沿网格水平切割或竖直切割，当切割后出现 $1\times 1$ 的格子则获胜。给定 $W,H(1\le W,H\le 200)$，问先手必胜还是必败。

题解

博弈论。

显然必胜还是必败只跟当前矩阵的长宽有关，记忆化直接求 sg 函数值。

sg(w,h)=mex{sg(i,h)⊕sg(w−i,h),sg(w,j)⊕sg(w,h−j)}sg(w,h)=mex\\{ sg(i,h)\\oplus sg(w-i,h),sg(w,j)\\oplus sg(w,h-j)\\}sg(w,h)=mex{sg(i,h)⊕sg(w−i,h),sg(w,j)⊕sg(w,h−j)}

但是直接写会挂。

考虑 $1\times 1$ 格子这个胜利条件。显然，当一方出现 $1\times x$ 或 $x\times 1$ 的矩阵后，一次就能切出 $1\times 1$ 从而获胜。所以肯定不会让对方出现这两个局面，也即切割时不能切出长或宽为 $1$ 的矩阵。注意这点即可 AC.

时间复杂度 O(n2)O(n^2)O(n2).

代码

#include <cstdio>
#include <cstring>
using namespace std;
int n, m, sg[205][205];
int getsg(int w, int h) {if (w == 1 && h == 1) return sg[w][h] = 0;if (sg[w][h] != -1) return sg[w][h];int mex[205];memset(mex, 0, sizeof(mex));for (int i = 2; i <= w / 2 && w - i >= 2; i++) mex[getsg(i, h) ^ getsg(w - i, h)] = 1;//w/2为了加快速度for (int i = 2; i <= h / 2 && h - i >= 2; i++) mex[getsg(w, i) ^ getsg(w, h - i)] = 1;for (int i = 0; i <= 200; i++)if (!mex[i]) {sg[w][h] = i;break;}return sg[w][h];
}
int main() {memset(sg, -1, sizeof(sg));while (scanf("%d%d", &n, &m) != EOF) {if (getsg(n, m)) printf("WIN\\n");else printf("LOSE\\n");}return 0;
}

END