转载请注明出处,谢谢http://blog.csdn.net/ACM_cxlove?viewmode=contents
by---cxlove
题目:给出一个N*M的纸片,每一次可以把一部分剪成两部分,谁剪出1*1的就赢了。
http://poj.org/problem?id=2311
对于任何一个人,都不会先剪出1*n或者n*1,应该这样就必败了。
那我们考虑一个状态的后继中,最小的边也是2,这样就可以避免之前的问题,也不需要考虑类似ANTI-SG。
一旦出现2*2,2*3,3*2,这些都成了终止状态,不论怎么剪都会出现1*n,或者n*1
还是考察SG函数
#include<iostream>
#include<cstdio>
#include<ctime>
#include<cstring>
#include<cstdlib>
#include<vector>
#define C 240
#define TIME 10
#define LL long long
using namespace std;
int sg[205][205];
int get_sg(int n,int m){
if(sg[n][m]!=-1)
return sg[n][m];
int vis[1005];
memset(vis,0,sizeof(vis));
for(int i=2;i<=n-i;i++)
vis[get_sg(i,m)^get_sg(n-i,m)]=1;
for(int i=2;i<=m-i;i++)
vis[get_sg(n,i)^get_sg(n,m-i)]=1;
for(int 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)!=EOF)
if(get_sg(n,m))
printf("WIN\n");
else
printf("LOSE\n");
return 0;
}
分享到:
相关推荐
北大POJ1027-The Same Game 解题报告+AC代码
北大POJ1753-Flip Game 解题报告+AC代码
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
poj 3901 The Computer Game.md
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
POJ1753 Flip Game题目完整代码及报告
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
poj分类poj分类poj分类poj分类
北大POJ1159-Palindrome 解题报告+AC代码
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友
POJ1503解答 POJ1503解答,正确答案(已通过POJ)
poj 百练 题目分类 poj 百练 题目分类
POJ1083的代码,POJ1083的代码,POJ1083的代码
POJ1048,加强版的约瑟夫问题 难度中等
北大POJ2002-Squares 解题报告+AC代码
poj 1001答案