概述
题目描述
点击进入题目
现在，有一个n级台阶的楼梯，每级台阶上都有若干个石子，其中第i级台阶上有ai个石子(i≥1)。两位玩家轮流操作，每次操作可以从任意一级台阶上拿若干个石子放到下一级台阶中（不能不拿）。已经拿到地面上的石子不能再拿，最后无法进行操作的人视为失败。问如果两人都采用最优策略，先手是否必胜。
思路
这题分两种情况
- 先手必胜状态：当后手移动偶数台阶上的石子时，先手只需将对手移动的石子继续移到下一个台阶，这样奇数台阶的石子相当于没变，于是留给后手的又是奇数台阶异或为0的状态
- 先手必败状态：当后手移动奇数台阶上的石子时，留给先手的奇数台阶异或非0，根据经典Nim游戏，先手总能找出一种方案使奇数台阶异或为0
时间复杂度
N<=1e5
O(N)=O(100000)
代码
#include <iostream>
using namespace std;
int main()
{
int n;
cin>>n;
int res=0;
for(int i=1; i<=n; i++)
{
int x;
cin>>x;
if(i%2) res^=x;
}
if(res) cout<<"Yes";
else cout<<"No";
}
最后
以上就是顺心丝袜为你收集整理的题解【acwing】892：台阶-Nim游戏题目描述思路时间复杂度代码的全部内容，希望文章能够帮你解决题解【acwing】892：台阶-Nim游戏题目描述思路时间复杂度代码所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复