博弈论
一、Nim游戏
1、思路
公平组合游戏：
（1）2名玩家交替行动
（2）再游戏进行的任意时刻，可以执行的合法行动与轮到谁无关
（3）不能行动的玩家判负
先手必胜状态：可以走到某一个先手必败状态
先手必败状态：走不到一个先手必败状态
对于每堆石子，a1,a2,a3……an为每堆石子个数
结论：
当 a1^a2^a3…………^an=0 则是先手必败状态
当 a1^a2^a3…………^an=x!=0 则是先手必胜状态
对于先手必胜状态的证明：
记x的二进制中表示最高位的1在第k位。
a1~an中必然存在一个ai，ai的第k位是1
那么ai^x<ai，
从ai中拿走ai-(ai^x)个石子
此时，ai剩下的石子数为ai-(ai-(ai^x))，数值上刚好等于ai^x
即通过拿走石子可以将ai变为ai^x
此时有 （2） a1^a2^a3^……ai^x……^an
而我们已知式子 a1^a2^a3…………^an=x
可以把(2)化简为x^x，即为0。
对于先手必败状态的证明：
我们已知 a1^a2^a3…………^an=0
证明此情况先手必败，即证明拿走任意石子数后值!=0
反证法：设拿走石子后，值=0
那么应该有 a1^a2^a3^……a'i……^an=0
由0^0=0，a1^a’1=0
那么ai^a'i也应该等于0，此时应该有ai=a'i
也就是不拿石子，与题意相违背，所以不成立。
2、代码模板：
#include<iostream>
using namespace std;
int main()
{
int n;
scanf("%d",&n);
int res=0;
while(n--)
{
int x;
scanf("%d",&x);
res^=x;//对所有的石子数进行异或操作
}
if(res)
puts("Yes");
else
puts("No");
}
二、集合—Nim游戏
1、思路
给定的定义：
（1）Mex运算：
设S表示一个非负数集合，定义Mex(S)为求出不属于集合S的最小非负整数的运算。
Mex(S)=min{x};
例如:S={0,1,2,4},那么Mex(S)=3;
例如:S={0,1,2,4},那么Mex(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）有向图游戏的和
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)^SG(G2)^···^SG(Gm)
有向图游戏的和的SG函数值等于它包含的各个子游戏SG函数的异或和,即:
SG(G)=SG(G1)^SG(G2)^···^SG(Gm)
投递东软集团等公司10个岗位
查看8道真题和解析