题意:给一张n*m的方格纸,两个人轮流随意按某一行或某一列减,1张纸减完后变两张都可以被选择,看谁捡到剩下1*1就赢了。
思路:对于任何一个人,都不会先剪出1*n或者n*1,应该这样就必败了。mex求出不属于集合的最小整数,纸片的SG值是后者的纸片的SG的异或值。
#include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<map> #include<queue> #include<vector> #include<string> #define ll long long using namespace std; int n,m,sg[205][205]; int dfs(int x,int y) { if(sg[x][y]!=-1) return sg[x][y]; bool f[205]; memset(f,0,sizeof(f)); for(int i=2;i<=x-i;i++) { f[dfs(i,y)^dfs(x-i,y)]=1; } for(int i=2;i<=y-i;i++) { f[dfs(x,i)^dfs(x,y-i)]=1; } int t=0; while(f[t]) { t++; } return sg[x][y]=t; } int main() { memset(sg,-1,sizeof(sg)); sg[0][0]=0; while(~scanf("%d%d",&n,&m)) { if(dfs(n,m)) { printf("WIN\n"); } else printf("LOSE\n"); } }