Nim游戏详解

Nim游戏详解若一个游戏满足 由两名玩家交替行动 1 在游戏进行的任意时刻 可以执行的合法行动与轮到哪位玩家无关 2 不能行动的玩家判负 3 则称该游戏为一个公平组合游戏 尼姆游戏 NIM 属于公平组合游戏 但常见的棋类游戏 比如围棋就不是公平组合游戏

大家好,我是讯享网,很高兴认识大家。

若一个游戏满足:

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

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

题目描述

给定 n 堆石子以及一个由 k 个不同正整数构成的数字集合 S。

现在有两位玩家轮流操作,每次操作可以从任意一堆石子中拿取石子,每次拿取的石子数量必须包含于集合 S,最后无法进行操作的人视为失败。

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

输入格式
第一行包含整数 k,表示数字集合 S 中数字的个数。

第二行包含 k 个整数,其中第 i 个整数表示数字集合 S 中的第 i 个数 si。

第三行包含整数 n。

第四行包含 n 个整数,其中第 i 个整数表示第 i 堆石子的数量 hi。

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

否则,输出 No。


讯享网

数据范围
1≤n,k≤100,
1≤si,hi≤10000
输入样例:
2
2 5
3
2 4 7
输出样例:
Yes

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

1.必胜状态,先手进行某一个操作,留给后手是一个必败状态时,对于先手来说是一个必胜状态。即先手可以走到某一个必败状态。
2.必败状态,先手无论如何操作,留给后手都是一个必胜状态时,对于先手来说是一个必败状态。即先手走不到任何一个必败状态。

结论:两个人都是特别聪明的情况下,只要知道开始时处于的情况便可以知道输赢。假设n堆石子,石子数目分别是a1,a2,…,an,如果a1^a2^…^an≠0,先手必胜;否则先手必败。

证明:

1.操作到最后一种情况是n堆石子都是0,0^0^.....^0=0;

3.在操作过程中先手如果可以将自己每次操作后的情况都变成a1^a2^a3....^an=0的话,那么后手操作后一定会破坏掉这个情况,那么最后0^0^.....^0=0的这种情况一定是后手遇到的所以先手必赢。

由上述可得:
1. 如果先手面对的局面是a1^a2^…^an≠0,那么先手总可以通过拿走某一堆若干个石子,将局面变成a1^a2^…^an=0。如此重复,最后一定是后手面临最终没有石子可拿的状态。先手必胜。
2. 如果先手面对的局面是a1^a2^…^an=0,那么无论先手怎么拿,都会将局面变成a1^a2^…^an≠0,那么后手总可以通过拿走某一堆若干个石子,将局面变成a1^a2^…^an=0。如此重复,最后一定是先手面临最终没有石子可拿的状态。先手必败。

代码如下:

#include<iostream> #include<algorithm> using namespace std; int main() { int n; scanf("%d",&n); int res=0; while(n--) { int x; scanf("%d",&x); res^=x; } if(res) puts("Yes"); else puts("No"); return 0; }

讯享网

小讯
上一篇 2025-01-09 19:57
下一篇 2025-03-27 10:00

相关推荐

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容,请联系我们,一经查实,本站将立刻删除。
如需转载请保留出处:https://51itzy.com/kjqy/131396.html