文章目录
- 前言
- 一、Nim游戏
- 1.题目描述
- 输入格式
- 输出格式
- 数据范围
- 输入样例：
- 输出样例：
- 2.算法
- 二、台阶-Nim游戏
- 1.题目描述
- 输入格式
- 输出格式
- 数据范围
- 输入样例：
- 输出样例：
- 2.算法
- 三、集合-Nim游戏
- 1.题目描述
- 输入格式
- 输出格式
- 数据范围
- 输入样例：
- 输出样例：
- 2.算法
- 四、拆分-Nim游戏
- 1.题目描述
- 输入格式
- 输出格式
- 数据范围
- 输入样例：
- 输出样例：
- 2.算法
前言
博弈论又被称为对策论(Game Theory)，既是现代数学的一个新分支，也是运筹学的一个重要学科。博弈论主要研究公式化了的激励结构间的相互作用，是研究具有斗争或竞争性质现象的数学理论和方法。博弈论考虑游戏中的个体的预测行为和实际行为，并研究它们的优化策略。
一、Nim游戏
1.题目描述
给定 n 堆石子，两位玩家轮流操作，每次操作可以从任意一堆石子中拿走任意数量的石子（可以拿完，但不能不拿），最后无法进行操作的人视为失败。
问如果两人都采用最优策略，先手是否必胜。
输入格式
第一行包含整数 n。
第二行包含 n 个数字，其中第 i 个数字表示第 i 堆石子的数量。
输出格式
如果先手方必胜，则输出 Yes。
否则，输出 No。
数据范围
1≤n≤105,
1≤每堆石子数≤109
输入样例：
2
2 3
输出样例：
Yes
2.算法
- 算法结论：全部项异或，如果异或为0（a1^a2……an = 0）则先手必败，异或为1(（a1^a2……an = x）)则先手必胜
- 如何证明？？？
- 证明异或非0进行一步操作便可以使得异或为0：x的二进制表示中最高一位在第k位，则a1~an中必然有一个数ai的第k位是1，从ai对拿去（ai - (ai - x)）后该堆为ai^x，则此时所有堆异或等于0
- 证明异或为0不论怎么操作都会让异或非0：可以用反证法，如果a1^a2…ai…an = 0且a1^a2…ai拿去后…an = 0，则两式异或得ai^ai拿去后 = 0，则拿去前后不变，不符合逻辑
- 最后还要知道全为0时异或，这种情况必然是先手必败
- 所有这场游戏两人都实现最优策略则：异或为0（a1^a2……an = 0）则先手必败，异或为1(（a1^a2……an = x）)则先手必胜
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
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");
return 0;
}
二、台阶-Nim游戏
1.题目描述
现在，有一个 n 级台阶的楼梯，每级台阶上都有若干个石子，其中第 i 级台阶上有 ai 个石子(i≥1)。
两位玩家轮流操作，每次操作可以从任意一级台阶上拿若干个石子放到下一级台阶中（不能不拿）。
已经拿到地面上的石子不能再拿，最后无法进行操作的人视为失败。
问如果两人都采用最优策略，先手是否必胜。
输入格式
第一行包含整数 n。
第二行包含 n 个整数，其中第 i 个整数表示第 i 级台阶上的石子数 ai。
输出格式
如果先手方必胜，则输出 Yes。
否则，输出 No。
数据范围
1≤n≤105,
1≤ai≤109
输入样例：
3
2 1 3
输出样例：
Yes
2.算法
- 本题思路和上一题基本一致，但我们要分两种情况
- 当对手拿偶数台阶时，我们可以通过拿取对手从偶数台阶下方到奇数台阶的部分，把它再从奇数台阶下放到下一级偶数台阶，这样保证了奇数台阶始终不变
- 当对手拿奇数台阶时，情况和我们上一题一摸一样，所以奇数台阶异或为0则先手必败，异或为1则先手必胜
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int main()
{
int n;
scanf("%d", &n);
int res = 0;
for (int i = 1; i <= n; i ++ )
{
int x;
scanf("%d", &x);
if (i & 1) res ^= x; //判断奇偶再异或奇项
}
if (res) puts("Yes");
else puts("No");
return 0;
}
三、集合-Nim游戏
1.题目描述
给定 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
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)
-
我们可以举一个例子：设取石子的集合为{2，5}，且仅有一堆石子，石子数为10（终点SG值为0）
-
当仅有一堆石子是，如果SG（10）！= 0，则必胜，等于0则必败。原因：当SG不等于0时，下一个连接点必有一个是0；当SG等于0时，下一个连接点都是非0。所以先手只要不是0，就可以一直给后手0的情况，最终达到终点0，先手胜利。
-
当有n堆石子时，把每一堆石子的SG取出来，发现这就是Nim游戏！！！思路便和第一道例题一摸一样！！！（因为也是全为0的时候先手必败）
-
所以所有堆石子的SG异或值，不等于0先手必胜；等于0先手必败
#include<iostream>
#include<cstring>
#include<algorithm>
#include<set>
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<int> S; //因为在函数内部定义,所以下一次递归中的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++)//循环完之后可以进行选出最小的没有出现的自然数的操作
if(!S.count(i))
return f[x]=i;
}
int main()
{
cin>>m;
for(int i=0;i<m;i++)
cin>>s[i];
cin>>n;
memset(f,-1,sizeof(f));//初始化f均为-1,方便在sg函数中查看x是否被记录过
int res=0;
for(int i=0;i<n;i++)
{
int x;
cin>>x;
res^=sg(x);
//观察异或值的变化,基本原理与Nim游戏相同
}
if(res) printf("Yes");
else printf("No");
return 0;
}
四、拆分-Nim游戏
1.题目描述
给定 n 堆石子，两位玩家轮流操作，每次操作可以取走其中的一堆石子，然后放入两堆规模更小的石子（新堆规模可以为 0，且两个新堆的石子总数可以大于取走的那堆石子数），最后无法进行操作的人视为失败。
问如果两人都采用最优策略，先手是否必胜。
输入格式
第一行包含整数 n。
第二行包含 n 个整数，其中第 i 个整数表示第 i 堆石子的数量 ai。
输出格式
如果先手方必胜，则输出 Yes。
否则，输出 No。
数据范围
1≤n,ai≤100
输入样例：
2
2 3
输出样例：
Yes
2.算法
- 相比于集合-Nim，这里的每一堆可以变成小于原来那堆的任意大小的两堆
- 即a[i]可以拆分成(b[i],b[j]),为了避免重复规定b[i]>=b[j],即：a[i]>b[i]>=b[j]
- 相当于一个局面拆分成了两个局面，由SG函数理论，多个独立局面的SG值，等于这些局面SG值的异或和。因此需要存储的状态就是sg(b[i])^sg(b[j])（与集合-Nim的唯一区别）
#include <iostream>
#include <cstring>
#include <unordered_set>
using namespace std;
const int N = 110;
int n;
int f[N];
int sg(int x)
{
if(f[x] != -1) return f[x];
unordered_set<int> S;
for(int i = 0 ; i < x ; i++)
for(int j = 0 ; j <= i ; j++)//规定j不大于i，避免重复
S.insert(sg(i) ^ sg(j));//相当于一个局面拆分成了两个局面，由SG函数理论，多个独立局面的SG值，等于这些局面SG值的异或和
for(int i = 0 ; ; i++)
if(!S.count(i))
return f[x] = i;
}
int main()
{
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;
}
