蓝桥杯 之 位运算

• 在蓝桥杯当中，当数字很大的时间，我们就得相对应转化一下数字的表现情势
  

异或和之和

异或和之和

   思绪分析：
  

• 由于数据的范围非常大，最大的数字是                                             2                            20                                       2^{20}                  220,以是得思量利用二进制的情势举行表现
  

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

复制代码

• 增补一个通例做法，时间复杂度是                                   o                         (                                   n                            2                                  )                              o(n^2)                  o(n2)
  

1. import os
2. import sys
4. # 请在此输入您的代码
6. # 1,2,3,4,5
8. # 异或和可以用这个前缀和的思想
9. n = int(input())
10. num = list(map(int,input().split()))
11. pre = [0]*(n+1)
13. for i in range(n):
14.   pre[i+1] = pre[i]^num[i]
16. ans = 0
17. for i in range(1,n+1):
19.   for j in range(i,n+1):
21.     tmp = pre[j] ^ pre[i-1]
22.     ans+=tmp
24. print(ans)

复制代码