当前位置：首页 > article >正文

第十二届蓝桥杯异或数列

article 2025/3/9 22:42:04

原题：

https://www.acwing.com/problem/content/3424/

题目大意：

A、B两人的数初始值均为0，他们轮流从X数组中取数，可以将该数与自己的数或对方的数进行异或操作，A先手，当X中的数被取完的时候谁的数大谁赢。两人每次的操作都是最优的。判断最后是A赢还是B赢还是平局。

一般博弈的问题测试数据范围都比较大，所以肯定要找规律，找到必胜态和必败态。

第一次做这种博弈问题，花了很长时间理解，所以记录一下/(ㄒoㄒ)/~~。

1. 怎样比较最终两人的数字的大小？

比较a、b两个二进制数的大小，可以从高位向低位逐位比较，当发现某一位数字不一样时，就可以判断a、b两数的大小关系。

所以本题要对a、b最后的结果从高到低逐位比较。

由于a, b初始均为0，0与任何数异或结果还是这个数，所以最终a, b都是X中的一些数异或起来的结果，而对两个二进制数的某个对应位进行异或操作时不会影响到其他位，所以可以不管a, b最后的值具体是多少，直接从高到低逐位比较X数组中每个数。

例如，假设X = [1, 2, 3, 4, 5]，就直接像下面这样从高到低一位一位地比较，直到找到能分出胜负的那一位：

2. 怎样分出胜负？

我们需要一位一位地看能不能分胜负。

异或运算时，0不能改变数，只有1才能改变。

以上面为例，这五个数中最高位有两个1，两个1能不能分胜负呢？

看上面的这张图，初始时a，b的这一位都是0，当有一个人选了1，a或b的这一位就会发生改变(把1异或给自己或者对方)，从上图的(0，0)出发，沿着边走两次，要么还是(0, 0)，要么变成(1, 1)，所以这一位不能分出胜负。

其实我们也可以进一步看出，当这一位1有偶数个时，都不能分出胜负(从(0, 0)开始沿着边走偶数次还是走到这两位相同的地方)

那当这一位的1有奇数个时：由于偶数个1的时候是平局，所以谁拿到最后一个1，谁就会赢(因为两人都采用最佳策略，所以可以根据现在的状态决定这个1给自己还是对方)。而谁能拿到最后那个1取决于0的个数：

情况1：0有偶数个，例如：0 0 1 1 1，那么先手必胜，因为只要先拿走一个1，接下来后手就进入了一个双偶的局面，不管后手拿什么都拿和他一样的就行，都能拿到最后一个1

情况2：0有奇数个，例如：0 0 0 1 1 1，那么后手必胜，不管先手拿什么，都拿和他相反的，接下来就和上面类似，先手进入了双偶的局面，后手只要一直跟先手拿一致的就能赢

还要注意一个特殊情况就是1只有一个，这时候不管0有几个显然先手必胜。

总结一下：

若某一位上1一共有偶数个，则这一位分不出胜负，继续看下一位；

若某一位上1一共有奇数个，

当1有一个时，先手必胜；

当1不止一个时，若0有偶数个，则先手必胜；若0有奇数个，则后手必胜。

3. 用一个数组bits统计X中的数每一位上1的总个数

分析了胜负情况后，很自然地就要统计出每一位上所有Xi的1的个数，例如上面X = [1，2，3，4，5]的例子中，bits[0] = 3, bits[1] = 2, bits[3] = 2（从低位到高位统计）。

先定义一个函数处理单个数，之后再一个一个地处理，这段代码如下：

def get_bit(num):  # 处理单个数哪一位是1，并累加到bits里
  idx = 0  # 指示bits数组的索引
  while num:
      bit = num & 1  # num和1与一下，就能获得最低位是多少
      bits[idx] += bit # 这一位的值累加到bits数组对应的位上，可以得到1的个数
      num >>= 1  # 右移一位，处理num的更高一位
      idx += 1   # 索引加1

题目中Xi最大是2的20次方，也就是最多用21位表示，所以bits初始化为[0] * 21。

最后是我的ac code:

def get_bit(num):
    idx = 0
    while num:
        bit = num & 1
        bits[idx] += bit
        num >>= 1
        idx += 1

t = int(input())
for _ in range(t):
    tmp = list(map(int, input().split()))
    len_x = tmp[0]
    x = tmp[1:]
    bits = [0] * 21
    for xi in x:   # 统计Xi中的数每一位总共有几个1
        get_bit(xi)
    ans = 0
    for i in range(20, -1, -1):  # 从高到低比较，所以要倒序遍历
        if bits[i] % 2 == 0:  # 有偶数个1
            continue
        else:       # 有奇数个1
            if bits[i] == 1:  # 有1个1
                ans = 1
            elif (len_x - bits[i]) % 2 == 0: # 有偶数个0
                ans = 1
            elif (len_x - bits[i]) % 2 == 1: # 有奇数个0
                ans = -1
            break
    print(ans)

思路参考：http://【寒假每日一题07 | 【蓝桥杯省赛】异或数列 StarryCoding.109】https://www.bilibili.com/video/BV1wr421s73c?vd_source=9c4a17fd87c2018d071c433adb917522

查看全文

http://www.kler.cn/a/577753.html