笔记---简单博弈论

🕗 发布于 2024-02-05 19:35 笔记算法 c++

公平组合游戏（ICG)
满足一下几个特征：
1.两名玩家交替行动。
2.在游戏进程的任意时刻，可以执行的合法行动与轮到哪名玩家无关。
3.不能行动的玩家判为失败
如果满足以上特征，那么就是一个公平组合游戏
另一种游戏叫做有向图游戏：
给定一个有向无环图，图中有一个唯一的起点，在起点上放有一枚棋子，两名玩家交替的把这枚棋子沿有向边进行移动，每次可以一定一步，最终无法移动的人判为失败

其中Nim游戏属于公平组合游戏

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

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

输入格式
第一行包含整数 $n$ 。
第二行包含 $n$ 个数字，其中第 $i$ 个数字表示第 $i$ 堆石子的数量。

输出格式
如果先手方必胜，则输出 Yes。否则，输出 No。

数据范围
$1≤n≤10^{5},1≤每堆石子数≤10^{9}$

输入样例：

2
2 3

输出样例：

Yes

先手必败状态是指：遇到了无法操作的情况，必然会输掉游戏。
先手必胜状态是指：当我们进行完了这一步操作之后，对手一定会陷入必败状态

结论：
如果n堆的数量为： $a_{1},a_{2},......,a_{n}$ ，那么：
使得 $a$ ₁ ^ $a$ ₂ ^… $a$ _n
如果结果为0，那么先手必败，如果不为0，那么先手必胜

证明过程详见AcWing算法基础课数学知识（四）1:11:00

代码：

#include<iostream>
using namespace std;

int main() {
int n; cin >> n;
int res = 0;

while (n--) {
int x; cin >> x;
res ^= x;
}
if (res)cout << "Yes";
else cout << "No";
return 0;
}

AcWing.892.台阶-Nim游戏
现在，有一个 $n$ 级台阶的楼梯，每级台阶上都有若干个石子，其中第 $i$ 级台阶上有 $a_{i}$ 个石子 $(i \geq 1)$ 。

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

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

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

输入格式
第一行包含整数 $n$ 。

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

输出格式
如果先手方必胜，则输出 Yes。
否则，输出 No。

数据范围
$1 \leq n \leq 105,$
$1 \leq ai \leq 109$

输入样例：

3
2 1 3

输出样例：

Yes

过于抽象，可以参照详情
详细过程：AcWing算法基础课习题课week7——18:00

在分析中，我们可得知保证最优解且先手必胜的前提为能够保证每次先手操作前的时候看到的都是奇数级台阶的石子数一定是有不同的，也就是在操作后对手看到的奇数级台阶的石子数都是相同的，这样可以保证先手必胜。

故我们只需要求出奇数级台阶的石子数量的抑或值，如果为0，那么就必败，如果不为0，那么必胜。

#include<iostream>
using namespace std;

int main() {
int n; int res = 0;

cin >> n;
for (int i = 1; i <= n; i++) {
int x; cin >> x;
if (i % 2)res ^= x;
}
if (res)puts("Yes");
else puts("No");

return 0;
}

—————————————————————————————————————————————————

接下来是SG函数

定义Mex运算，为找到一个集合里面最小的不存在的自然数

从一个局面可以通过不同的操作衍生出很多其他的局面，比如果从一堆石子中拿一个会走向一种局面，拿两个就是另一种局面，以此类推
对于SG函数，我们首先把终点状态的SG函数值定义为0
对于过程中任意一个局面，假如现在处于 $x$ 局面，且 $x$ 局面可以衍生出 $y_{1},y_{2},y_{3}...y_{k}$ 等局面，那么在 $x$ 局面的SG函数值就等于 SG( $x$ ) = Mex{ SG( $y$ ₁), SG( $y$ ₂), SG( $y$ ₃)…SG( $y$ _k) }。

