题目描述

Alice 和 Bob 正在玩一个异或数列的游戏。初始时，Alice 和 Bob 分别有一个整数 aa 和 bb，初始值均为 0。

有一个给定的长度为 n的公共数列 X1​,X2​,⋯,Xn​​。Alice 和 Bob 轮流操作，Alice 先手，每步以在以下两种选项中选一种：

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

选项 2：从数列中选一个Xi​​​ 给 Bob 的数异或上，或者说令 b变为 b⊕Xi​​​。

每个数 Xi​​ 都只能用一次，当所有 Xi​ 均被使用后（n​​ 轮后）游戏结束。游戏结束时，拥有的数比较大的一方获胜，如果双方数值相同，即为平手。 现在双方都足够聪明，都采用最优策略，请问谁能获胜？

输入描述

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

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

接下来 T 行每行包含一组询问。其中第 i 行的第一个整数 ni​​ 表示数列长度，随后 ni​​ 个整数 X1​,X2​,⋯,Xni​表示数列中的每个数。

输出描述

输出 T​​ 行，依次对应每组询问的答案。 每行包含一个整数 1​​、0或−1分别表示 Alice 胜、平局或败。

输入输出样例

示例 1

输入

复制代码4 1 1 1 0 2 2 1 7 992438 1006399 781139 985280 4729 872779 563580

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

输出

复制代码1 0 1 1

1
2
3
4
1
0
1
1

 思路：

1.第一种情况：sum=0,说明Alice和Bob一定平手

2.第二种情况：sum!=0

计算出最大数的最大数位，假设是第i位，设这些数中有one个数在该为1，zero个数在该位为0

a.如果one是偶数，说明判断不出来，继续枚举下一位。

b.如果one是奇数，one只有一个，一定是Alice赢

                              one>1,zero是偶数，一定是Alice赢

                              one>1,zero是奇数，一定是Bob赢

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
t=int(input())
for i in range(t):
     a=[]
     sum=0
     ma=0
     mp=list(map(int,input().split()))
     for i in range(1,len(mp)):
          a.append(mp[i])
          sum^=mp[i]
          ma=max(ma,mp[i])
     if sum==0:
          print(0)
          continue
     i=1
     while i<ma:
          i<<=1
     while i>0:
          one=0
          zero=0
          for ele in a:
               if ele&i!=0:
                    one+=1
               else:
                    zero+=1
          if one%2==1:
               if zero%2==1 and one>1:
                    print(-1)
               else:
                    print(1)
               break
          i>>=1
     

总结：

1.⊕的规律：

满足交换律，结合律，a异或a=0，a异或0=a

最后

以上就是健忘金针菇最近收集整理的关于蓝桥杯省赛2021 异或数列 python 思路：的全部内容，更多相关蓝桥杯省赛2021内容请搜索靠谱客的其他文章。