POJ 2975 Nim

我们之前的\(Nim\)游戏都已经知道当\(Nim\)和为\(0\)时是必败的。

那我们就刻意制造这种情况。因为一次只能改一堆石头，不能制造几个数异或消去\(sum\)的情况，所以只用考虑将\(a[i]\)替换为\(a[i]⨁sum\)的情况就行了。

注意要保证\(a[i]⨁sum<a[i]\)。

#include<cstdio>
#include<cstdlib>

int n, a[1002], sum, ans;

int read() {
	int x = 0, f = 1; char s;
	while((s = getchar()) > '9' || s < '0') {
		if(s == '-') f = -1;
		if(s == EOF) exit(0);
	}
	while(s >= '0' && s <= '9') {
		x = (x << 1) + (x << 3) + (s ^ 48);
		s = getchar();
	}
	return x * f;
}

int main() {
	while(n = read(), n) {
		sum = ans = 0;
		for(int i = 1; i <= n; ++ i) a[i] = read(), sum ^= a[i];
		for(int i = 1; i <= n; ++ i) if((sum ^ a[i]) < a[i]) ++ ans;
		printf("%d\n", ans);
	}
	return 0;
}