测试地址：Cutting Game 题目大意：两个人在玩游戏，游戏规则是这样的：给定一张 W×H 的矩形方格纸，双方轮流行动，每次行动将方格纸切割成两部分，每部分也都是完整的矩形方格纸，每一个格子都要保持完整。除第一次行动外，后面的每一次行动都只要选取一个部分进行切割。也就是说， N 次行动后应该会产生N 1个部分。率先切割出一个 1×1 方格的人获得胜利。给定 W 和H，问先手必胜还是必败。 做法：这一题是一种SG博弈。 很容易想到用一个数对 (i,j)(i≤j) 来表示状态，但是要构成SG博弈，需要有终止节点，可是除了 (1,1) 外，所有的 (1,n) 都是N-position（先手必胜），SG函数无法确定，那么我们怎么办呢？那么我们想一想有哪些状态是全部指向N-position的，那这些状态就是P-position（先手必败），容易发现 (2,2),(2,3),(3,3) 就是这样的点，那么这些点的SG函数值为 0 ，边界就确定下来了，那么在下面计算SG函数的过程中只需要考虑切割出的矩形的最小边≥2的情况即可。 再来看怎么求一个状态的SG函数值。我们发现在这个游戏中，一个状态的后继状态可以用两个状态的“组合”来表示，例如 (2,4) 的一个后继状态可表示为 {(2,2),(2,2)} ，注意到分成的两个状态都可以看做一个子游戏，我们把这种组合称为两个游戏的和，那么这种和的SG函数值就是分成的各个子游戏的SG函数值的异或和。那么我们就可以用后继状态的SG函数值推出当前状态的SG函数值了，问题解决。 因为共有 WH 个状态，每个状态最多有 W+H 个后继状态，所以以上算法最终的时间复杂度为 O((W+H)WH) ，可以通过此题。 以下是本人代码：
#include <cstdio> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> using namespace std; int sg[210][210],srt[40010]={0},a,b; void calc_sg() { for(int i=2;i<=200;i++) for(int j=i;j<=200;j++) { if (i<=3&&j<=3) {sg[i][j]=0;continue;} for(int k=2;2*k<=i;k++) srt[sg[k][j]^sg[i-k][j]]++; for(int k=2;2*k<=j;k++) { int i1=i,i2=i,j1=k,j2=j-k; if (i1>j1) swap(i1,j1); if (i2>j2) swap(i2,j2); srt[sg[i1][j1]^sg[i2][j2]]++; } for(int k=0;;k++) if (!srt[k]) {sg[i][j]=k;break;} for(int k=2;2*k<=i;k++) srt[sg[k][j]^sg[i-k][j]]--; for(int k=2;2*k<=j;k++) { int i1=i,i2=i,j1=k,j2=j-k; if (i1>j1) swap(i1,j1); if (i2>j2) swap(i2,j2); srt[sg[i1][j1]^sg[i2][j2]]--; } } } int main() { calc_sg(); while(scanf("%d%d",&a,&b)!=EOF) { if (a>b) swap(a,b); if (sg[a][b]==0) printf("LOSE\n"); else printf("WIN\n"); } return 0; }