题目描述
蓝桥公司给他们的员工准备了丰厚的奖金，公司主管小明并不希望发太多的奖金，他想把奖金留给智慧的人，于是他决定跟每一个员工玩一个游戏，规则如下：
- 桌面上一共有 n堆一元钱。
- 双方轮流行动，由小明先行动，每次行动从某一堆钱中拿走若干元（至少一元钱），取走最后一元钱的人获胜。
输入描述
【算法|蓝桥 小明的游戏1 博弈论 nim】第一行为一个整数 T，表示测试数据数量。
每个测试用例包含俩行。第一行为一个整数 n ， 第二行包括 n个整数 a1?,a2?...an? 表示第 i 堆有 ai? 元。
1 \leq T, n \leq 10^5, 1 \leq a_i \leq 10^91≤T,n≤105,1≤ai?≤109 。
保证所有测试用例的 nn 的和不超过 2 \times 10^52×105。
输出描述
如果员工能拿到奖金输出
YES? ， 否则输出 NO。输入输出样例
示例 1
输入
3
2
1 1
1
1
3
2 2 1
输出
YES
NO
NO
运行限制
- 最大运行时间：1s
- 最大运行内存: 128M
思路：
这题为 博弈原型：
n 堆石子,俩人轮流从某一堆中取若干个石子，至少取一个，最后一人取完获胜， 问先手必胜还是必 败？ 做法： 和为 先手必胜.( 和为全部石子数量的异或值)
^ 异或 二进制相对应 相同为0，相反为1
代码：
#include
using namespace std;
int main()
{
int T;
cin>>T;
while(T--){
int n;
cin>>n;
int nim=0;
for(int i=0;
i>x;
nim^=x;
//nim和为0，先手必胜，否则败（nim和为全部数量的疑惑值）
}
if(nim==0) cout<<"YES"< 推荐阅读
- #|力扣-105题 从前序与中序遍历序列构造二叉树（C++）- dfs
- C++|C++-析构函数
- C语言程序练习|交换最小值和最大值
- acm算法学习|4/5 逆元+深搜+bfs
- 麦克算法|第12节课 图
- 寒假刷题特辑|【第五章】 C语言之牛客网刷题笔记 【点进来保证让知识充实你一整天】
- java|教你代码实现抢红包功能
- 学习|使用IOS快捷指令打开任意支付宝小程序
- 笔记|单调栈详解-基于LeetCode的题目