两个人轮流剪纸片，直到有一个人剪出1*1的方格就算这个人赢了。然后给出纸片的长和宽，求先手会赢还是会输。
对于任何一个人，都不会先剪出1*n或者n*1，应该这样就必败了。
如果拿到（2，2）（2，3）（3，2），则必赢。
然后直接遍历2-x-i即可。sgfun(i,y)和fun(x-i,y)为补集关系，所以当前sg为这两个sg的异或和。
注意结果不能行动的局面为必胜局面。
#include <iostream> #include <cstdio> #include <cstring> using namespace std; typedef long long ll; const int maxn = 250; int n,m; int sg[maxn][maxn]; int fun(int x,int y) { bool nextt[250]; memset(nextt,0,sizeof(nextt)); if(sg[x][y] != -1) return sg[x][y]; for(int i = 2;i <= x-i; ++i){ nextt[fun(i,y)^fun(x-i,y)] = 1; } for(int i = 2 ; i <= y-i; ++i){ nextt[fun(x,i)^fun(x,y-i)] = 1; } for(int i = 0; ; ++i){ if(nextt[i] == 0){ sg[x][y] = i; return i; } } } int main() { memset(sg,-1,sizeof(sg)); sg[2][2] = sg[2][3] = sg[3][2] = 0; while(scanf("%d%d",&n,&m) == 2){ if(fun(n,m) == 0) printf("LOSE\n"); else printf("WIN\n"); } }
原文：https://www.cnblogs.com/jrfr/p/13519505.html