【蓝桥杯】异或数组_蓝桥杯选数异或

 问题描述

首先，对Py的位运算进行总结：

这题要用到的有异或、位移和与。

1^1 == 0
1^0 == 1
0^1 == 1
0^0 == 0

1.最优策略

看完题目，第一个疑问就是：什么是最优策略？

如果在十进制维度看，很难想到什么是最优策略。题目暗示很明显，需要转化成二进制按位看。

由于异或运算的特质，以及希望运算结果最大的前提，那么最优策略就是保持二进制数高位为1。

如果持有的数字某位为0，那么就希望1与之异或，得到1，来使其增大。

如果持有的数字某位为1，那么就希望0与之异或，来保持大小，防止变成0，减小。

知道目标，就需要找其中规律，即什么时候能达到该策略。

2.可能性

在一次交锋中，若：

仅有一个不为0的数，那么先手与之异或，必大于0。【output=1】

两个数，那么先手选较大值，后手无论将较小值给自己或先手都会输，除非两个数一样，可以消除，那就是平局。

多于两个数，情况就变得复杂了。需要考虑最高位的个数，对更高位的1的争夺直接影响着胜负。

三个数，若最高位仅有1个，先手选最大值，后手无法用1消去最高位的1，先手胜。【output=1】

三个数，若最高位有2个，先手选其一，后手必须将其消去，在最高位无法判断，只能转去下一位判断，最好情况是平局

三个数，最高位有3个，先手必赢。

在最高位无法判断的情况下，开始比较次高位，依次类推。

若最高位再加一个数字，有4个，则：

最高位只有1个，Alice赢。

最高位有2个，在该位无法判断，转向判断下位。

最高位有3个，先手取高位之一，则后手取剩下的高位为0者，先手只能消去自己的1，或给对方1，那么之后还是会被消去1，或者被后手综合评价后输掉。先手取高位为0者，后手取1，先手取1或给对方消去，后手都能够消去先手的1或给自己加上1，先手仍旧输。因此，Alice在无法平局的情况下，必输。

最高位有4个，无法判断，转下一位。

3.平局

怎么考虑平局？

由于平局是Alice和Bob在每次选择了最优解后得出的，所以可以逻辑上理解一下：如果平局，那么一定是只能平局。那么只有一种可能：就是所有的数字异或后，结果是0。

因为，若不是0，这多出来的部分被其中一方吸收了，就无法达成平局了。

即使双方最后是相同数字（非0），平局的，那也证明了，经过有限次运算，是可以达到双方都是0 的。

4.思路总结

先通过异或所有的数考虑平局。

在不是平局的前提下，

最高位有1个：Alice胜

最高位为偶：转到下一位

最高位为奇：剩下数量为偶，Alice胜。剩下数量为奇，Alice输。

5.代码

turn = int(input())
 
def judge(info):
    #get info
    temp = list(map(int,info.split()))
    # len of arr
    n = temp[0]
    if n==0:return 0
    # list array
    arr = temp[1:len(temp)]
    num_max = max(arr)
    # check if its a draw
 
    draw = 0
    for i in arr:
        draw ^= i
    if draw == 0:
        return draw
 
    #get the num of the top
 
    top = 1
    while top<num_max:
        top <<= 1
 
    while top >=1 :
        top_1 = 0
        top_0 = 0
        for num in arr:
            if num&top != 0:
                top_1 += 1
            else:
                top_0 += 1
 
        # print("top_1",top_1)
        # print("top_0",top_0)
        if top_1%2 ==1:
            if top_0%2 == 1 and top_1>1:
                return -1
            else:
                return 1
            break
        top >>= 1
 
if turn==0:
    print(0)
else:
    for i in range(turn):
        print(judge(input()))