蓝桥杯2021年第十二届省赛-异或数列_异或后若小于原先数则输出0,大于则输出1

蓝桥杯2021年第十二届省赛真题-异或数列 - C语言网 (dotcpp.com)https://www.dotcpp.com/oj/problem2605.html

先手胜输出1，平局输出0，先手败输出-1；

A和B起始值都是0；

两人数字相同时，即A^B=0时平局；

首先0^1=1，0^0=0，1^1=0，A^B=X1^X2^……^Xn;

故平局时，X1^X2^……^Xn=0；

谁数字大就赢，也就是当A和B（二进制）从高到低有一位不同时，是1的那个人赢；

用num数组统计X1……Xn每一位为1的次数；

例如，4（100），6（110），5（101），这3个数统计后，num[3]=3，num[2]=1，num[1]=1；

【经评论区提醒加上一个判断条件】

当最高位为1的个数只有一个时，先手赢；

（代码上有的，写题解时没加上orz）

当最高位为1的个数为奇数且卡牌总数n为奇数时，先手赢；

例如最高位1出现3次（A，B，C），n=5；

先手拿A与自己的值异或，最高位是1；

接着 ，    1.后手拿B与自己的值异或，先手拿C与后手的值异或，后手最高位为0，先手胜；

                2.后手拿最高位0与自己的值异或，先手拿另一个最高位0与自己的值异或，回到1；

同时，当最高位为1的个数为奇数且卡牌总数n为偶数时，后手赢；

区别就是上面2的情况先手没有0的值拿，于是和后手交换了拿最高位为1的数的顺序；

由此推之，当最高位为1的个数为偶数时，看次高位，次高位为1个数是偶数，看次次高位……

#include<bits/stdc++.h>
using namespace std;
// A和B初始的数值都是0。
int num[23];
long long a;
void pre(long long a)
{
    int cnt=1;
    while(a){
        if(a&1)num[cnt]++;
        cnt++;
        a>>=1;
    }
}
int main()
{
    int T;
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>T;
    while(T--){
        memset(num,0,sizeof(num));
        int n,sum=0;
        cin>>n;
        for(int i=0;i<n;i++){
            cin>>a;
            pre(a);
            sum^=a;
        }
        if(!sum)puts("0");
        else{
            for(int i=20;i>0;i--)
            if(num[i]==1){puts("1");break;}
            else if(num[i]%2==1){
                if(n%2==1){puts("1");break;}
                else if(n%2==0){puts("-1");break;}
            }
        }
    }
    return 0;
}