公平组合游戏ICG(蓝书上有第p183)
Mex运算
设S是一个非负整数集合,而Mex(S)得出的则是不在S这个集合当中的最小整数。
例子S={0,1,4,5},Mex(S)=2。
SG函数
就是说在有向图中对于其中每个节点X有K条边,则SG(X)=Mex({SG(y1),SG(y2)···,SG(yk)})
也就是说求SG(X)就是它的所有后续节点的集合来做Mex得出的答案。
集合-Nim游戏
那题目又不是一个有向图该如何使用SG函数?
这个在纸上画一下每种情况模拟就知道了,就是Y总视频里画的那个样子。
代码
#include<set>
#include<cstdio>
#include<cstring>
using namespace std;
int n,m,i,j,a[101],x,s,f[10001];
int sg(int x)
{
if(f[x]!=-1)return f[x];
set<int>b;int i,y;
for(i=1;i<=n;++i)
{
y=a[i];
if(x>=y)b.insert(sg(x-y));
}
for(i=0;;++i)if(!b.count(i))return f[x]=i;
}
int main()
{
memset(f,-1,sizeof f);
scanf("%d",&n);
for(i=1;i<=n;++i)scanf("%d",a+i);
scanf("%d",&m);
for(i=0;i<m;++i)scanf("%d",&x),s^=sg(x);
printf("%s",s?"Yes":"No");
return 0;
}