bzoj 1874: [BeiJing2009 WinterCamp]取石子游戏【博弈论】

先预处理出来sg值,然后先手必败状态就是sg[a[i]]的xor和为0(nim)

如果xor和不为0,那么一定有办法通过一步让xor和为0,具体就是选一个最大的sg[a[i]],把它去成其他sg值的xor和,这样后手的xor和就是0了

当然并不一定要取最大的,只要sg[a[i]]>(ans^sg[a[i]])即可,从小到大枚举,然后判一下是否能取这么多即可

#include<iostream>
#include<cstdio>
using namespace std;
const int N=1005;
int n,m,a[N],b[N],sg[N],v[N],ti,ans;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
scanf("%d",&m);
for(int i=1;i<=m;i++)
scanf("%d",&b[i]);
for(int i=1;i<=1000;i++)
{
ti++;
for(int j=1;j<=m;j++)
if(i-b[j]>=0)
v[sg[i-b[j]]]=ti;
for(int j=0;j<=1000;j++)
if(v[j]!=ti)
{
sg[i]=j;
break;
}
}
for(int i=1;i<=n;i++)
ans^=sg[a[i]];
if(!ans)
puts("NO");
else
{
puts("YES");
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(sg[a[i]-b[j]]==(ans^sg[a[i]]))
{
printf("%d %d\n",i,b[j]);
return 0;
}
}
return 0;
}
上一篇:Long类型参数传到前端精度丢失的解决方案


下一篇:BZOJ 1874: [BeiJing2009 WinterCamp]取石子游戏(SG函数)