当前位置: 首页 > news >正文

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

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


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);}}

相关文章:

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

大家好&#xff0c;我是晴天学长&#xff0c;贡献度的题&#xff0c;找到技巧非常重要&#xff0c;需要的小伙伴可以关注支持一下哦&#xff01;后续会继续更新的。&#x1f4aa;&#x1f4aa;&#x1f4aa; 1) .字典树考试 字典树考试 问题描述 蓝桥学院最近教学了字典树这一数…...

Linux下Qt生成程序崩溃文件

文章目录 1.背景2.Qt编译生成程序2.1.profile模式的本质 3.执行程序&#xff0c;得到core文件4.代码定位4.1.直接使用gdb4.2.使用QtCreator 5.总结6.题外话6.1.profile模式和debug模式的区别 1.背景 在使用Qt时&#xff0c;假如在windows&#xff0c;当软件崩溃时&#xff0c;…...

Go语言中测试和性能

1. 测试:软件开发最重要的方面 测试软件程序可能是软件开发人员能够做的最重要的事情。通过测试代码的功能,开发人员能够在很大程度上确定程序是有效的。另外,每次修改代码后,开发人员都可运行测试,确认没有引入Bug和衰退。通过测试软件,还能够让软件工程师确认程序按期望…...

回归预测 | Matlab基于CPO-GPR基于冠豪猪算法优化高斯过程回归的多输入单输出回归预测

回归预测 | Matlab基于CPO-GPR基于冠豪猪算法优化高斯过程回归的多输入单输出回归预测 目录 回归预测 | Matlab基于CPO-GPR基于冠豪猪算法优化高斯过程回归的多输入单输出回归预测预测效果基本介绍程序设计参考资料 预测效果 基本介绍 Matlab基于CPO-GPR基于冠豪猪算法优化高斯…...

python 日期字符串转换为指定格式的日期

在Python编程中&#xff0c;日期处理是一个常见的任务。我们经常需要将日期字符串转换为Python的日期对象&#xff0c;以便进行日期的计算、比较或其他操作。同时&#xff0c;为了满足不同的需求&#xff0c;我们还需要将日期对象转换为指定格式的日期字符串。本文将详细介绍如…...

day03-Docker

1.初识 Docker 1.1.什么是 Docker 1.1.1.应用部署的环境问题 大型项目组件较多&#xff0c;运行环境也较为复杂&#xff0c;部署时会碰到一些问题&#xff1a; 依赖关系复杂&#xff0c;容易出现兼容性问题开发、测试、生产环境有差异 例如一个项目中&#xff0c;部署时需要依…...

C语言函数实现冒泡排序

前言 今天我们来看看怎么使用函数的方式实现冒泡排序吧&#xff0c;我们以一个数组为例arr[] {9,8,7,6,5,4,3,2,1,0},我们将这个数组通过冒泡排序的方式让他变为升序吧。 代码实现 #include<stdio.h> void bubble_sort(int arr[], int sz) {int i 0;for (i 0;i < s…...

区间概率预测python|QR-CNN-BiLSTM+KDE分位数-卷积-双向长短期记忆神经网络-时间序列区间概率预测+核密度估计

区间预测python|QR-CNN-BiLSTMKDE分位数-卷积-双向长短期记忆神经网络-核密度估计-回归时间序列区间预测 模型输出展示&#xff1a; (图中是只设置了20次迭代的预测结果&#xff0c;宽度较宽&#xff0c;可自行修改迭代参数&#xff0c;获取更窄的预测区间&#xff09; 注&am…...

Java 分支结构 - if…else/switch

顺序结构只能顺序执行&#xff0c;不能进行判断和选择&#xff0c;因此需要分支结构。 Java有两种分支结构&#xff1a; if语句switch语句 if语句 一个if语句包含一个布尔表达式和一条或多条语句。 语法 If 语句的用语法如下&#xff1a; if(布尔表达式) {//如果布尔表达…...

【Unity每日一记】如何从0到1将特效图集制作成一个特效

&#x1f468;‍&#x1f4bb;个人主页&#xff1a;元宇宙-秩沅 &#x1f468;‍&#x1f4bb; hallo 欢迎 点赞&#x1f44d; 收藏⭐ 留言&#x1f4dd; 加关注✅! &#x1f468;‍&#x1f4bb; 本文由 秩沅 原创 &#x1f468;‍&#x1f4bb; 收录于专栏&#xff1a;Uni…...

