给出一个N*M的纸片,每一次可以把一部分剪成两部分,谁剪出1*1的就赢了。
?id=2311
对于任何一个人,都不会先剪出1*n或者n*1,应该这样就必败了。
那我们考虑一个状态的后继中,最小的边也是2,这样就可以避免之前的问题,也不需要考虑类似ANTI-SG。
一旦出现2*2,,2*3,3*2,这些都成了终止状态,不论怎么剪都会出现1*n,或者n*1
还是考察SG函数
# include<stdio.h># include<algorithm># include<iostream># include<string.h>using namespace std;# define N 210int sg[N][N];int GetSG(int n,int m){int i;if(sg[n][m]!=-1)return sg[n][m]; int vis[N];memset(vis,0,sizeof(vis));for(i=2; i<=n-i; i++)vis[GetSG(i,m)^GetSG(n-i,m)]=1;for(i=2; i<=m-i; i++)vis[GetSG(n,i)^GetSG(n,m-i)]=1;for(i=0;; i++)if(vis[i]==0)return sg[n][m]=i;}int main(){int n,m;memset(sg,-1,sizeof(sg));while(~scanf("%d%d",&n,&m)){if(GetSG(n,m))printf("WIN\n");elseprintf("LOSE\n");}return 0;}
年轻是我们唯一拥有权利去编织梦想的时光