好的网站制作网站,营销策划思路及方案,宿迁房产网查备案,淘宝网站建设情况大家好#xff0c;我是晴天学长#xff0c;贡献度的题#xff0c;找到技巧非常重要#xff0c;需要的小伙伴可以关注支持一下哦#xff01;后续会继续更新的。#x1f4aa;#x1f4aa;#x1f4aa; 1) .字典树考试 字典树考试 问题描述 蓝桥学院最近教学了字典树这一数…大家好我是晴天学长贡献度的题找到技巧非常重要需要的小伙伴可以关注支持一下哦后续会继续更新的。 1) .字典树考试 字典树考试 问题描述 蓝桥学院最近教学了字典树这一数据结构小蓝是全班的第一名他不仅掌握了普通字典树还自学了01字典树的使用。 为了展示自己的能力他向全班同学出了以下问题: 给定一个长度为N的数组A你能否求出表达式〉1二i1f(A; Aj)的值﹖其中f(a)表示α二进制表示中1的个数表示按位与运算。 然而这个问题很快就被小桥同学迅速解决了尽管她明明没有学过01字典树。现在小蓝想让你也尝试解决这个问题。 输入格式 第—行输入—个整数N(1N2 ×105)表示数组A的长度。 第二行输入N个整数A1,Ag,A3,.…· ,Ay表示数组A(0A;109). 输出格式 输出—个整数表示答案。 2) .算法思路
1.用一个大于32位的数组存每个数字的个数用上前缀和。 2.然后遍历数组当前位为1与前缀和数组cnt[i]进行计算。要注意的是 1cut[i]–,为什么因为两个1按位与才为1第二个原因是因为不减的话会有重复计算。 3.算法步骤
从用户输入中读取一个整数n。 创建一个大小为n10的整数数组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[n10];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 (t1) {cnt[j];}}}long ans0;for (int i 1; i n; i) {int k N[i];for (int j 0; j 32; j) {if (((kj)1)1) {cnt[j]--;anscnt[j];}}}System.out.println(ans);}}
