1 条题解
-
0
这是一个经典的博弈论问题,可以使用Nim游戏的思想来解决。
Nim游戏是一个二人博弈,游戏的初始状态为有 堆石子,每堆石子的数量可以是任意自然数。双方轮流进行行动,每次行动可以从任意一堆石子中取走若干个石子(不能不取),取走最后一个石子的人获胜。
根据Nim游戏的定理,如果所有堆的石子数量的异或和为 ,则先手必败,否则先手必胜。这个定理可以通过数学归纳法证明。
对于这个问题,我们可以将每堆钱看做一堆石子,那么问题就转化为了Nim游戏。如果所有堆的钱数异或和为 ,则Rarity必输光光,否则Rarity必拿回压岁钱。
#include <iostream> using namespace std; int main(void) { int t; cin >> t; for (int i=0;i<t;i++) { int n; cin>>n; int res = 0; for (int j=0;j<n;j++) { int x; cin >> x; res ^= x; } if (res) cout << "NO" << endl; else cout << "YES" << endl; } return 0; }
- 1
信息
- ID
- 103
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 5
- 标签
- 递交数
- 29
- 已通过
- 15
- 上传者