NIM

目录

题目传送门

题目描述

给定 n 堆石子,两位玩家轮流操作,每次操作可以从任意一堆石子中拿走任意数量的石子(可以拿完,但不能不拿),最后无法进行操作的人视为失败。

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

输入格式

第一行包含整数 n。

第二行包含 n 个数字,其中第 i 个数字表示第 i 堆石子的数量。

输出格式

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

否则,输出 No

数据范围

1≤n≤105
1≤每堆石子数≤109

输入样例:

2
2 3

输出样例:

Yes

算法求解

分析

NIM
https://www.acwing.com/solution/content/14269/
NIM
NIM

代码

#include<iostream>
using namespace std;
int n;

int main()
{
    scanf("%d", &n);
    int res = 0;
    for(int i = 0; i < n; i++)
    {
        int a; 
        scanf("%d", &a);
        res ^= a;
    }
    if(res) puts("Yes");
    else    puts("No");
    return 0;
}

时间复杂度

参考文章

https://www.acwing.com/solution/content/14269/

上一篇:Qt创建多线程的两种方式


下一篇:c – QVector对默认构造函数的要求是什么原因?