小记:这题是对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;
}
标签:函数,int,2311,Game,Cutting,MAXN,后继,sg,mex From: https://blog.51cto.com/u_16192154/6767443