SG函数
过程:
补充
1.Mex运算:
设S表示一个非负整数集合.定义mex(S)为求出不属于集合S的最小非负整数运算,即:
mes(S)=min{x};
例如:S={0,1,2,4},那么mes(S)=3;
2.SG函数
在有向图游戏中,对于每个节点x,设从x出发共有k条有向边,分别到达节点y1,y2,····yk,定义SG(x)的后记节点y1,y2,····
yk的SG函数值构成的集合在执行mex运算的结果,即:
SG(x)=mex({SG(y1),SG(y2)····SG(yk)})
特别地,整个有向图游戏G的SG函数值被定义为有向图游戏起点s的SG函数值,即 SG(G)=SG(s).
3.有向图游戏的和
设G1,G2,····,Gm是m个有向图游戏.定义有向图游戏G,他的行动规则是任选某个有向图游戏Gi,并在Gi上行动一步.G被称为有向图游戏G1,G2,·····,Gm的和.
有向图游戏的和的SG函数值等于它包含的各个子游戏SG函数的异或和,即:
SG(G)=SG(G1)xorSG(G2)xor···xor SG(Gm)
代码:
#include<iostream>
#include<cstring>
#include<algorithm>
#include<set>
using namespace std;
const int N=110,M=10010;
int n,m;
int f[M],s[N];//s存储的是可供选择的集合,f存储的是所有可能出现过的情况的sg值
int sg(int x)
{
if(f[x]!=-1) return f[x];
//因为取石子数目的集合是已经确定了的,所以每个数的sg值也都是确定的,如果存储过了,直接返回即可
set<int> S;
//set代表的是有序集合(注:因为在函数内部定义,所以下一次递归中的S不与本次相同)
for(int i=0;i<m;i++)
{
int sum=s[i];
if(x>=sum) S.insert(sg(x-sum));
//先延伸到终点的sg值后,再从后往前排查出所有数的sg值
}
for(int i=0;;i++)
//循环完之后可以进行选出最小的没有出现的自然数的操作
if(!S.count(i))
return f[x]=i;
}
int main()
{
cin>>m;
for(int i=0;i<m;i++)
cin>>s[i];
cin>>n;
memset(f,-1,sizeof(f));//初始化f均为-1,方便在sg函数中查看x是否被记录过
int res=0;
for(int i=0;i<n;i++)
{
int x;
cin>>x;
res^=sg(x);
//观察异或值的变化,基本原理与Nim游戏相同
}
if(res) printf("Yes");
else printf("No");
return 0;
}
hxdtql!
sg(int x)的作用是把数量为x的石头堆的下一级的所有sg储存在set里面,最后选出未出现的最小的就是sg(x)的值。
or2
手写我爱惨了
补充关于为什么每堆石子的SG值可以构成NIM游戏:在NIM游戏中,玩家从n堆石子中任意一堆拿走任意个石子,可以拿完但不可以不拿—>对应n个有向图游戏顶点的SG值(设为SG1),玩家可以向任意一个方向走,如果是向SG2小于当前SG1值的状态走,就相当于拿了SG1 - SG2 这么多石子;如果向大于当前SG1值的状态SG2走,那么另一名玩家可以走回去(SG2 > SG1,由于mex函数,SG2的后继状态一定包含SG1,所以一定可以走回去),既然如此,向SG值较大的方向走就是无效步骤,所以可以不考虑。
这样看,就是一个纯粹的NIM游戏了
这里的set应该可以换成unordered_set的吧?
大佬,请问set存储一个局面所有sg的值的时候,再调用mex运算求有向图游戏起点的sg值的时候,怎么保证count查询的sg值起点能到局面的sg值? 就是如何保证查询的起点x 能到y1,y2…等的sg值呢
已解决,set每次都会更新
这里set定义在局部,每次都会更新
orz,非常详细
f数组在每次不要重新变为-1吗
可以看看sg值相同的原因
哈哈哈问完之后就知道了,是每次你选的都是一样的,这个被判断了以后再遇到,情况就都一模一样的了:)
tql!
爱你,优美的题解
tql谢谢你
我天!看懂了,蟹蟹大佬(借用图做笔记!!!
卧槽,你这个真的清晰简洁
牛逼
orz
nice
牛啊佬,绝了,我去看个视频讲解巩固一下
nice
f[]数组
讲解的真不错