蓝桥杯 之 位运算

• 在蓝桥杯当中，当数字很大的时候，我们就得相对应转化一下数字的表示形式

异或和之和

异或和之和

思路分析：

• 由于数据的范围十分大，最大的数字是$2^{20}$,所以得考虑使用二进制的形式进行表示

n = int(input())
a = [int(x) for x in input().split()]
ans = 0
for k in range(21):            # 所有a不超过20位zero, one = 1, 0           # 统计第k位的0和1的数量cnt, sum = 0, 0            #cnt用于统计第k位有多少对si⊕sj =1for i in range(n):v = (a[i] >> k) & 1    # 取a[i]的第k位sum ^= v               # 对所有a[i]的第k位做异或得到sum，sum等于0或者1if sum == 0:           # 前缀和为0zero += 1          # 0的数量加1cnt += one         # 这次sum=0，这个sum跟前面等于1的sum异或得1else:                  # 前缀异或为1one += 1           # 1的数量加1cnt += zero        # 这次sum=1，这个sum跟前面等于0的sum异或得1ans += cnt * (1 << k)      # 第k位的异或和相加
print(ans)

• 补充一个常规做法，时间复杂度是$o(n^2)$

import os
import sys# 请在此输入您的代码# 1,2,3,4,5# 异或和可以用这个前缀和的思想
n = int(input())
num = list(map(int,input().split()))
pre = [0]*(n+1)for i in range(n):pre[i+1] = pre[i]^num[i]ans = 0
for i in range(1,n+1):for j in range(i,n+1):tmp = pre[j] ^ pre[i-1]ans+=tmpprint(ans)