公平组合游戏ICG

定义

若一个游戏满足：
+ 由两名玩家交替行动
+ 在游戏进程的任意时刻，可以执行的合法行动与轮到哪名玩家无关
+ 不能行动的玩家判负

则称该游戏为一个公平组合游戏。

Nim博弈属于公平组合游戏，但是城建的棋类游戏，比如围棋，就不是公平组合游戏。因为围棋交战双方分别只能落黑子和白子。胜负判定也比较复杂，不满足条件2和条件3。

例题举例1：AcWing 891.Nim游戏

给定n堆石子，两位玩家轮流操作，每次操作可以从任意一堆石子中拿走任意数量的石子（可以拿完，但不能不拿），最后无法进行操作的人视为失败。
问如果两人都采用最优策略，先手是否必胜。

例如：有两堆石子，第一堆有2个，第二堆有3个，先手必胜。

操作步骤：
1. 先手从第二堆拿走1个，此时第一堆和第二堆数目相同
2. 无论后手怎么拿，先手都在另外一堆石子中取走相同数量的石子即可。

解题思路

必胜状态和必败状态
在解决这个问题之前，先来了解两个名词：
必胜状态，先手进行某一个操作，留给后手是一个必败状态时，对于先手来说是一个必胜状态。即先手可以走到某一个必败状态。
必败状态，先手无论如何操作，留给后手都是一个必胜状态时，对于先手来说是一个必败状态。即先手走不到任何一个必败状态。

模板代码

#include<iostream>
using namespace std;
int main()
{
    int n;
    scanf("%d",&n);
    int res=0,x;   //为什么res可以初始化为0？
    while(n--)     //因为这是异或操作，0异或一个数，等于这个数本身
    {              //因此res可以初始化为0
        scanf("%d",&x);
        res^=x;
    }
    if(res) puts("Yes");
    else puts("No");
    return 0;
}

例题举例2：AcWing 892.台阶-Nim游戏

现在，有一个 n 级台阶的楼梯，每级台阶上都有若干个石子，其中第 i 级台阶上有 a~i~ 个石子(i≥1)。
两位玩家轮流操作，每次操作可以从任意一级台阶上拿若干个石子放到下一级台阶中（不能不拿）。
已经拿到地面上的石子不能再拿，最后无法进行操作的人视为失败。
问如果两人都采用最优策略，先手是否必胜。

解题思路

此时我们需要将奇数台阶看做一个经典的Nim游戏，如果先手时奇数台阶上的值的异或值为0，则先手必败，反之必胜
证明：
先手时，如果奇数台阶异或非0，根据经典Nim游戏，先手总有一种方式使奇数台阶异或为0，于是先手留了奇数台阶异或为0的状态给后手
于是轮到后手：
+ ①当后手移动偶数台阶上的石子时，先手只需将对手移动的石子继续移到下一个台阶，这样奇数台阶的石子相当于没变，于是留给后手的又是奇数台阶异或为0的状态
+ ②当后手移动奇数台阶上的石子时，留给先手的奇数台阶异或非0，根据经典Nim游戏，先手总能找出一种方案使奇数台阶异或为0

因此无论后手如何移动，先手总能通过操作把奇数异或为0的情况留给后手，当奇数台阶全为0时，只留下偶数台阶上有石子。
（核心就是：先手总是把奇数台阶异或为0的状态留给对面，即总是将必败态交给对面）

因为偶数台阶上的石子要想移动到地面，必然需要经过偶数次移动，又因为奇数台阶全0的情况是留给后手的，因此先手总是可以将石子移动到地面，当将最后一个（堆）石子移动到地面时，后手无法操作，即后手失败。

因此如果先手时奇数台阶上的值的异或值为非0，则先手必胜，反之必败！

模板代码

#include<iostream>
using namespace std;
int main()
{
    int n,x,res=0;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&x);
        if(i&1) res^=x;
    }
    if(res) puts("Yes");
    else puts("No");
    return 0;
}

例题举例3：AcWing 893.集合-Nim游戏

给定 n 堆石子以及一个由 k 个不同正整数构成的数字集合 S。

现在有两位玩家轮流操作，每次操作可以从任意一堆石子中拿取石子，每次拿取的石子数量必须包含于集合 S，最后无法进行操作的人视为失败。

问如果两人都采用最优策略，先手是否必胜。

解题思路

性质1修改成：$SG(k)$可以走到$0−k−1$的任何一个状态

模板代码

#include<iostream>
#include<unordered_set>
#include<cstring>
using namespace std;
const int N=110,M=10010;
int s[N],f[M];
int k,n,h;
int sg(int x)  
{
    if(f[x]!=-1) return f[x];     //记忆化搜索，只要算过了，就不重复算了
    unordered_set<int> c;   //用一个哈希表存储由起点产生的每个局面
    for(int i=0;i<k;i++)                        //递归的
        if(x-s[i]>=0)   //>=,不是>
            c.insert(sg(x-s[i]));
    for(int i=0;;i++)
        if(!c.count(i))            //计算sg(起点)
            return f[x]=i;
}
int main()
{
    memset(f,-1,sizeof(f));   //初始化为-1
    scanf("%d",&k);
    for(int i=0;i<k;i++) scanf("%d",&s[i]);
    scanf("%d",&n);
    int res=0;
    while(n--)
    {
        scanf("%d",&h);
        res^=sg(h);
    }
    if(res) puts("Yes");
    else puts("No");
    return 0;
}

例题举例4：AcWing 894.拆分-Nim游戏

给定 n 堆石子，两位玩家轮流操作，每次操作可以取走其中的一堆石子，然后放入两堆规模更小的石子（新堆规模可以为 0，且两个新堆的石子总数可以大于取走的那堆石子数），最后无法进行操作的人视为失败。

问如果两人都采用最优策略，先手是否必胜。

解题思路

总数在操作过程中可能会变多，但是单堆的最大值会变小，所以这个过程是一定可以停止的。

模板代码

#include<iostream>
#include<cstring>
#include<unordered_set>
using namespace std;
const int N=110;
int n,a;
int s[N],f[N];
int sg(int x)
{
    unordered_set<int> c;
    if(f[x]!=-1) return f[x];
    for(int i=0;i<x;i++)          //拆分成两个局面
        for(int j=0;j<=i;j++)     //规定一个大一个小
            c.insert(sg(i)^sg(j));    //多个独立局面的SG值，等于这些局面SG值得异或和
    for(int i=0;;i++)//mex操作
        if(!c.count(i))
            return f[x]=i; //当递归回第一层时，返回SG(x1)的值，即要用来异或的值
}
int main()
{
    scanf("%d",&n);
    memset(f,-1,sizeof(f));
    int res=0;
    while(n--)
    {
        scanf("%d",&a);
        res^=sg(a);
    }
    if(res) puts("Yes");
    else puts("No");
    return 0;
}