【Nim 游戏】 学习笔记
2024-09-08 14:12:46
前言
没脑子选手随便一道博弈论都不会 ……
正文
Nim 游戏引入
这里给出最简单的 \(Nim\) 游戏的题目描述:
\(Nim\) 游戏
有两个顶尖聪明的人在玩游戏,游戏规则是这样的:
有\(n\)堆石子,两个人可以从任意一堆石子中拿任意多个石子(不能不拿),没法拿的人失败。
问最后谁会胜利。
结果是:当 \(n\) 堆石子的数量异或和等于 \(0\) 时,先手必胜,否则先手必败。
来考虑口胡一个证明:
考虑异或和是 \(0\) 的意义。
异或和是 \(0\) 代表着对于所有石头数的每一位二进制上的数字都有偶数个1。
那么无论先手怎么操作拿掉哪堆石头里的多少个数量。
后手都可以拿去对应的石头数量使得剩下的石头数的每一位二进制上的数字都有偶数个。
显然最后后手会拿下最后石子,此时先手败。
Code
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int T,n,m,x,f[10100],a[10010],sg[100010];
bool vis[100010];
int main(){
scanf("%d",&T);
while (T--){
scanf("%d",&n);
int ans=0;
for (int i=1; i<=n; i++){
scanf("%d",&a[i]);
ans^=a[i];
}
if (ans) printf("Yes\n");
else printf("No\n");
}
}
阶梯 Nim 游戏
给出这种 \(Nim\) 游戏的题目描述:
给你一个 \(n\) 层的楼梯,每个台阶上都有一堆石子 \(a_i\)
每次把一个台阶上的至少一个石子搬运到它的上一层台阶,不能操作的人输。
玩游戏的两个人都是绝顶聪明。
这里给出结论(反正我也不会证明):
一个状态是必胜态,当且仅当奇数层节点的 \(a_i\) 的按位异或和不为 \(0\)。
代码的话,具体看题目吧。
高手过招-巧妙的阶梯 Nim 【题解】
POI 2009 阶梯 Nim 基础题
最新文章
- 扑面而来的碎片--图片3D炸裂效果初体验
- java socket 多线程通讯
- 我的CSS布局之旅--持续更新
- scss编译
- CSS中的content和attr的用法
- 软件测试技术(二)——使用等价类划分的方法进行的UI测试
- C语言基础知识--位运算
- OC语言-01类和对象
- install samba on crux without net.
- [LeetCode]题解(python):150-Evaluate Reverse Polish Notation
- win10被微软流氓更新后编译基于visual Studio的web项目报[ArgumentOutOfRangeException: 指定的参数已超出有效值的范围
- 好代码是管出来的——Git的分支工作流与Pull Request
- 【故障公告】10:30-10:45 左右 docker swarm 集群节点问题引发故障
- [Java]LeetCode138. 复制带随机指针的链表 | Copy List with Random Pointer
- ButterKnife注解式绑定控件
- Winscp无法连接linux虚拟机解决
- js前台计算两个日期的间隔时间
- SQL Server AlwaysOn搭建
- 洛谷P1373小a和uim大逃离题解
- 04 Python数据类型
热门文章
- 如何基于ZEGO SDK 实现通话质量监测
- MATLAB地图工具箱学习心得(二)设计可变参数和位置拾取的“放大镜”式投影程序
- 【第二课】从零开始学习Linux(学习笔记)
- come on! 基于LinkedHashMap实现LRU缓存
- vscode设置vue文件高亮显示
- PowerDotNet平台化软件架构设计与实现系列(13):应用监控平台
- XCTF练习题---MISC---What-is-this
- “如何实现集中管理、灵活高效的CI/CD”研讨会报名即将截止
- ServletContext类 (共享数据+获取初始化的参数+请求转发+读取资源文件)
- 面试官:我把数据库部署在Docker容器内,你觉得如何?