[AcWing] 894. 拆分-Nim游戏(C++实现)博弈论SG函数例题
2022/1/5 11:06:16
本文主要是介绍[AcWing] 894. 拆分-Nim游戏(C++实现)博弈论SG函数例题,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
[AcWing] 894. 拆分-Nim游戏(C++实现)博弈论SG函数例题
- 1. 题目
- 2. 读题(需要重点注意的东西)
- 3. 解法
- 4. 可能有帮助的前置习题
- 5. 所用到的数据结构与算法思想
- 6. 总结
1. 题目
2. 读题(需要重点注意的东西)
思路:
首先要知道几个定义
公平组合游戏(ICG)
公平组合游戏(ICG)
(1)由两名玩家交替行动
(2)在游戏进行的任意时刻,可以执行的合法行动与轮到哪位玩家无关
(3)轮流走,当一个玩家不能走时游戏结束
(4)游戏不能区分玩家的身份,例如黑白棋就是不行的
特征
给定初始局势,指定先手玩家,如果双方都采取最优策略,那么获胜者已经确定了,也就是说ICG问题存在必胜策略
必胜状态和必败状态
必胜状态和必败状态
必胜状态:先手进行某一个操作,留给后手是一个必败状态时,对于先手来说是一个必胜状态。即先手可以走到某一个必败状态。
必败状态:先手无论如何操作,留给后手都是一个必胜状态时,对于先手来说是一个必败状态。即先手走不到任何一个必败状态。
结论
假设n堆石子,石子数目分别是a1,a2,…,an,如果a1⊕a2⊕…⊕an≠0,先手必胜;否则先手必
败。
SG函数
SG函数
给定一个有向无环图和一个起始顶点上的一枚棋子,两名选手交替的将这枚棋子沿有向边进行移动,无法移动者判负。事实上,这个游戏可以认为是所有公平组合游戏的抽象模型。
mex运算
mex运算
表示最小的不属于这个集合的非负整数。
对于一个给定的有向无环图,定义图的每个顶点的SG函数如下:SG(x)=mex{ SG(y) | y是x的后继 }。
首先将终点全部置0,再逐一找出前驱节点的SG值
有向图游戏的和
有向图游戏的和
设G1、G2、……、Gn是n个有向图游戏,定义游戏G是G1、G2、……、Gn的和,游戏G的移动规则是:任选一个子游戏Gi并移动上面的棋子。则SG =SG(G1) ⊕ SG(G2) ⊕ … ⊕ SG(Gn)。也就是说,游戏的和的SG函数值是它的所有子游戏的SG函数值的异或。
SG值的意义
SG值的意义
当我们面对由n个游戏组合成的一个游戏时,只需对于每个游戏求它的SG值,就可以把这些SG值全部看成Nim的石子堆,然后依照找Nim的必胜策略的方法来找这个游戏的必胜策略。
结论:
先手必胜:SG =SG(G1) ⊕ SG(G2) ⊕ … ⊕ SG(Gn) ≠ 0
先手必败:SG =SG(G1) ⊕ SG(G2)⊕ … ⊕ SG(Gn) = 0
SG值的一个定理
两堆石子的SG值,等于各堆石子SG值的异或
SG(a1,a2) = SG(a1) ⊕ SG(a2)
本题思路:
本题的主要思路就是代结论,求出每个局面的SG值,但是需要注意,此题的局面有很多种,因为一堆石子(如上图a1)又可以分为两堆石子(如上图(b1,b2)、(c1,c2)),考虑所有的局面,用mex运算计算出sg值,然后代入结论:
先手必胜:SG =SG(G1) ⊕ SG(G2) ⊕ … ⊕ SG(Gn) ≠ 0
先手必败:SG =SG(G1) ⊕ SG(G2)⊕ … ⊕ SG(Gn) = 0
3. 解法
---------------------------------------------------解法---------------------------------------------------
#include <cstring> #include <iostream> #include <algorithm> #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 ++ ) // 存储分出来的两堆石子sg值的异或 S.insert(sg(i) ^ sg(j)); for (int i = 0;; i ++ ) // mex运算求出该堆石子的sg值 if (!S.count(i)) return f[x] = i; } int main() { cin >> n; memset(f, -1, sizeof f); int res = 0; while (n -- ) { int x; cin >> x; res ^= sg(x); // 公式 } if (res) puts("Yes"); else puts("No"); return 0; }
可能存在的问题
4. 可能有帮助的前置习题
- [AcWing] 893. 集合-Nim游戏(C++实现)博弈论SG函数模板题
5. 所用到的数据结构与算法思想
- 博弈论
- SG函数
- 记忆化搜索
6. 总结
博弈论SG函数例题,理解思想并自己实现代码。
这篇关于[AcWing] 894. 拆分-Nim游戏(C++实现)博弈论SG函数例题的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-05feign默认connecttimeout和readtimeout是多少-icode9专业技术文章分享
- 2024-07-05idea控制台,日志太多,导致部分想看得日志被刷走 搜不到-icode9专业技术文章分享
- 2024-07-05The server selected protocol version Tls10 is not accepted by client preferences [TLs12]-icode9专业技术文章分享
- 2024-07-05怎么清理项目缓存-icode9专业技术文章分享
- 2024-07-04安装 Eyoucms详细图文教程-icode9专业技术文章分享
- 2024-07-04ueditor 复制文章时,图片的链接是一个下载图片地址,该如何处理?-icode9专业技术文章分享
- 2024-07-04怎样判断host有没有对wordpress有缓存呢-icode9专业技术文章分享
- 2024-07-04具有编译功能的系统make后,无法ssh连接-icode9专业技术文章分享
- 2024-07-04make后如何升级ssh-icode9专业技术文章分享
- 2024-07-03微信支付提示下单账户与支付账户不一致-icode9专业技术文章分享