Acwing 892. 台阶-Nim游戏

现在，有一个n级台阶的楼梯，每级台阶上都有若干个石子，其中第i级台阶上有ai个石子(i≥1)。

两位玩家轮流操作，每次操作可以从任意一级台阶上拿若干个石子放到下一级台阶中（不能不拿）。

已经拿到地面上的石子不能再拿，最后无法进行操作的人视为失败。

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

输入格式

第一行包含整数n。

第二行包含n个整数，其中第i个整数表示第i级台阶上的石子数ai。

输出格式

如果先手方必胜，则输出“Yes”。

否则，输出“No”。

数据范围

1≤n≤10^5,
1≤ai≤10^9

输入样例：

3
2 1 3

输出样例：

Yes

胜者:只要维持自己取完石子之后奇数台阶上的石子数量异或为0,就可以保持必胜状态

因为偶数台阶上的石子必然要向奇数台上放,如果奇数台阶上的石子异或不为0的话,就可以通过从某一个奇数台阶上拿下来一些石子放在偶数台阶上使得奇数台阶上的石子数量异或变为0

如果奇数台阶上的石子异或原本为0,由于每次操作不能不拿石子,所以操作后奇数台阶上的石子异或变为非0

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

最后

以上就是微笑荔枝为你收集整理的Acwing 892. 台阶-Nim游戏的全部内容，希望文章能够帮你解决Acwing 892. 台阶-Nim游戏所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。