小记:这题是对sg函数的初步理解。
对于sg函数只要 g[x] == 0,则此时为必败态。
x作为后继,我们就要对所有的后继进行标记,然后mex之。
因为每次只能切一刀,所以切完之后,会有两块方格,而对每一块方格进行游戏又会有一个sg函数值,
所以根据sg函数的性质,它这一刀所代表的后继,即为这两块方格的sg函数值的异或值(即为x)。
然后根据后继mex之。
mex的到的值即为此态的sg函数值,返回即可。
根据sg函数值判断必败必胜态。
代码:
#include <iostream> #include <cstdio> #include <cstring> using namespace std; #define MAXN 210 int dp[MAXN][MAXN]; int sg(int n,int m){ if(dp[n][m] != -1)return dp[n][m]; bool g[MAXN]={0}; for(int i = 2; i <= n/2; i++){ g[sg(i,m) ^ sg(n - i,m)] = 1; } for(int j = 2; j <= m/2; j++){ g[sg(n,j) ^ sg(n,m - j)] = 1; } for(int i = 0; ; i++){ if(g[i]==0)return dp[n][m] = i; } } int main() { memset(dp,-1,sizeof(dp)); int n,m; while(~scanf("%d%d",&n,&m)){ if(sg(n,m)>0){ printf("WIN\n"); } else printf("LOSE\n"); } return 0; }