自动搬运

查看原文

来自洛谷，原作者为

	fish_love_cat 「要毁灭世界，根本不需要邪恶。起初，那些都是不会被任何人怪罪的小小愿望。而那样的愿望却如此轻易地，和末日相连在一起。」

搬运于2025-08-24 22:58:37，当前版本为作者最后更新于2024-05-21 22:45:59，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

前置芝士：SG 函数。

分讨写不出来，还是老老实实用 SG 函数做吧。

要两次判断，一次考虑剪长，一次考虑剪宽，剪完后递归求解子局面，结果异或后记录，对记录下来的求 $\operatorname{mex}$ 得出即可得出函数值。

注意不可以剪出一边为 $1$，不然对手直接能赢，所以循环边界条件要注意。

代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int sg[205][205];
int SG(int n,int m){
	if(sg[n][m]!=-1)return sg[n][m];
	int f[205]={};
	for(int i=2;i<=n-2;i++)f[SG(i,m)^SG(n-i,m)]=1;
	for(int i=2;i<=m-2;i++)f[SG(n,i)^SG(n,m-i)]=1;
  	//注意边界
	for(int i=0;i<=200;i++)
	if(!f[i])return sg[n][m]=i;
}
signed main(){
	memset(sg,-1,sizeof sg);
	int n,m;
	while(cin>>n>>m)
	puts(SG(n,m)?"WIN":"LOSE");
	return 0;
}
//最优解 = 打表
//:-(

瑞平：写分讨写出 $21$ 次提交，怒挂 $17$ 发，挤占大量评测姬资源，谴责。