磁力链接的示例与解释

磁力链接&#xff08;Magnet URI scheme&#xff09;是一种特殊类型的统一资源标识符&#xff08;URI&#xff09;&#xff0c;它包含了通过特定散列函数&#xff08;如SHA-1&#xff09;得到的文件内容的散列值&#xff0c;而不是基于位置或名称的引用。这使得磁力链接成为在分…...

云存储中常用的相同子策略的高效、安全的基于属性的访问控制的论文阅读

参考文献为2022年发表的Efficient and Secure Attribute-Based Access Control With Identical Sub-Policies Frequently Used in Cloud Storage 动机 ABE是实现在云存储中一种很好的访问控制手段,但是其本身的计算开销导致在实际场景中应用收到限制。本论文研究了一种LSSS矩…...

JVM高级篇之GC

文章目录 版权声明垃圾回收器的技术演进ShenandoahShenandoah GC体验Shenandoah GC循环过程 ZGCZGC简介ZGC的版本更迭ZGC体验&使用ZGC的参数设置ZGC的调优 版权声明 本博客的内容基于我个人学习黑马程序员课程的学习笔记整理而成。我特此声明&#xff0c;所有版权属于黑马…...

第十四届蓝桥杯省赛大学C组(C/C++)三国游戏

原题链接&#xff1a;三国游戏 小蓝正在玩一款游戏。 游戏中魏蜀吴三个国家各自拥有一定数量的士兵 X,Y,Z&#xff08;一开始可以认为都为 0&#xff09;。 游戏有 n 个可能会发生的事件&#xff0c;每个事件之间相互独立且最多只会发生一次&#xff0c;当第 i 个事件发生时…...

java之static详细总结

static也叫静态&#xff0c;可以修饰成员变量、成员方法。 成员变量 按照有无static分为两种&#xff1a; 类变量&#xff1a;static修饰&#xff0c;属于类&#xff0c;与类一起加载一次&#xff0c;在内存中只有一份&#xff0c;会被类的全部对象共享实例变量&#xff08;…...

RabbitMQ3.13.x之六_RabbitMQ使用场景

RabbitMQ3.13.x之六_RabbitMQ使用场景 文章目录 RabbitMQ3.13.x之六_RabbitMQ使用场景1. 为什么选择 RabbitMQ&#xff1f;1. 可互操作2. 灵活3. 可靠 2. 常见用户案例1. 服务解耦2. 远程过程调用3. 流处理4. 物联网 1. 为什么选择 RabbitMQ&#xff1f; RabbitMQ 是一个可靠且…...

C++ 类和对象(初篇)

类的引入 C语言中&#xff0c;结构体中只能定义变量&#xff0c;在C中&#xff0c;结构体内不仅可以定义变量&#xff0c;也可以定义函数。 而为了区分C和C我们将结构体重新命名成class去定义 类的定义 标准格式&#xff1a; class className {// 类体&#xff1a;由成员函…...

微软推出GPT-4 Turbo优先使用权:Copilot for Microsoft 365商业用户享受无限制对话及增强图像生成能力

每周跟踪AI热点新闻动向和震撼发展 想要探索生成式人工智能的前沿进展吗&#xff1f;订阅我们的简报&#xff0c;深入解析最新的技术突破、实际应用案例和未来的趋势。与全球数同行一同&#xff0c;从行业内部的深度分析和实用指南中受益。不要错过这个机会&#xff0c;成为AI领…...

Spring Boot Actuator

概述 Spring Boot Actuator是Spring Boot的一个功能模块&#xff0c;用于提供生产环境中常见的监控和管理功能。它提供了各种端点&#xff08;endpoints&#xff09;&#xff0c;可以用于监视应用程序的运行状况、收集应用程序的指标数据以及与应用程序进行交互。 以下是Spri…...

我与C++的爱恋:类与对象(一)

​ ​ &#x1f525;个人主页&#xff1a;guoguoqiang. &#x1f525;专栏&#xff1a;我与C的爱恋 ​C语言是面向过程的&#xff0c;关注的是过程&#xff0c;分析出求解问题的步骤&#xff0c;通过函数调用逐步解决问题。 C是基于面向对象的&#xff0c;关注的是对象&…...

