题目:题目链接
题目的意思就是普通的nim博弈,不同的是要你求出先手在胜利的时候第一步可以移动的方法数,如果输了直接输出0;
分析:因为答案最多只有n,令ans=a1^a2^…^an,如果需要构造出异或值为0的数,而且由于只能操作一堆石子,所以对于某堆石子ai,现在对于ans^ai,就是除了ai以外其他的石子的异或值,如果ans^ai<=ai,那么对于ai的话,是可以减小到ans^ai的值,然后使得所有数的异或值为0,也即转移到了必败态。
代码:
#include <iostream> #include <cstdio> #include <string> #include <string.h> #include <map> #include <vector> #include <cstdlib> #include <cmath> #include <algorithm> #include <cmath> #include <queue> #include <set> #include <stack> using namespace std; int main() { int n; while(scanf("%d", &n)) { if(n==0) break; int sp[1100]; int sum = 0; for(int i = 0; i < n; ++i) { scanf("%d", &sp[i]); sum ^= sp[i]; } if(sum==0) { printf("0\n"); continue; } else { int ans = 0; for(int i = 0; i < n; ++i) { if((sum ^ sp[i]) <= sp[i]) ans++; } printf("%d\n", ans); } } return 0; }
努力努力...