[AcWing] 892. 台阶-Nim游戏 (C++实现)博弈论Nim游戏例题
2022/1/5 11:08:21
本文主要是介绍[AcWing] 892. 台阶-Nim游戏 (C++实现)博弈论Nim游戏例题,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
[AcWing] 892. 台阶-Nim游戏 (C++实现)博弈论Nim游戏例题
- 1. 题目
- 2. 读题(需要重点注意的东西)
- 3. 解法
- 4. 可能有帮助的前置习题
- 5. 所用到的数据结构与算法思想
- 6. 总结
1. 题目
2. 读题(需要重点注意的东西)
思路:
首先要知道几个定义
公平组合游戏(ICG)
(1)由两名玩家交替行动
(2)在游戏进行的任意时刻,可以执行的合法行动与轮到哪位玩家无关
(3)轮流走,当一个玩家不能走时游戏结束
(4)游戏不能区分玩家的身份,例如黑白棋就是不行的
特征
给定初始局势,指定先手玩家,如果双方都采取最优策略,那么获胜者已经确定了,也就是说ICG问题存在必胜策略
必胜状态和必败状态
必胜状态:先手进行某一个操作,留给后手是一个必败状态时,对于先手来说是一个必胜状态。即先手可以走到某一个必败状态。
必败状态:先手无论如何操作,留给后手都是一个必胜状态时,对于先手来说是一个必败状态。即先手走不到任何一个必败状态。
结论
假设n堆石子,石子数目分别是a1,a2,…,an,如果a1⊕a2⊕…⊕an≠0,先手必胜;否则先手必
败。
本题思路:
本题的主要思路就是代结论,假设n堆石子,石子数目分别是a1,a2,…,an,如果a1⊕a3⊕…⊕an≠0,先手必胜;否则先手必败。
即:所有奇数级台阶上的石子异或不为0的话,先手必胜;否则先手必败
代码实现思路:
1、输入n堆石头
2、如果a1⊕a3⊕…⊕an≠0,先手必胜;否则先手必败。
注:奇数&1为1,偶数&1为0
3. 解法
---------------------------------------------------解法---------------------------------------------------
#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); // 所有奇数的异或不为0,则先手必胜;否则先手必败 if (i & 1) res ^= x; } if (res) puts("Yes"); else puts("No"); return 0; }
4. 可能有帮助的前置习题
- [AcWing] 891. Nim游戏 (C++实现)博弈论Nim游戏模板题
5. 所用到的数据结构与算法思想
- 博弈论
- Nim游戏
6. 总结
博弈论Nim游戏模板题,理解思想并背下代码。
这篇关于[AcWing] 892. 台阶-Nim游戏 (C++实现)博弈论Nim游戏例题的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-04el-table 开启定时器下,表格的选中状态会消失是什么原因-icode9专业技术文章分享
- 2024-10-03如何安装和初始化飞牛私有云 fnOS?-icode9专业技术文章分享
- 2024-10-03如何安装 App 并连接到飞牛 NAS?-icode9专业技术文章分享
- 2024-10-03如何安装飞牛 TV 并连接到影视服务器?-icode9专业技术文章分享
- 2024-10-03如何在PVE和ESXI上安装飞牛私有云 fnOS?-icode9专业技术文章分享
- 2024-10-03fnOS国产最强NAS安装系统异常情况处理-icode9专业技术文章分享
- 2024-10-03飞牛NAS如何创建存储空间?-icode9专业技术文章分享
- 2024-10-03fnOS国产最强NAS硬盘会自动休眠吗?-icode9专业技术文章分享
- 2024-10-03fnOS国产最强NAS如何安装飞牛影视和创建媒体库?-icode9专业技术文章分享
- 2024-10-03fnOS国产最强NAS如何为家人朋友开通影视账号?-icode9专业技术文章分享