题目:题目链接
题目的意思就是普通的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;
}
努力努力...