题意：
给一个w*h的矩形，两人轮流只能沿格子的边缘横剪或竖剪，最先剪出1*1的格子的人获胜，问先手必胜还是必败。
分析：
此题要求对grundy值有理解。一个全局状态的grundy值是对游戏中某个状态的有效的描述，grundy值描述了当前状态的所有后继状态，比如n堆石子的nim游戏的grundy值是a1^a2^...an。
代码：
//poj 2311 //sep9 #include#include using namespace std; const int maxN=256; int dp[256][256]; int grundy(int w,int h) { if(dp[w][h]!=-1) return dp[w][h]; set s; for(int i=2;w-i>=2;++i) s.insert(grundy(i,h)^grundy(w-i,h)); for(int i=2;h-i>=2;++i) s.insert(grundy(w,i)^grundy(w,h-i)); int res=0; while(s.count(res)) res++; return dp[w][h]=res; } int main() { memset(dp,-1,sizeof(dp)); int w,h; while(scanf("%d%d",&w,&h)==2){ if(grundy(w,h)!=0) puts("WIN"); else puts("LOSE"); } return 0; }