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

jupiter
2022-03-17 / 0 评论 / 550 阅读 / 正在检测是否收录...
温馨提示:
本文最后更新于2022年03月17日,已超过964天没有更新,若内容或图片失效,请留言反馈。

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
0
1
1

【评测用例规模与约定】

对于所有评测用例,$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.00656ms94.55MB输入 输出
2正确20.00687ms95.83MBVIP特权
3正确20.00734ms95.92MBVIP特权
4正确20.00500ms92.60MBVIP特权
5正确20.00406ms92.29MBVIP特权

参考资料

  1. 异或数列(c++位运算)
  2. 蓝桥杯2021年第十二届省赛-异或数列
  3. http://lx.lanqiao.cn/detail.page?submitid=7217417
  4. 第十二届蓝桥杯大赛软件赛省赛 Python 大学 A 组 试题
0

评论 (0)

打卡
取消