【大模型RAG】拍照搜题技术架构速览:三层管道、两级检索、兜底大模型

摘要 拍照搜题系统采用“三层管道&#xff08;多模态 OCR → 语义检索 → 答案渲染&#xff09;、两级检索&#xff08;倒排 BM25 向量 HNSW&#xff09;并以大语言模型兜底”的整体框架&#xff1a; 多模态 OCR 层 将题目图片经过超分、去噪、倾斜校正后&#xff0c;分别用…...

Vue记事本应用实现教程

文章目录 1. 项目介绍2. 开发环境准备3. 设计应用界面4. 创建Vue实例和数据模型5. 实现记事本功能5.1 添加新记事项5.2 删除记事项5.3 清空所有记事 6. 添加样式7. 功能扩展&#xff1a;显示创建时间8. 功能扩展&#xff1a;记事项搜索9. 完整代码10. Vue知识点解析10.1 数据绑…...

Vue3 + Element Plus + TypeScript中el-transfer穿梭框组件使用详解及示例

使用详解 Element Plus 的 el-transfer 组件是一个强大的穿梭框组件&#xff0c;常用于在两个集合之间进行数据转移&#xff0c;如权限分配、数据选择等场景。下面我将详细介绍其用法并提供一个完整示例。 核心特性与用法 基本属性 v-model&#xff1a;绑定右侧列表的值&…...

鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院挂号小程序

一、开发准备 ​​环境搭建​​&#xff1a; 安装DevEco Studio 3.0或更高版本配置HarmonyOS SDK申请开发者账号 ​​项目创建​​&#xff1a; File > New > Create Project > Application (选择"Empty Ability") 二、核心功能实现 1. 医院科室展示 /…...

linux arm系统烧录

1、打开瑞芯微程序 2、按住linux arm 的 recover按键 插入电源 3、当瑞芯微检测到有设备 4、松开recover按键 5、选择升级固件 6、点击固件选择本地刷机的linux arm 镜像 7、点击升级 &#xff08;忘了有没有这步了 估计有&#xff09; 刷机程序 和 镜像 就不提供了。要刷的时…...

如何在看板中有效管理突发紧急任务

在看板中有效管理突发紧急任务需要&#xff1a;设立专门的紧急任务通道、重新调整任务优先级、保持适度的WIP&#xff08;Work-in-Progress&#xff09;弹性、优化任务处理流程、提高团队应对突发情况的敏捷性。其中&#xff0c;设立专门的紧急任务通道尤为重要&#xff0c;这能…...

鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个生活电费的缴纳和查询小程序

一、项目初始化与配置 1. 创建项目 ohpm init harmony/utility-payment-app 2. 配置权限 // module.json5 {"requestPermissions": [{"name": "ohos.permission.INTERNET"},{"name": "ohos.permission.GET_NETWORK_INFO"…...

数据库分批入库

今天在工作中&#xff0c;遇到一个问题&#xff0c;就是分批查询的时候&#xff0c;由于批次过大导致出现了一些问题&#xff0c;一下是问题描述和解决方案&#xff1a; 示例&#xff1a; // 假设已有数据列表 dataList 和 PreparedStatement pstmt int batchSize 1000; // …...

【碎碎念】宝可梦 Mesh GO : 基于MESH网络的口袋妖怪 宝可梦GO游戏自组网系统

目录 游戏说明《宝可梦 Mesh GO》 —— 局域宝可梦探索Pokmon GO 类游戏核心理念应用场景Mesh 特性 宝可梦玩法融合设计游戏构想要素1. 地图探索&#xff08;基于物理空间 广播范围&#xff09;2. 野生宝可梦生成与广播3. 对战系统4. 道具与通信5. 延伸玩法 安全性设计 技术选…...

如何在网页里填写 PDF 表格?

有时候&#xff0c;你可能希望用户能在你的网站上填写 PDF 表单。然而&#xff0c;这件事并不简单&#xff0c;因为 PDF 并不是一种原生的网页格式。虽然浏览器可以显示 PDF 文件&#xff0c;但原生并不支持编辑或填写它们。更糟的是&#xff0c;如果你想收集表单数据&#xff…...