HDU 1850

HDU 1850

Nim 博弈的结论： n堆石子每堆有a[i]个， a1^a2^ = k  当 k == 0 时， 先手（先手记为“A”，后手记为“B”）必败， 否则先手必胜

假设 A 先 选择了 在 第 i 堆石子中取了x个石子，除去第 i 堆石子， 其余石子的异或值 k'  = k ^ a[i] ; 轮到B取，此时可以把整局比赛 看成一局新的比赛，（B为先手，A为后手），这是我们判断B先手时是否能必胜：即需要判断 k' ^ (a[i] - x) 是否为 0 即可。

已知的是： k ^ k == 0 所以， k' ^ (a[i] - x) 可以转化为  a[i] - x 是否等于 k 因为   x > 0 所以当 a[i] > k 即 ((k ^ a[i]) < a[i] 时，我们找到了一种必胜的策略。

同理，我们遍历每一堆石子，累加必胜策略即可。

#include<bits/stdc++.h>
using namespace std;
#define clr(a) memset(a,0,sizeof(a))typedef long long ll;
const int maxn = 1e5 + 10;
const int MAXN = 1e6 + 10;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
const int N = 1010;int n;
int a[N];int main(){while(scanf("%d", &n) && n){int sum = 0, cnt = 0;for(int i=0; i<n; i++){scanf("%d", &a[i]);sum ^= a[i];}for(int i=0; i<n; i++){if((sum ^ a[i]) < a[i]) cnt ++;}cout << cnt << endl;}return 0;
}