SG函数介绍（Nim or not Nim?、A New Stone Game、Georgia and Bob（阶梯博弈））

---

一、引入

组合博弈游戏

1.有向图游戏的引入

以当前局面作为图中的一个节点，由当前局面可以到达的局面作为当前节点的后继节点，那么整体就可以形成一个图的结构，这样的一个公平组合游戏就形成了一个“有向图游戏”。

2.对有向图游戏的分析

在双方的交替操作下，相当于在这个有向图中交替移动棋子，若有一方无法移动则判定为失败。
根据我们在尼姆游戏中的了解，可以知道，在双方均采取最优策略的前提下，每个局面所对应的结果其实是确定的。
所以我们将这些点划分为必败点和必胜点，存在关系如下：

1、所有终结点是 必败点 P 。
2、从任何必胜点N 操作，至少有一种方式可以进入必败点 P。
3、无论如何操作，必败点P 都只能进入 必胜点 N。

---

二、SG函数与SG定理

1.mex操作的引入

mex（S）表示最小的不属于这个集合的非负整数。

也就是在非负整数中，先除去S，然后在剩余的非负整数中取最小值。例如mex{0,1,2,4}=3、mex{2,3,5}=0、mex{}=0。

2.SG函数

我们先将局面转化为有向图游戏，我们以最终的必败态的SG值为0，每个点的SG值等于以其后继节点的SG值为S，求mex{S}作为当前节点的SG值。

此时存在关系如下：
1.最终状态SG值为0；
2.SG值为0的点为必败态，它的后继节点中不存在SG值为0的点；
3.SG值非0的点为必胜态，它的后继节点中存在一点SG值为0.

至于如何求SG函数，我们可以使用记忆化搜索。

mex运算的实现，可以借助set，集合内存入各种后继局面的SG值，再从0开始枚举，直至发现有一点没有出现在后续节点的SG值集合中，该值就是当前点的SG值。

int f[M],s[N];//s存储的是可供选择的集合,f存储的是所有可能出现过的情况的sg值
int sg(int x){
    if(f[x]!=-1) return f[x];set<int> 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++)//mex运算if(!S.count(i))return f[x]=i;
}

3.SG定理

之前考虑的其实都是一种简单情况，以取石子为例就是只在一堆上进行操作，而我们面临的情况事实上会更复杂，仍然以尼姆游戏为例，我们需要在多个堆中进行选择，然后再进行操作，我们此时又当如何确定局面的SG值呢？

SG定理：游戏和的(SG)函数等于各个子游戏的(SG)函数的异或和。

比如说当前有N堆石子，每堆石子有着对应的取法（可能相同，也可能不同），而当前局面的SG值也就是单独考虑每堆石子的SG值异或和的结果。
此时要求子游戏之间的独立性，不同子游戏之间不存在影响。

证明：

1.终止状态为异或和为0的状态

当最终每一堆石子都无法操作时，每一堆的SG值为0.

2.由异或和不为0的状态存在方法可以到异或和为0的状态

给出一个子游戏的SG值，意味着小于该值的非负整数都属于这一点的后继节点，那么就完全可以复刻之前尼姆游戏的证明.

3.由异或和为0的状态只能到达异或和不为0的状态

同样可以采用反证法来证明。

---

三、例题（掌握如何划分子游戏）

重点：
找到必败态跟必胜态，
满足条件：
1.必败态只会要么为最终情况，无法操作，要么操作后只能变为必胜态
2.必胜态存在策略可以变为必败态。

需要一些猜想！！！猜测必败态并证明

1.Nim or not Nim?（取或分割）

Nim or not Nim?

大意：与尼姆游戏的区别在于除了取石子，还可以选择将一堆石子分割为不为空的两堆石子

分析：
那么选出其中一堆来分析其SG值，比如有一堆石子，石子数为2，那么它所对应的后继状态有：（1）、（0），（1，1）
由条件可知，（0）的SG值为0，（1）的SG值为1，（1，1）有后继节点为（1），故（1，1）SG值为mex（1）为0，所以2的SG值为2.

了解了如何找SG值后，还要看这道题的特殊性，数据范围是$10^9$，即便是记忆化搜索也没办法用数组来存数据，所以可能需要找规律，当然了，我们找规律也是需要先推出一些数据，所以还是需要掌握如何求SG函数。

规律：

int sg(int x){
    int tmp=x%4;if(tmp==0)return x-1;else if(tmp==3)return x+1;else return x;
}

代码如下：

#include<iostream>
#include<cstring>
using namespace std;
int t,n;
int sg(int x){
    int tmp=x%4;if(tmp==0)return x-1;else if(tmp==3)return x+1;else return x;
}
int main(){
    cin>>t;while(t--){
    cin>>n;int ans=0;while(n--){
    int tmp;cin>>tmp;ans^=sg(tmp);}if(ans)cout<<"Alice"<<endl;else cout<<"Bob"<<endl;}
}

