蓝桥杯|历届真题:异或数列

1.题目

【问题描述】

Alice 和 Bob 正在玩一个异或数列的游戏。初始时，Alice 和 Bob 分别有一个整数$a$和$b$，有一个给定的长度为 $n$ 的公共数列 $X_1,X_2, \dots, X_{n_i}$ 。Alice 和 Bob 轮流操作，Alice 先手，每步可以在以下两种选项中选一种：

选项 1：从数列中选一个 $Xi$ 给 Alice 的数异或上，或者说令 $a$ 变为 $a ⊕ Xi$。（其中 $⊕$ 表示按位异或）

选项 2：从数列中选一个$Xi$ 给 Bob 的数异或上，或者说令 $b$变为$ b ⊕ Xi$。每个数 $X_i$ 都只能用一次，当所有 $Xi$ 均被使用后（$n$ 轮后）游戏结束。游戏结束时，拥有的数比较大的一方获胜，如果双方数值相同，即为平手。

现在双方都足够聪明，都采用最优策略，请问谁能获胜？

【输入格式】

每个评测用例包含多组询问。询问之间彼此独立。

输入的第一行包含一个整数 $T$，表示询问数。

接下来 $T$ 行每行包含一组询问。其中第 i 行的第一个整数 $n_i$ 表示数列长度，随后 $n_i$个整数 $X_1,X_2, \dots, X_{n_i}$ 表示数列中的每个数。

【输出格式】

输出 $T$ 行，依次对应每组询问的答案。

每行包含一个整数 1、0 或 −1 分别表示 Alice 胜、平局或败。

【样例输入】

4
1 1
1 0
2 2 1
7 992438 1006399 781139 985280 4729 872779 563580

【样例输出】

【评测用例规模与约定】

对于所有评测用例，$1 ≤T≤ 200000,1 ≤ \sum^T_{i=1}n_i ≤ 200000,0 ≤X_i <2^{20}$。

2. 题解

2.1 思路分析

a和b起始值都是0 两人数字相同时，即a^b=0时平局
a^b=X1^X2^……^Xn 因此 X1^X2^……^Xn=0-->平局

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

用 bitCount[]  数组 统计X1……Xn每一位为1的次数；
eg：
    4(100)、6(110)、5（101），这3个数统计后
    bitCount[3]=3，bitCount[2]=1，bitCount[1]=1

从最高位遍历bitCount[i]
    bitCount[i]==1，该位数只要一个1，Alice 先手，胜
    bitCount[i]是偶数，无影响，不处理
    bitCount[i]是奇数：
        n是偶数，奇数个1奇数个0，只要后手把0先选完，后手就获得最后一个1的支配权，后手胜
        n是奇数，奇数个1偶数个0，先手把0先选完，先手获得最后一个1的支配权,先手胜

2.2 代码实现

import java.util.*;

public class Main {

    static Scanner scanner = new Scanner(System.in);

    // 统计x1-xn对应的2进制数的每1位的1的总数量
    public static int[] getBitCount(int[] arr){
        int[] bitCount = new int[20];//存储每一位对应的1的总数
        for (int i = 0; i < bitCount.length; i++) {
            bitCount[i]=0;
        }

        for (int i = 0; i < arr.length ; i++) {
            int tmp = arr[i];

            int bit=0;
            while (tmp>0){
                bitCount[bit++]+=tmp&1;
                tmp = tmp>>1 ;
            }
        }
        return bitCount;
    }

    public static int playOneEpoch(){
        int arrNum = scanner.nextInt();
        int [] arr = new int[arrNum];
        int xor = 0; // 用于计算X1^X2^……^Xn
        for (int j = 0; j < arrNum; j++) {
            arr[j]= scanner.nextInt();
            xor ^= arr[j];
        }
        if(xor==0)return 0;

        // 统计所有位的1的个数
        int[] bitCountOf1 = getBitCount(arr);
        // 从高位到低位进行判断
        for (int i = bitCountOf1.length-1; i >=0; i--) {
            if(bitCountOf1[i]==0 || bitCountOf1[i]%2==0){//无需进行处理，对结果没有影响
                continue;
            }else if(bitCountOf1[i]==1){//先手Alice选中直接获胜
                return 1;
            }else if(bitCountOf1[i]%2==1){ // 该位只有奇数个1，则拿到最后一个1的一方获胜
                if(arrNum%2==0){//总数为偶数 后手有最后一个1的支配权，后手胜利
                    return -1;
                }else{//总数为奇数 先手有最后一个1的支配权，先手胜利
                    return 1;
                }
            }
        }
        return 0;
    }
    
    public static void main(String[] args) {
        int T = scanner.nextInt();
        int[] res = new int[T];

        for (int i = 0; i < T; i++) {
            res[i] = playOneEpoch();
        }

        for (int i = 0; i < T; i++) {
            System.out.println(res[i]);
        }
    }
}

2.3 提交结果

评测点序号	评测结果	得分	CPU使用	内存使用	下载评测数据
1	正确	20.00	656ms	94.55MB	输入输出
2	正确	20.00	687ms	95.83MB	VIP特权
3	正确	20.00	734ms	95.92MB	VIP特权
4	正确	20.00	500ms	92.60MB	VIP特权
5	正确	20.00	406ms	92.29MB	VIP特权