P10501 Cutting Game 题解

SG函数模板题。

显然 $1\times 1$ 的纸条是先手必败态，$1\times x,x\times 1$ 是先手必胜态。

可以列出 $sg$ 函数的定义： $$ \begin{cases} sg(1,1)=0\ sg(n,m)=\mathrm{mex}({sg(i,m) \oplus sg(n-i,m)|2\le i\le n-2}\ \texttt{ }\cup{sg(n,j) \oplus sg(n,m-j)|2\le j\le m-2}) \end{cases} $$ 为什么 $i,j$ 的边界一定要保证两边都 $>1$ 呢，不难发现每一步都会尽量避免直接剪出 $1\times x$ 或 $x\times 1$ 的纸条，因为这样会使对手直接获胜。

记忆化搜索即可。

#include<bits/stdc++.h>
#define FL(i,a,b) for(int i=(a);i<=(b);i++)
#define FR(i,a,b) for(int i=(a);i>=(b);i--)
#define ll long long
using namespace std;
const int MAXN = 2e2 + 10;
int W,H;
int sg[MAXN][MAXN];
int SG(int n,int m){
	if(sg[n][m]!=-1) return sg[n][m];
	unordered_map<int,bool>vis;
	vis.clear(); 
	FL(i,2,n-2) vis[SG(i,m)^SG(n-i,m)]=1; 
	FL(i,2,m-2) vis[SG(n,i)^SG(n,m-i)]=1;
	FL(i,0,400) if(!vis[i]) return sg[n][m]=i;
}
int main(){
	memset(sg,-1,sizeof(sg));
	while(~scanf("%d%d",&W,&H))
		puts(SG(W,H)?"WIN":"LOSE");
}