蓝桥杯算法心得——字典树考试（贡献度+前缀和）

大家好，我是晴天学长，贡献度的题，找到技巧非常重要，需要的小伙伴可以关注支持一下哦！后续会继续更新的。💪💪💪

---

1) .字典树考试

字典树考试
问题描述
蓝桥学院最近教学了字典树这一数据结构，小蓝是全班的第一名，他不仅掌握了普通字典树，还自学了01字典树的使用。
为了展示自己的能力，他向全班同学出了以下问题:
给定一个长度为N的数组A，你能否求出表达式〉1二=i+1f(A; & Aj)的值﹖其中，f(a)表示α二进制表示中1的个数，&表示按位与运算。
然而，这个问题很快就被小桥同学迅速解决了，尽管她明明没有学过01字典树。现在小蓝想让你也尝试解决这个问题。
输入格式
第—行输入—个整数N(1<N<2 ×105)表示数组A的长度。
第二行输入N个整数A1,Ag,A3,.…· ,Ay表示数组A(0<A;<109).
输出格式
输出—个整数表示答案。

---

2) .算法思路

1.用一个大于32位的数组存每个数字的个数，用上前缀和。
2.然后遍历数组，当前位为1，与前缀和数组cnt[i]进行计算。要注意的是
（1）cut[i]–,为什么，因为两个1按位与才为1，第二个原因是因为不减的话，会有重复计算。

---

3）.算法步骤

从用户输入中读取一个整数n。
创建一个大小为n+10的整数数组N。
创建一个大小为40的整数数组cnt，用来记录每个位的计数。
使用循环，从1到n依次读取N数组的元素，并进行以下操作：
a. 将当前元素存储到N数组的对应位置。
b. 使用嵌套循环，从0到31遍历当前元素的每一位，并进行以下操作：
i. 计算当前位是否为1，方式是将当前元素右移j位并与1进行按位与运算，如果结果为1，则当前位为1。
ii. 如果当前位为1，则将对应位的计数cnt[j]加1。
创建一个变量ans，用来存储最终结果，初始值为0。
使用循环，从1到n依次遍历N数组的元素，并进行以下操作：
a. 将当前元素赋值给变量k。
b. 使用嵌套循环，从0到31遍历当前元素的每一位，并进行以下操作：
i. 判断当前位是否为1，方式是将当前元素右移j位并与1进行按位与运算，如果结果为1，则当前位为1。
ii. 如果当前位为1，则将对应位的计数cnt[j]减1，并将cnt[j]加到ans中。
输出最终结果ans。

---

4）. 代码实例

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner  scanner = new Scanner(System.in);int n = scanner.nextInt();int[] N = new int[n+10];int[] cnt = new int[40];for (int i = 1; i <= n; i++) {N[i] = scanner.nextInt();for (int j = 0; j < 32; j++) {int t = (N[i]>>j)&1;if (t==1) {cnt[j]++;}}}long ans=0;for (int i = 1; i <=n; i++) {int  k = N[i];for (int j = 0; j < 32; j++) {if (((k>>j)&1)==1) {cnt[j]--;ans+=cnt[j];}}}System.out.println(ans);}}

---