链接：https://vjudge.net/problem/POJ-2311
题意：给出一个N*M的纸片，每一次可以把一部分剪成两部分，谁剪出1*1的就赢了。
题解：二维sg函数，每一个变量可以随便转但是都不会先剪出1*n或者n*1，这样就必败了，直接让状态的后继中最小的边是2即可
#include <cstdio> #include <iostream> #include <cstring> using namespace std; int sg[205][205]; int vis[520]; int dfs_sg(int n, int m) { if(sg[n][m]!=-1) return sg[n][m]; memset(vis, 0, sizeof(vis)); for(int i=2; i<=n-i; i++) //sg[1][k] 和 sg[k][1]=0, 所以都不会这样的后继状态 vis[dfs_sg(i, m)^dfs_sg(n-i, m)]=1; for(int i=2; i<=m-i; i++) //二维的sg有2个方向可以转 vis[dfs_sg(n, i)^dfs_sg(n, m-i)]=1; for(int i=0; ; i++) if(!vis[i]) return sg[n][m]=i; } int main() { //freopen("in.txt", "r", stdin); memset(sg, -1, sizeof(sg)); int n, m; while(cin>>n>>m) { sg[1][1]=0; printf(dfs_sg(n,m)? "WIN\n":"LOSE\n"); } return 0; }
原文：https://www.cnblogs.com/Yokel062/p/11688403.html
