POJ 2975

题面:http://poj.org/problem?id=2975

本题就是nim游戏的一个变试,因为我们知道nim游戏中每次会取ai xor x<ai(x=a1 xor a2 xor ... xor aN的那堆石子,然后就能造成必胜局,所以只要统计有多少个满足ai xor x<ai的i即可.

Code:
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<ctime>
#include<deque>
using namespace std;
const int N=1005;
int n,k[N];
int main(){
    while(~scanf("%d",&n)){
        if(n==0){
            break;
        }
        int ans=0,sum;
        for(int i=1;i<=n;i++){
            scanf("%d",&k[i]);
            if(i==1){
                sum=k[i];
            }
            else{
                sum^=k[i];
            }
        }
        for(int i=1;i<=n;i++){
            if((sum^k[i])<k[i]){
                ans++;
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}