题意：n*m的纸片，一次切成两份，谁先切出1*1谁胜
Multi-SG？
不太一样啊
本题的要求是后继游戏中任意游戏获胜就可以了....
这时候，如果游戏者发现某一单一游戏他必败他就不会再玩了
$2*2,2*3,3*3$都不会再玩了(除非只剩下这样的纸片了)，所以都可以认为是终止状态，必败
在此基础上按照Multi-SG递推就对了
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> using namespace std; typedef long long ll; const int N=205; inline int read(){ char c=getchar();int x=0,f=1; while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1;c=getchar();} while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘;c=getchar();} return x*f; } int n,m,f[N][N],vis[N]; int main(){ freopen("in","r",stdin); n=200;m=200; f[2][2]=f[2][3]=f[3][2]=f[3][3]=0; for(int i=2;i<=n;i++) for(int j=2;j<=m;j++){ memset(vis,0,sizeof(vis)); for(int k=2;k<i-1;k++) vis[ f[k][j]^f[i-k][j] ]=1; for(int k=2;k<j-1;k++) vis[ f[i][k]^f[i][j-k] ]=1; for(int k=0;;k++) if(!vis[k]) {f[i][j]=k;break;} } while(scanf("%d%d",&n,&m)!=EOF) puts(f[n][m] ? "WIN" : "LOSE"); }
POJ 2311 Cutting Game [Multi-SG?]
原文：http://www.cnblogs.com/candy99/p/6562109.html