博弈论(Nim+sg)

Nim游戏

给定 n 堆石子，两位玩家轮流操作，每次操作可以从任意一堆石子中拿走任意数量的石子（可以拿完，但不能不拿），最后无法进行操作的人视为失败。

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

输入格式

第一行包含整数 n。

第二行包含 n 个数字，其中第 i 个数字表示第 i 堆石子的数量。

输出格式

如果先手方必胜，则输出 Yes。

否则，输出 No。

数据范围

1≤n≤10^5
1≤每堆石子数≤10^9

输入样例：

2
2 3

输出样例：

Yes

必胜状态：先手进行某一个操作，留给后手的是一个必败状态时，对于先手来说是一个必胜状态，即先手可以走到某一个必败状态 

必败状态： 先手无论如何操作，留给后手都是一个必胜状态时，对于先手来说是一个必败状态，即先手走不到任意一个必败状态

结论：a1^a2^a3^a4^...an!=0 先手必胜

          a1^a2^a3^a4^...an==0先手必败

  异或运算三个性质：

①任何数和 0做异或运算，结果仍然是原来的数
 ②任何数和其自身做异或运算，结果是 0
 ③异或运算满足交换律和结合律

#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
    int res=0;
    int n;cin>>n;
    while(n--)
    {
        int x;cin>>x;
        res^=x;
    }
    if(res!=0) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    return 0;
}

 台阶-Nim游戏

现在，有一个 n 级台阶的楼梯，每级台阶上都有若干个石子，其中第 i级台阶上有 ai 个石子(i≥1)。

两位玩家轮流操作，每次操作可以从任意一级台阶上拿若干个石子放到下一级台阶中（不能不拿）。

已经拿到地面上的石子不能再拿，最后无法进行操作的人视为失败。

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

输入格式

第一行包含整数 n。

第二行包含 n 个整数，其中第 i 个整数表示第 i 级台阶上的石子数 ai。

输出格式

如果先手方必胜，则输出 Yes。

否则，输出 No。

数据范围

1≤n≤10^5
1≤ai≤10^9

输入样例：

3
2 1 3

输出样例：

Yes

因为第一阶拿到地面要拿一次，第二阶那两次，第三阶那三次…所以可以看成第二阶有两堆石子，第三阶有三堆....因为偶数阶石子为偶数堆，所以异或为0，奇数阶异或后就是原本石子数目，所以可以把原本所有奇数阶的石子进行异或，得到的  就是答案 （是把第i阶（等同于经典nim问题中的第i堆）的石子理解为有i堆，每一堆的数量都是原本第i阶的石子数；）

 偶数台阶需要拿偶数次才能到地面，就相当于是把偶数个相同数量的石子堆拿完的策略。正好可以转化成前面一道题的“偶数个石子堆异或在一起，并且这些石子数量相同”，结果必然是0，因此可以不考虑。

 最后的状态肯定是所有台阶上的石子都为0 异或结果为0 那么就先手想办法让台阶上的石子异或结果为0 留给后手 让后手一直处于0太 必输的状态

那么去思考 这些台阶上的所有数异或都可以么

当后手改变了偶数的石子 其实相当于没有改变 那先手完全可以 后手在偶数石子中拿了多少 在它的下一层奇数层中在拿出来多少 运往下一层偶数层 使得奇数层数不改变 

所有改变偶数就对结果没有任影响 故也可以想到偶数台阶的石子不起作用

奇数台阶的石子起到作用-->就转换到经典Nim游戏

#include<iostream>
using namespace std;
int main()
{
    int n;cin>>n;
    int res=0;
    //只处理奇数个台阶之间相互异或
    for(int i=1;i<=n;i++)
    {
        int x;cin>>x;
        if(i%2!=0) res^=x;
    }
    if(res) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    return 0;
}

 集合-Nim游戏

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

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

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

输入格式

第一行包含整数 k，表示数字集合 S 中数字的个数。

第二行包含 k 个整数，其中第 i 个整数表示数字集合 S 中的第 i 个数 si。

第三行包含整数 n。

第四行包含 n 个整数，其中第 i 个整数表示第 i 堆石子的数量 hi。

输出格式

如果先手方必胜，则输出 Yes。

否则，输出 No。

数据范围

1≤n,k≤100
1≤si,hi≤10000

输入样例：

2
2 5
3
2 4 7

输出样例：

Yes

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)