首页 > 其他分享 >Nim游戏

Nim游戏

时间:2023-08-07 22:48:49浏览次数:33  
标签:状态 游戏 Nim 必败 石子 必胜 int

给定 n 堆石子,两位玩家轮流操作,每次操作可以从任意一堆石子中拿走任意数量的石子(可以拿完,但不能不拿),最后无法进行操作的人视为失败。

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

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

第二行包含 n 个数字,其中第 i 个数字表示第 i 堆石子的数量。

输出格式
如果先手方必胜,则输出 Yes。

否则,输出 No。

数据范围
1≤n≤10^5,
1≤每堆石子数≤10^9
输入样例:
2
2 3
输出样例:
Yes

分析

若一个游戏满足:

由两名玩家交替行动
在游戏进行的任意时刻,可以执行的合法行动与轮到哪位玩家无关
不能行动的玩家判负
则称该游戏为一个公平组合游戏。

尼姆游戏(NIM)属于公平组合游戏,但常见的棋类游戏,比如围棋就不是公平组合游戏,因为围棋交战双方分别只能落黑子和白子,胜负判定也比较负责,不满足条件2和3。

必胜状态和必败状态
在解决这个问题之前,先来了解两个名词:

必胜状态,先手进行某一个操作,留给后手是一个必败状态时,对于先手来说是一个必胜状态。即先手可以走到某一个必败状态。
必败状态,先手无论如何操作,留给后手都是一个必胜状态时,对于先手来说是一个必败状态。即先手走不到任何一个必败状态。
结论
假设nn堆石子,石子数目分别是a1,a2,…,an,如果a1⊕a2⊕…⊕an≠0,先手必胜;否则先手必败。

#include <iostream>
#include <cstdio>
using namespace std;

/*
先手必胜状态:先手操作完,可以走到某一个必败状态
先手必败状态:先手操作完,走不到任何一个必败状态
先手必败状态:a1 ^ a2 ^ a3 ^ ... ^an = 0
先手必胜状态:a1 ^ a2 ^ a3 ^ ... ^an ≠ 0
*/

int main(){
    int n;
    scanf("%d", &n);
    int res = 0;
    for(int i = 0; i < n; i++) {
        int x;
        scanf("%d", &x);
        res ^= x;
    }
    if(res == 0) puts("No");
    else puts("Yes");
} 

标签:状态,游戏,Nim,必败,石子,必胜,int
From: https://www.cnblogs.com/liyuzhong/p/17612927.html

相关文章

  • 知识图:人工智能和数据科学的游戏规则改变者
    知识图谱已成为人工智能和数据科学中一种强大而通用的方法,用于记录结构化信息,以促进成功的数据检索、推理和推理。本文探讨了最先进的知识图谱,包括构造、表示、查询、嵌入、推理、对齐和融合。我们还讨论了知识图谱的许多应用,例如推荐引擎和问答系统。最后,为了为新的进展和研究机......
  • 知识图:人工智能和数据科学的游戏规则改变者
    [知识图谱]已成为人工智能和数据科学中一种强大而通用的方法,用于记录结构化信息,以促进成功的数据检索、推理和推理。本文探讨了最先进的知识图谱,包括构造、表示、查询、嵌入、推理、对齐和融合。我们还讨论了知识图谱的许多应用,例如推荐引擎和问答系统。最后,为了为新的进展和研究......
  • 知识图:人工智能和数据科学的游戏规则改变者
    [知识图谱]已成为人工智能和数据科学中一种强大而通用的方法,用于记录结构化信息,以促进成功的数据检索、推理和推理。本文探讨了最先进的知识图谱,包括构造、表示、查询、嵌入、推理、对齐和融合。我们还讨论了知识图谱的许多应用,例如推荐引擎和问答系统。最后,为了为新的进展和研究......
  • 知识图:人工智能和数据科学的游戏规则改变者
    [知识图谱]已成为人工智能和数据科学中一种强大而通用的方法,用于记录结构化信息,以促进成功的数据检索、推理和推理。本文探讨了最先进的知识图谱,包括构造、表示、查询、嵌入、推理、对齐和融合。我们还讨论了知识图谱的许多应用,例如推荐引擎和问答系统。最后,为了为新的进展和研究......
  • 取数游戏 Atcoder-abc128_d
    枚举两端取了几个数,将手中的负数从小到大放回序列即可#include<bits/stdc++.h>usingnamespacestd;intn,m,a[55],c[55],ans=-0x7fffffff;intmain(){scanf("%d%d",&n,&m);for(inti=1;i<=n;i++)scanf("%d",&a[i]);f......
  • P1005 [NOIP2007 提高组] 矩阵取数游戏题解
    题面传送门:P1005[NOIP2007提高组]矩阵取数游戏-洛谷|计算机科学教育新生态(luogu.com.cn)分析题目可知,这道题是一道求最值的问题,第一次看题没有认真读题,以为是每次只在某一行中选一个数,于是想了半天无果。重新读题才发现每次需要每行都取,那么这就很简单了,相当于在每一行......
  • 代理IP与Socks5代理:跨界电商、游戏与爬虫的技术赋能
    一、代理IP与Socks5代理:简介与区别代理IP:代理IP是一种通过代理服务器转发网络请求的技术。它可以隐藏用户的真实IP地址,提供匿名访问,是实现地理突破的关键工具。Socks5代理:Socks5代理采用SOCKS5协议,相对于传统代理IP技术,支持TCP和UDP协议,提供更高性能、更强安全性和更全面的功能。......
  • 游戏运营——关于游戏玩家社群
    记得在上个游戏中,我们在TapTap上线,当时建了两个QQ群,游戏上线不到一周的时间,QQ群就满了。我惊讶与群友们的活跃度,真是热爱游戏的小伙伴们,从个人游戏体验到建议,不吝啬地在群里表达,每隔一小时都能达到999+,我的心情也跟着激动、开心和紧张。所以在现在的项目里,我第一时间就想到建立......
  • 基于NodeJS游戏交流社区系统的设计与实现
    随着社会的发展,社会的各行各业都在利用信息化时代的优势。计算机的优势和普及使得各种信息系统的开发成为必需。游戏交流社区系统,主要的模块包括查看首页、个人中心、用户管理、游戏类型管理、游戏信息管理、游戏攻略管理、交流论坛、系统管理等功能。系统中管理员主要是为了安全有......
  • 【算法】用c#实现德州扑克卡牌游戏规则
    德州扑克是一种牌类游戏,可多人参与,它的玩法是,玩家每人发两张底牌,桌面依次发5张公共牌,玩家用自己的两张底牌和5张公共牌自由组合,按大小决定胜负。使用c#完成功能Hand()以返回手牌类型和按重要性递减顺序排列的等级列表,用于与同类型的其他手牌进行比较,即最佳手牌。可能的手牌按价......