比如说有一个局面指向且仅指向终点，那么他的SG函数值就只能为 $1$

最终对于一系列局面，起点的SG(x) = 0时，就是必败，SG(x) ≠ 0时，就是必胜

因为如果先手保证了当前SG值不为0，那么就是一定是可以到达0的，也就是说在双方绝顶聪明的前提下，一定能使得对手处于SG值等于0的局面，相反，如果先手的SG值等于0，那么就会让对手使得自己最终处于SG值等于0的局面

而且应用SG函数时，我们都会有多个图需要考虑，也就是说先手会从多个图里面选，如果所有的图都无法胜利，那么就导致最终的失败，但是如果有一个图可以胜利，那么就可以导致最终胜利

在多个图的情形下，只需要把多个图的SG的起点的值抑或起来就可以，如果最终得到结果是0，那么必败，如果不为0，那么必胜

AcWing.893.集合-Nim游戏
给定 $n$ 堆石子以及一个由 $k$ 个不同正整数构成的数字集合 $S$ 。

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

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

输入格式
第一行包含整数 $k$ ，表示数字集合 S 中数字的个数。
第二行包含 $k$ 个整数，其中第 $i$ 个整数表示数字集合 $S$ 中的第 $i$ 个数 $s$ _i。
第三行包含整数 $n$ 。
第四行包含 $n$ 个整数，其中第 $i$ 个整数表示第 $i$ 堆石子的数量 $h$ _i。

输出格式
如果先手方必胜，则输出 Yes。
否则，输出 No。

数据范围
$1≤n,k≤100,1≤s_{i},h_{i}≤10000$

输入样例：

输出样例：

Yes

根据上述的SG函数，我们可以把每一堆石子的局面的各种选法的集合看成一个图，那么在样例中我们就有三个图，分别求出这三个图的起点的SG函数值，将其抑或起来，就可以得到最终的结果

代码：

#include<iostream>
#include<cstring>
#include<unordered_set>
using namespace std;

const int N = 110;
const int M = 10010;

int n, m;
int s[N],f[M];//s：可以选的石子个数，f：SG函数值

int sg(int x) {
if (f[x] != -1)return f[x];//如果某个状态算过，那么就直接返回这个状态的值

unordered_set<int> S;//哈希表存所有可以到达的值
for (int i = 0; i < m; i++) {
int sum = s[i];
if (x >= sum)S.insert(sg(x - sum));//如果这堆石子的数量是大于拿走的数量的
//那么才能够存进去
}

for (int i = 0;; i++) {//找集合中不存在的最小的自然数
if (!S.count(i))//如果这个数在S中找不到
return f[x] = i;//那么就返回这个数作为其SG函数值
}
}

int main() {
cin >> m;
for (int i = 0; i < m; i++)cin >> s[i];//能够选的石子数

cin >> n;//石子堆数

memset(f, -1, sizeof f);//初始化f数组，以进行记忆化搜索

int res = 0;//存答案
for (int i = 0; i < n; i++) {
int x;//输入n堆石子各有多少个石子
cin >> x;
res ^= sg(x);//对每堆石子求其SG函数值，并进行抑或操作
}

if (res)puts("Yes");//如果最后非0，那么必胜
else puts("No");//否则必败

return 0;
}

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

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

输入格式
第一行包含整数 $n$ 。

第二行包含 $n$ 个整数，其中第 $i$ 个整数表示第 $i$ 堆石子的数量 $a_{i}$ 。

输出格式
如果先手方必胜，则输出 Yes。
否则，输出 No。

数据范围
$1≤n,a_{i}≤100$

输入样例：

2
2 3

输出样例：

Yes

可以将n堆石子看作n个局面（集合），对于每个局面求SG值之后把他们抑或起来求结果即可

对于每个局面，我们只需要找到其所有能到的值，然后再去找不存在的最小自然数，在过程中会出现一堆分成两堆的情况，两堆的局面的SG值就等于两堆各自的SG值抑或起来

