AcWing 891. 基础课二刷之第47题加强巩固 Nim游戏*
原题链接
简单
作者:
Snow_raw
,
2021-08-16 21:27:00
,
所有人可见
,
阅读 209
题目描述
给定 n 堆石子,两位玩家轮流操作,每次操作可以从任意一堆石子中拿走任意数量的石子(可以拿完,但不能不拿),最后无法进行操作的人视为失败。
问如果两人都采用最优策略,先手是否必胜。
输入格式
第一行包含整数 n。
第二行包含 n 个数字,其中第 i 个数字表示第 i 堆石子的数量。
输出格式
如果先手方必胜,则输出 Yes。
否则,输出 No。
数据范围
1≤n≤105,
1≤每堆石子数≤109
样例
2
2 3
输出
Yes
算法
博弈
C++ 代码
#include<bits/stdc++.h>
using namespace std;
int main(){
int t;
cin>>t;
int res=0;
while(t--){
int x;
cin>>x;
res^=x;
}
if(res)cout<<"Yes"<<endl;
else cout<<"No"<<endl;
return 0;
}
总结
本题博弈太多大神总结了,我就简单概要一下,所有堆的石头^起来得到一个x,如果x!=0那么设k为x的最高位,且所有堆
石头中一定至少有一堆石头的k位为1否则与k为x的最高位所矛盾,那么拿走在ai堆拿走ai-ai^x个石头则ai石头数量变
成ai-(ai-ai^x)=ai^x个石头,所有堆再异或一下则等于x^x=0,也就是必败态丢给对手所以自己必赢,做与必败态相对应
的映射操作即能保证自己必赢。