2.A New Stone Game

A New Stone Game

大意：有N堆石子，两人轮流进行操作，每一次为“操作者指定一堆石子：
1、先从中扔掉一部分（至少一颗，可以全部扔掉）；
2、若该堆仍有石子剩余，将该堆剩下的石子中的任意多颗任意移到任意一个未取完的堆中；
操作者无法完成操作时为负。

这道题与之前尼姆游戏的区别在于堆与堆之间不再相互独立
但分析还是类似的。

分析：
只有一堆时，先手必胜，可以直接取完；

有两堆时，若数目相等，先手拿取，要么拿完，则后手拿完另外一堆，先手失败；要么只拿一部分，再移动一部分，则后手可以进行模仿，使状态重新变为两堆相等的情况，先手最后还是要拿完其中一堆，故此时先手必败；
有两堆时，若不等，先手可以通过操作使之相等，从而后手面临必败局势，即先手必胜；

有了三堆时，先手可以将一堆处理，使另外两堆的数目相同，从而后手必败，即先手必胜；

有四堆时，四堆的后继状态要么仍为四堆，要么为三堆的必胜态，问题就是四堆先手如何能保证操作之后对方会把四堆的局面变为三堆，此时才能保证先手必胜；或者说先手怎样才会不得不把四堆变为三堆，使得先手必败；
当四堆中，存在两两相等时，先手的操作都可以被后手模拟，所以后手可以迫使先手把局面变为三堆，后手必胜，即先手必败；
除此以外，则先手必胜。

结论：
当n为偶，且可以分成n/2对两两相等的石子时，先手必败，否则先手必胜。

代码：

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int a[101];
int t,n;
int tmp;
int main(){
    while(cin>>n&&n){
    t=0;for(int i=0;i<n;i++){
    cin>>tmp;if(tmp){
    a[t++]=tmp;}}tmp=1;if(t%2==1)cout<<1<<endl;else {
    sort(a,a+t);for(int i=0;i<t-1;i++){
    if(a[i]==a[i+1]);else{
    tmp=0;}i++;}if(tmp==0)cout<<1<<endl;else cout<<0<<endl;}}
}

3.Georgia and Bob（阶梯博弈）

Georgia and Bob

大意：有一排格子，上面放置了n颗棋子，此时可进行的操作是把棋子向左移动，不过要求是棋子不能越过其左边的棋子或左边界，而且至少移动一个格子，每个格子只能容纳一枚棋子，两人交替操作，无法完成操作的人判定为输，其对手获得胜利。

分析：
其实可以把题意进行转化，刚看到这道题时我就联想到了刚刚学到阶梯博弈（y总课程里面的台阶-Nim游戏），每次操作都是把一个台阶上的石子移到下一个台阶上面去，至少移动一颗石子，石子到了地面就不可移动了。

此时可以把每颗棋子理解为台阶上的一级，棋子左侧的空格数也就是所对应的石子数，我们将棋子左移时，棋子所对应空格数减少，但其右侧棋子对应空格数增加，也就相当于把石子由当前台阶移到了下一个台阶，并且至少要移动一颗石子，而且最右侧的棋子移动后就相当于把石子移到了地面上，然后无法移动。

那么我们接下来的任务是分析如何解决阶梯博弈。

已知最终结束状态下，石子都将位于地面，也就是第0层，确定了最终状态后，我们的任务是找出必胜态跟必败态，满足条件：

1.必败态只会要么为最终情况，无法操作，要么操作后只能变为必胜态
2.必胜态存在策略可以变为必败态。

我们给出的答案是以奇数层石子数异或和为0作为必败态，非0作为必胜态。
相当于取出奇数层石子，做Nim游戏

1.当奇数层异或和为0时，要么为最终状态无法操作，要么进行操作，对偶数层奇数层的操作都会影响到奇数层上的石子个数，从而异或和结果必定会发生变化，也就是必定会变为必胜态；

2.当奇数层异或和非0时，参考Nim游戏中的证明，可以发现奇数层中必有一处可以通过移除石子使得奇数层异或和为0.

从而证明了必胜态必败态划分的合理性，那么我们就可以直接根据数据给出答案了。

代码：

注意，棋子的输入是没有顺序的，所以要进行排序后再进行对奇数层的异或。

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int t,n;
int a[1005];
int main(){
    cin>>t;while(t--){
    cin>>n;int ans=0;for(int i=1;i<=n;i++){
    cin>>a[i];}sort(a+1,a+n+1); for(int i=n;i>=1;i-=2){
    ans^=a[i]-a[i-1]-1;}if(ans)cout<<"Georgia will win"<<endl;else cout<<"Bob will win"<<endl;}
}