蓝桥杯.异或数列(博弈，位运算)_蓝桥杯 异或数列

Question:

Solve:

思路还是不太好想的，我尽量描述~

这道题最终的判断会归结于两个数 va 和 vb 比大小，所以可以借鉴两个数比较的过程来解这道题：

从最高位开始，依次比较二者的每一位的大小

 对于这道题也是相同的思路

从最高位开始去判断最后的 va 和 vb 二进制的每一位，Alice和Bob谁会得到1，谁会得到0，还是都是0或者都是1打成平局，当然va和vb绝对不需要实际计算，用所有的 xi 推导出来结果就行

在使用上述思路之前，我们还需要讨论一个特殊情况： 最终平局

因为题上说过所有的xi都会被使用

所以如果最后是平局（va == vb），所有的xi异或值必定为 0 

va和vb都是一堆xi的异或值，又因为相同的两个数异或结果为0，所以所有的xi异或值为 0

解决了最后会得到平局的问题之后，就可以进入正题了：

因为要判断的是二人在某一 二进制位 会获得 0 还是 1，所以第一步肯定是先提取对应数据啦~ 

因此先将所有的xi的某一数位的 0 和 1 的个数计数为 cnt0，cnt1

接下来讨论cnt0和cnt1的数量对于结果的影响

1. 如果 cnt1 == 1，那么只有先手的人才有将当前位的 0 变为 1 的机会，所以先手必胜

2. 如果 cnt1 是一个偶数，那么在采取最优策略的时候（ 其实就是轮流异或 1 ），二人该数位的结果一定都是 1 ，无法决策出谁赢，所以需要判断下一位

3. 如果 cnt1 和 cnt0 都是奇数，那一定是后手赢，为什么呢？

    模拟一次过程就明白了~

    首先，Alice肯定会选择一个数位为 1 的数将自己的 0 变为 1

    之后，二者都一直选 0直到 0 消耗完，因为现在是Alice占优势的，所以这个选择一定是成立的

    到了现在，剩余了偶数个数的 1 ，而且又是Alice选择，一定就是Bob赢了

4. 如果 cnt1 和 cnt0 一奇一偶，那就会是先手赢

    同样的上述模拟，留给读者了~

总结一下：

所有xi异或为 0， 平局

cnt1 为偶数，当前位平局

cnt1 和 cnt0 都是奇数，后手赢

一奇一偶，先手赢

特别地，cnt1 == 1 ，先手赢

Code:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll t, n, a[200010], sum;
int cnt1, cnt0;
//判断胜负函数
int judge(){
    //偶数个1，无法决定胜负
    if(cnt1 % 2 == 0) return 0;
    //只有1个1，先手必胜
    if(cnt1 == 1) return 1;
    //0和1的个数都为奇数，后手胜
    if(cnt1 % 2 != 0 && cnt0 % 2 != 0)
        return -1;
    //先手胜
    else
        return 1;
}
void solve()
{
    sum = 0;
    for(int i = 1; i <= n; i++){
        cin >>a[i];  sum ^= a[i];
    }
    //所有数异或值为0，平局
    if(sum == 0) { cout <<0 <<endl; return; }
    //从最高位开始枚举
    for(int i = 20; i >= 0; i--){
        cnt1 = cnt0 = 0;
        //计数
        for(int j = 1; j <= n; j++){
            if((a[j] >> i) & 1) cnt1++;
            else cnt0++;
        }
        //judge
        int res = judge();
        if(res == 0) continue;
        else{
            cout <<res <<endl;
            return;
        }
    }
}
int main(void)
{
    cin >>t;
    while(t--){
        cin >>n;
        solve();
    }
    return 0;
}

最后附上蓝桥杯汇总链接：蓝桥杯C/C++A组省赛历年真题题解 

声明：图片均来源于蓝桥杯官网，以个人刷题整理为目的，如若侵权，请联系删除~