博弈论算法的实现2

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
#include
#include
#include

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 S;
//set代表的是有序集合(注:因为在函数内部定义,所以下一次递归中的S不与本次相同)
for(int i=0;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;
1
2
3
4

}

int main()
{
cin>>m;
for(int i=0;i cin>>s[i];

cin>>n;
memset(f,-1,sizeof(f));//初始化f均为-1,方便在sg函数中查看x是否被记录过

int res=0;
for(int i=0;i>x;
    res^=sg(x);
    //观察异或值的变化,基本原理与Nim游戏相同
}

if(res) printf("Yes");
else printf("No");

return 0;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

}
往年题解(非常lj,可直接跳过)

将每一个h[i]h[i]的所有方案看做是一张有向图，例

若S=[2,5],h=10S=[2,5],h=10,则有如下展开形式：

mex()：mex()：设集合S是一个非负整数集合，定义mex(S)mex(S)为求出不属于S的最小非负整数的运算，即：mes(S)=min[x],其中xmes(S)=min[x],其中x属于自然数，且xx不属于SS（用人话说就是不存在SS集合中的数中，最小的那个数）

SG()：SG()：在有向图中，对于每个节点xx，设从xx出发共有kk条有向边，分别达到节点y1，y2……yky1，y2……yk，定义SG(x)SG(x)为xx的后继节点的SGSG值构成的集合执行mex()mex()运算后的值
即：SG(x)=mex(SG(y1),SG(y2)…SG(yk))SG(x)=mex(SG(y1),SG(y2)…SG(yk))；（用人话说就是比后继节点的SGSG都小的值）
特别的整个图GG的SGSG值被定义为起点ss的SGSG值，即SG(G)=SG(s)SG(G)=SG(s)
上图标红的值就是每一个节点的SGSG值
性质：1.SG(i)=k，则i最大能到达的点的SG值为k−1。1.SG(i)=k，则i最大能到达的点的SG值为k−1。
2.非0可以走向0 2.非0可以走向0
3.0只能走向非0 3.0只能走向非0

定理：
对于一个图GG，如果SG(G)!=0SG(G)!=0，则先手必胜，反之必败

证明：
若SG(G)=!0SG(G)=!0，
1.根据性质2，先手必可以走向0，
2.因此留给后手的是0，根据性质3，后手只能走向非0
3.以此类推，后手始终无法走向0，后手永远处于非0，当先手到达终点的0时，先手获胜
（由此我们可以知道，有些事是命中注定的~~~）
反之同理，必败

定理：
对于n个图，如果SG(G1)SG(G1) ^ SG(G2)SG(G2) ^ … SG(Gn)!=0SG(Gn)!=0 ,则先手必胜，反之必败

证明（类似与Nim游戏）：
①当SG(Gi)=0SG(Gi)=0 时 ， xor=0xor=0 ， 显然先手必败
（PS：结束状态必是状态①，但状态①不一定是结束状态）

②当xor=x!=0xor=x!=0 时，因为肯定存在一个SG(xi)SG(xi)^x 因此，必定可以从SG(xi)−>SG(xi)SG(xi)−>SG(xi)^xx ， 于是使得xor=0xor=0

③当xor=0xor=0时，当移动任何一个节点时，对应的SGSG值必然减小，可以证明：xor!=0xor!=0
下证：xor!=0xor!=0
假设:xor=0xor=0,则说明移动的那个节点的值并没有变化，即从SG(k)SG(k)变成了kk，但是这与SGSG函数的性质1相矛盾，因此不成立

证得：若先手面对的状态是xor!=0xor!=0,则先手方总能使xor=0xor=0，即使后手面对的永远是必败态直到结束状态①，因此先手必胜！
反之，必败！

C++ 代码
#include
#include
#include

using namespace std;

const int N = 110 , M = 10010;

int n , m;
int s[N] , f[M];

int sg(int x)
{
if(f[x] != -1) return f[x];//记忆化搜索，如果f[x]已经被计算过，则直接返回

// 因为这题中较大堆的拆分情况独立于较小堆，因此有别于894.拆分-Nim，这里的S必须开成局部变量
unordered_set S;//用一个哈希表来存每一个局面能到的所有情况，便于求mex

for(int i = 0 ; i < m ; i++)
    if(x >= s[i]) S.insert(sg(x - s[i]));//如果可以减去s[i]，则添加到S中

for(int i = 0 ; ; i++)//求mex()，即找到最小并不在原集合中的数
    if(!S.count(i)) return f[x] = i;
1
2
3
4
5
6
7
8

}

int main()
{
cin >> m;
for(int i = 0 ; i < m ; i++) cin >> s[i];

memset(f , -1 , sizeof f);

cin >> n;
int res = 0;
while(n--)
{
    int x;
    cin >> x;
    res ^= sg(x);
}


if(res) puts("Yes");
else puts("No");
return 0;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

}