给定 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