算法-尼姆博弈

解题思路

这是一个经典的博弈论问题，可以使用Nim游戏的思想来解决。

Nim游戏是一个二人博弈，游戏的初始状态为有n堆石子，每堆石子的数量可以是任意自然数。双方轮流进行行动，每次行动可以从任意一堆石子中取走若干个石子（不能不取），取走最后一个石子的人获胜。

根据Nim游戏的定理，如果所有堆的石子数量的异或和为0，则先手必败，否则先手必胜。这个定理可以通过数学归纳法证明。

对于这个问题，我们可以将每堆钱看做一堆石子，那么问题就转化为了Nim游戏。如果所有堆的钱数异或和为0，则小明必败，否则小明必胜。

#include <iostream>
using namespace std;
typedef long long ll;
const ll N=1e5+10;
void solve(){ll n;cin>>n;ll a[N];ll sum=0;for(ll i=1;i<=n;i++){cin>>a[i];sum^=a[i];}if(sum==0){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;}
}
int main()
{ll t;cin>>t;while(t--) solve();return 0;
}