算法【博弈类问题】

server/2025/2/23 11:34:24/

本文最开始讲解一些常见博弈类问题如巴什博弈(Bash)、尼姆博弈(Nim)、斐波那契博弈(Fibonacci)、威佐夫博弈(Wythoff)。通过这些讲解会发现，这些博弈问题在考场上要临时想清楚是不太可能的，所以需要后面的内容即SG函数、SG定理的内容，大多数博弈类问题都可以根据SG定理来解决。

博弈类问题大致分为，公平组合游戏、非公平组合游戏（绝大多数的棋类游戏）、反常游戏。只需要关注公平组合游戏(ICG)，反常游戏是公平组合游戏的变形，经济类博弈也不是课程所讨论的范围。

1.两个玩家轮流行动且游戏方式一致

2.两个玩家对状况完全了解

3.游戏一定会在有限步数内分出胜负

4.游戏以玩家无法行动结束

博弈的双方都被认为是神之个体，因为所有玩家对状况完全了解，且充分为自己打算，绝对理性

当局面确定，结果必然注定，并且没有任何随机的成分。游戏中的每一个状态，最终导致的结果也必然注定，只有必胜态、必败态，两种状态。这一类博弈问题的结果没有任何意外，一方可以通过努力去改变结果是不可能的，这一点是反直觉的。

下面通过题目加深理解。

题目一

巴什博弈(Bash Game)

一共有n颗石子，两个人轮流拿，每次可以拿1~m颗石子。拿到最后一颗石子的人获胜，根据n、m返回谁赢。

分析：如果还剩m+1个则后手必赢，所以在n为m+1的整数倍时，先手不可能将一份m+1拿完，而后手只需要拿完后保持m+1的整数倍就能保证赢。代码如下。

class Solution {
public:bool isWin(int n, int m) {return n % (m+1) == 0 ? "后手" : "先手";}
};

题目二

测试链接：P4018 Roy&October之取石子 - 洛谷

分析：分析可知6及6的整数倍不可能是任何质数的自然数次方，所以如果是石子数如果是6的整数倍，那么不管先手怎么取，后手只需要保证取完剩下的石子数是6的整数倍就会必赢。代码如下。

#include <iostream>
using namespace std;
int T;
int n;
int ans[100000];
int main(void){scanf("%d", &T);for(int i = 0;i < T;++i){scanf("%d", &n);ans[i] = n % 6 != 0 ? 1 : 0;}for(int i = 0;i < T-1;++i){if(ans[i]){printf("October wins!\n");}else{printf("Roy wins!\n");}}if(ans[T-1]){printf("October wins!");}else{printf("Roy wins!");}return 0;
}

题目三

测试链接：P2197 【模板】Nim 游戏 - 洛谷

分析：结论可以直接记住，具体分析可以参考下面的sg定理。尼姆博弈如果每堆石子数异或结果为0则后手赢，不为0则先手赢。代码如下。

#include <iostream>
using namespace std;
int T;
int n;
int ans[10];
int main(void){scanf("%d", &T);int temp1, temp2;for(int i = 0;i < T;++i){temp1 = 0;scanf("%d", &n);for(int j = 0;j < n;++j){scanf("%d", &temp2);temp1 ^= temp2;}ans[i] = temp1;}for(int i = 0;i < T-1;++i){if(ans[i] == 0){printf("No\n");}else{printf("Yes\n");}}if(ans[T-1] == 0){printf("No");}else{printf("Yes");}return 0;
}

题目四

测试链接：P4279 [SHOI2008] 小约翰的游戏 - 洛谷

分析：可以知道如果所有石子数都为1，则谁赢取决于堆数的奇偶性；如果只有一堆石子数超过1其他都为1，则先手可以根据石子数为1的堆数来决定将超过1的那堆石子拿完还是剩1个所以先手必赢；观察到只有一堆石子数超过1其他都为1时石子数的异或结果必不为0，而如果有多个超过1的堆时所有堆异或结果如果不为0，则先手可以使拿过之后异或结果为0，而后手拿完必使异或结果不为0，这样先手必会先碰见只有一堆石子数超过1其他都为1的情况，保证先手赢；如果所有堆异或结果如果为0则后手赢。代码如下。

#include <iostream>
using namespace std;
int T;
int N;
bool ans[500];
int main(void){scanf("%d", &T);int pile_1, pile_other, res, temp;for(int i = 0;i < T;++i){pile_1 = 0;pile_other = 0;res = 0;scanf("%d", &N);for(int j = 0;j < N;++j){scanf("%d", &temp);if(temp == 1){++pile_1;}else{++pile_other;}res ^= temp;}if(pile_other == 0){ans[i] = pile_1 % 2 != 1;}else{ans[i] = res != 0;}}for(int i = 0;i < T-1;++i){if(ans[i]){printf("John\n");}else{printf("Brother\n");}}if(ans[T-1]){printf("John");}else{printf("Brother");}return 0;
}

