acwing 219 剪纸游戏

发布时间 2023-09-14 23:17:40作者: 最爱丁珰

这一道题就是显然的multi-SG题目了(只是没有明显的后继节点,只能分解节点罢了)

这里无论双方怎么决策,决策图都不可能出现1x某某的网格(原因见蓝书),所以我们在程序中就不要考虑SG[1][某某]

最后的不能分解的节点就是2x2,2x3,3x3(注意不要涉及1x某某哦),我们把这三个节点赋成0即可

然后对每一个节点枚举从哪里剪开(注意别枚举1x某某的决策,因为不会出现),然后按照multi-SG进行决策就行了

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=210;
int sg[N][N];
bool flag[N<<1];
int main()
{
	for(int i=2;i<=200;i++)
	for(int j=i;j<=200;j++)
	if((i==2&&(j==2||j==3))||(i==j&&j==3)) continue;
	else 
	{
		memset(flag,0,sizeof(flag));
		for(int k=2;k<j-1;k++) 
		flag[sg[min(k,i)][max(k,i)]^sg[min(j-k,i)][max(j-k,i)]]=1;
		for(int k=2;k<i-1;k++) 
		flag[sg[min(k,j)][max(k,j)]^sg[min(i-k,j)][max(i-k,j)]]=1;
		for(int k=0;k<=410;k++)
		if(!flag[k])
		{
			sg[i][j]=k;
			break;
		}
	}
	int n,m;
	while(scanf("%d%d",&n,&m)==2)
	if(sg[min(n,m)][max(n,m)]==0) printf("LOSE\n");
	else printf("WIN\n");
	return 0;
 }