#include<iostream>
#include<unordered_set>
#include<cstring>
using namespace std;

const int N = 110;

int f[N];//存sg值

int sg(int x) {//sg函数
if (f[x] != -1)return f[x];//如果已经搜过了就不用再算了

unordered_set<int>S;//哈希表存各种局面的sg值

//插入两堆
for (int i = 0; i < x; i++) {//第一堆插入小于总石子数的石子
for (int j = 0; j <= i; j++) {//避免重复，使第二堆小于等于第一堆的石子数
S.insert(sg(i)^sg(j));//两堆的sg值等于两堆各自的sg值抑或起来
}
}

for (int i = 0;; i++)//找到集合中不存在的自然数
if (!S.count(i))
return f[x] = i;
}

int main() {
int n; cin >> n;

memset(f, -1, sizeof f);

int res = 0;//答案

for (int i = 0; i < n; i++) {
int x; cin >> x;
res ^= sg(x);//输入每堆石子数量并抑或上它
}

if (res)puts("Yes");
else puts("No");

return 0;
}

原文地址：https://blog.csdn.net/2302_79440616/article/details/136008457

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：小程序之一———— 文件重命名
下一篇：C++(10) 模板函数

MySQL数据库基础
在过去的mysql中主要是使用的utf8mb3，但是mysql显示的就是utf8，中mysql8中区分显示了。类似于不同的编译器，虽然C/C++的代码是一样的，但是预处理、编译、汇编、链接这些过程却不
阅读更多2024-09-30
Percona Monitoring and Management
Percona Monitoring and Management (PMM)是一款开源的专用于管理和监控MySQL、MongoDB、PostgreSQL。
阅读更多2024-09-30
鸿蒙开发（NEXT/API 12）【已连接穿戴设备查询】手机侧应用开发
Wear Engine提供查询用户已连接的穿戴设备列表（即支持Wear Engine能力且与手机侧运动健康App处于连接状态的穿戴设备）的接口。
阅读更多2024-09-30
Redis数据库
本篇文章介绍了redis的相关知识，并使用springboot集成redis，实现缓存和分布式锁，后续会对文章勘误及更新~~
阅读更多2024-09-30
旧版的存档
【代码】旧版的存档。
阅读更多2024-09-30
Spring Boot 封装统一返回结果及全局异常处理
为了更细致地控制异常处理，我们可以定义一些自定义异常。然后，在全局异常处理器中添加对自定义异常的处理。通过封装统一的返回结果和全局异常处理，我们可以让Spring Boot应用更加健壮和易于维护。这种
阅读更多2024-09-30
【C++】IO流
C++IO流，包含输入输出流、文件流、字符流
阅读更多2024-09-30
低至1元/小时：国庆七天，30元通关《黑神话：悟空》！
随着《黑神话：悟空》自8月20日全球同步上线，正式登陆PC、PS5平台以来，以其精湛的画面和流畅的战斗体验，在发售三天后，该作的全平台销量超过1000万套，打破中国游戏历史记录，被媒体称为“中国首款3
阅读更多2024-09-30
阿里巴巴国际站获取商品详情item_get接口技术分享
item_get API接口是阿里巴巴开放平台提供的一个重要接口，它允许商家通过API调用，获取阿里巴巴平台上的商品详细信息。这些信息包括商品标题、价格、库存、属性、描述等，为商家提供了全面、准确的商
阅读更多2024-09-30
软件测试谣言二三事，认真你就输了
软件测试的职业寿命，取决于互联网行业能存活多久，至少目前看来，这个职业没有消失的风险，至于你能在这个职业待多久，那取决于你自己的能力，我见过不少超过35岁的老员工还在测试的职位上兢兢业业。以广州为例，
阅读更多2024-09-30

笔记---简单博弈论

接下来是SG函数

相关文章