题目五

测试链接：P6487 [COCI 2010/2011 #4] HRPA - 洛谷

分析：首先，需要知道如果石子数是斐波那契数列的数则必须一次全部拿完才能保证赢，以及齐肯多夫定理，任何正整数都可以表示成若干个不连续的斐波那契数之和。所以如果石子数是斐波那契数列则直接返回，否则找到分解出的最小的斐波那契数即是答案。代码如下。

#include <iostream>
using namespace std;
long long f[101];
int main(void){long long n;scanf("%ld", &n);f[0] = 1;f[1] = 2;for(int i = 2;i < 101;++i){f[i] = f[i-1] + f[i-2];}int l, r, m, index;while (n != 0){l = 0;r = 100;while (l <= r){m = l + (r - l) / 2;if(f[m] <= n){index = m;l = m + 1;}else{r = m - 1;}}n -= f[index];}printf("%ld", f[index]);return 0;
}

题目六

测试链接：P2252 [SHOI2002] 取石子游戏|【模板】威佐夫博弈 - 洛谷

分析：这道题可以直接记住结论。小 != (大 - 小) * 黄金分割比例，先手赢。小 == (大 - 小) * 黄金分割比例，后手赢。不过需要将黄金分割比的精度提高，不然过不了全部的用例。代码如下。

#include <iostream>
#include <cmath>
using namespace std;
int a, b;
int main(void){scanf("%d%d", &a, &b);int more = max(a, b);int less = min(a, b);long double gold = (sqrtl(5.0L) + 1.0L) / 2.0L;printf("%d", less != (int)((more - less) * gold));return 0;
}

图游戏的概念

任何局面都认为是图中的点，每一个局面都可以通过一种行动，走向图中的下一个点。如果当前行动有若干个，那么后继节点就有若干个。最终，必败局面的点认为不再有后继节点。那么公平组合游戏（ICG），就可以对应成一张图。

SG函数(Sprague-Grundy函数）

如下是SG返回值的求解方式，俗称mex过程。最终必败点是A，规定SG(A) = 0。假设状态点是B，那么SG(B) = 查看B所有后继节点的sg值，其中没有出现过的最小自然数。SG(B) != 0，那么状态B为必胜态；SG(B) == 0，那么状态B为必败态。

SG定理(Bouton定理)

如果一个ICG游戏（总），由若干个独立的ICG子游戏构成（分1、分2、分3..)，那么：SG(总) = SG(分1) ^ SG(分2) ^ SG(分3)..  任何ICG游戏都是如此，正确性证明类似尼姆博弈。当数据规模较大时，要善于通过对数器的手段，打印SG表并观察，看看能不能发现简洁规律。

下面通过题目加深理解。

题目七

SG定理用法展示巴什博弈

一共有n颗石子，两个人轮流拿，每次可以拿1~m颗石子。拿到最后一颗石子的人获胜，根据n、m返回谁赢。

分析：对于sg(0)，必输则sg(0)是0，然后按照规则推导后面的sg值。当然，在观察sg值之后可以总结出一些公式，比如题目一中的总结出之后不需要再去求每个sg值。代码如下。

class Solution {
public:bool isWin(int n, int m) {vector<int> sg;vector<bool> appear;sg.resize(n+1);sg[0] = 0;appear.resize(m+1);for(int i = 1;i <= n;++i){appear.assign(m+1, false);for(int j = 1;j <= m && i - j >= 0;++j){appear[sg[i-j]] = true;}for(int j = 0;j <= m;++j){if(!appear[j]){sg[i] = j;break;}}}return sg[n] != 0;}
};

题目八

SG定理用法展示尼姆博弈

一共有 n 堆石头，两人轮流进行游戏。在每个玩家的回合中，玩家需要选择任一 非空石头堆，从中移除任意非零数量的石头。如果不能移除任意的石头，就输掉游戏。返回先手是否一定获胜。

分析：有了sg定理就可以知道为什么是每堆石子数异或了，代码如下。

#include <iostream>
using namespace std;
int T;
int n;
int stones[10000];
int ans[10];
int main(void){scanf("%d", &T);int temp;for(int i = 0;i < T;++i){scanf("%d", &n);for(int j = 0;j < n;++j){scanf("%d", &stones[j]);}temp = stones[0];for(int j = 1;j < n;++j){temp ^= stones[j];}ans[i] = temp;}for(int i = 0;i < T-1;++i){if(ans[i] == 0){printf("No\n");}else{printf("Yes\n");}}if(ans[T-1] == 0){printf("No");}else{printf("Yes");}return 0;
}

题目九

两堆石头的巴什博弈

有两堆石头，数量分别为a、b。两个人轮流拿，每次可以选择其中一堆石头，拿1~m颗。拿到最后一颗石子的人获胜，根据a、b、m返回谁赢。

来自真实大厂笔试，没有在线测试。

分析：只是巴什博奕的小拓展。代码如下。

class Solution {
public:string whoWin(int a, int b, int m) {return a % (m + 1) == b % (m + 1) ? "后手" : "先手";}
};

题目十

三堆石头拿取斐波那契数博弈

有三堆石头，数量分别为a、b、c。两个人轮流拿，每次可以选择其中一堆石头，拿取斐波那契数的石头。拿到最后一颗石子的人获胜，根据a、b、c返回谁赢。

来自真实大厂笔试，每堆石子的数量在10^5以内，没有在线测试。

分析：先生成一个斐波那契数列，然后推导sg值即可。代码如下。

class Solution {
public:int f[30];string whoWin(int a, int b, int c) {f[0] = 1;f[1] = 2;for(int i = 2;i < 30;++i){f[i] = f[i-1] + f[i-2];}int maxValue = max(a, max(b, c));vector<int> sg;sg.resize(maxValue+1);vector<bool> appear;appear.resize(30);sg[0] = 0;for(int i = 1;i <= maxValue;++i){appear.assign(30, false);for(int j = 0;j < 30 && i - f[j] >= 0;++j){appear[sg[i-f[j]]] = true;}for(int j = 0;j < 30;++j){if(!appear[j]){sg[i] = j;break;}}}return sg[a] ^ sg[b] ^ sg[c] == 0 ? "后手" : "先手";}
};

题目十一

测试链接：P2148 [SDOI2009] E&D - 洛谷

分析：这道题基本思路很简单，求一个二维的sg表，不过因为数据量过大，必会超时，所以根据生成一些较小值的sg值打表找规律可以发现，对于sg[a][b]，其值为(a - 1) | (b - 1)中最右边0的位数。代码如下。

#include <iostream>
using namespace std;
int T;
int N;
bool ans[20];
int main(void){scanf("%d", &T);int res;int temp1, temp2, temp3;for(int i = 0;i < T;++i){scanf("%d", &N);res = 0;for(int j = 0;j < N/2;++j){scanf("%d %d", &temp1, &temp2);temp3 = (temp1 - 1) | (temp2 - 1);for(int k = 0;k < 32;++k){if((temp3 & (1 << k)) == 0){res ^= k;break;}}}ans[i] = res != 0;}for(int i = 0;i < T-1;++i){if(ans[i]){printf("YES\n");}else{printf("NO\n");}}if(ans[T-1]){printf("YES");}else{printf("NO");}return 0;
}

题目十二

测试链接：P3185 [HNOI2007] 分裂游戏 - 洛谷

分析：这道题因为每次操作涉及多个石碓，所以每个石堆并不是独立的，并不能简单粗暴像之前的题一样。这次将每次石子看作是独立的，并且将石碓的下标倒置，这样石子在0下标石碓的sg值就是0，代表必输。如果石子在i堆，它的其中一个后继是去到了j和k堆，那么这个情况的sg值就是sg(j) ^ sg(k)，将所有情况找到，才求出sg(i)。对于所有石子求异或，最后的值如果为0代表先手必输；否则去遍历先手的所有第一次操作，如果操作可以使sg总为0，代表后手必输，这次操作就是先手必赢操作之一，因为将下标倒置，所以找到的第一个必赢操作就是字典序最小的。代码如下。

#include <iostream>
#include <vector>
using namespace std;
int t;
int n;
int sg[21];
int bottle[21];
int ans[10][4];
void build(){vector<bool> appear;appear.reserve(101);sg[0] = 0;for(int i = 1;i <= 21;++i){appear.assign(101, false);for(int j = i-1;j >= 0;--j){for(int k = j;k >= 0;--k){appear[sg[j] ^ sg[k]] = true;}}for(int j = 0;j < 101;++j){if(!appear[j]){sg[i] = j;break;}}}
}
int main(void){build();scanf("%d", &t);int res, nums;for(int i = 0;i < t;++i){scanf("%d", &n);res = 0;nums = 0;for(int j = n-1;j >= 0;--j){scanf("%d", &bottle[j]);if(bottle[j] % 2 == 1){res ^= sg[j];}}if(res == 0){ans[i][0] = -1;ans[i][1] = -1;ans[i][2] = -1;ans[i][3] = 0;}else{for(int j = n-1;j >= 1;--j){if(bottle[j] != 0){for(int k = j-1;k >= 0;--k){for(int l = k;l >= 0;--l){if((res ^ sg[j] ^ sg[k] ^ sg[l]) == 0){++nums;if(nums == 1){ans[i][0] = n-1-j;ans[i][1] = n-1-k;ans[i][2] = n-1-l;}}}}}}ans[i][3] = nums;}}for(int i = 0;i < t-1;++i){printf("%d %d %d\n%d\n", ans[i][0], ans[i][1], ans[i][2], ans[i][3]);}printf("%d %d %d\n%d", ans[t-1][0], ans[t-1][1], ans[t-1][2], ans[t-1][3]);return 0;
}


http://www.ppmy.cn/server/170118.html

相关文章

（安全防御）DNS透明代理

（安全防御）DNS透明代理

拓扑需求 配置步骤 1.完成防火墙基本接口配置 2.创建服务端的链路接口 3.配置虚拟DNS服务器&#xff0c;以及真是DNS服务器信息 slb enable 开启负载均衡功能 slb进入服务器负载均衡配置视图 设置真实服务器IP地址 端口 创建虚拟服务器组 设置虚拟ip地址 关联真实服务器组 …
阅读更多...
OpenFeign 实现远程调用

OpenFeign 实现远程调用

1. 问题引入 在前面写的代码中&#xff0c;通过使用RestTemplate来实现远程调用&#xff0c;但是这种方式还是存在一些问题 需要拼接 URL&#xff0c;灵活性高&#xff0c;但是 URL 复杂时容易写错代码可读性差 而 OpenFeign 就解决了上述问题&#xff0c;OpenFeign 是一个声…
阅读更多...
MySQL 日志

MySQL 日志

MySQL 日志 慢查询日志(Slow query log) 慢查询⽇志由执⾏时间超过系统变量 long_query_time 指定的秒数的SQL语句组成&#xff0c;并且检 查的⾏数⼤于系统变量 min_examined_row_limit 指定值。被记录的慢查询需要进⾏优化&#xff0c; 可以使⽤mysqldumpslow客⼾端程序对慢…
阅读更多...
rk3588/3576板端编译程序无法运行视频推理

rk3588/3576板端编译程序无法运行视频推理

图片推理可以&#xff0c;但是视频不行&#xff0c;运行视频推理报错&#xff1a;segment fault. 我遇到的问题原因是ffmpeg安装有问题&#xff0c;可以先在板端运行&#xff1a;ffmpeg -version ffmpeg version 4.2.4-1ubuntu1.0firefly6 Copyright (c) 2000-2020 the FFmpe…
阅读更多...
Android SDK封装打包流程详解

Android SDK封装打包流程详解

在Android开发中&#xff0c;SDK的封装和打包是将功能模块化并供其他开发者使用的常见需求。以下是Android SDK封装和打包的基本流程&#xff1a; 1. 创建Android Library模块 首先&#xff0c;你需要创建一个Android Library模块&#xff0c;而不是普通的Application模块。 在…
阅读更多...
Ubuntu22.04 - gflags的安装和使用

Ubuntu22.04 - gflags的安装和使用

目录 gflags 介绍gflags 安装gflags 使用 gflags 介绍 gflags 是Google 开发的一个开源库&#xff0c;用于 C应用程序中命令行参数的声明、定义和解析。gflags 库提供了一种简单的方式来添加、解析和文档化命令行标志(flags),使得程序可以根据不同的运行时配置进行调整。 它具…
阅读更多...
告别卡关！XSS挑战之旅全关卡通关思路详解

告别卡关！XSS挑战之旅全关卡通关思路详解

XSS挑战之旅 XSS测试思路Level1Level2Level3Level4Level5Level6Level7Level8Level9Level10Level11Level12Level13Level14Level15Level16Level17Level18Level19Level20免责声明&#xff1a; XSS测试思路 确定输入输出点&#xff1a; 寻找URL参数、表单输入、HTTP头&#xff08;R…
阅读更多...
C从入门到放弃篇1

C从入门到放弃篇1

各位新入坑C语言的朋友&#xff0c;你们有福了因为你们遇到了我&#xff0c;我会带你放弃C语言&#xff0c;哈哈哈哈哈。 其实&#xff0c;学任何东西都是循序渐进的&#xff0c;在学习的初期投入更多的精力&#xff0c;将来你会越学越快。我相信&#xff0c;放弃是最容易的事…
阅读更多...
最新文章

Copyright @ 2022~2023