蓝桥杯算法心得——字典树考试(贡献度+前缀和)
大家好,我是晴天学长,贡献度的题,找到技巧非常重要,需要的小伙伴可以关注支持一下哦!后续会继续更新的。💪💪💪
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);}}
相关文章:
蓝桥杯算法心得——字典树考试(贡献度+前缀和)
大家好,我是晴天学长,贡献度的题,找到技巧非常重要,需要的小伙伴可以关注支持一下哦!后续会继续更新的。💪💪💪 1) .字典树考试 字典树考试 问题描述 蓝桥学院最近教学了字典树这一数…...
Linux下Qt生成程序崩溃文件
文章目录 1.背景2.Qt编译生成程序2.1.profile模式的本质 3.执行程序,得到core文件4.代码定位4.1.直接使用gdb4.2.使用QtCreator 5.总结6.题外话6.1.profile模式和debug模式的区别 1.背景 在使用Qt时,假如在windows,当软件崩溃时,…...
Go语言中测试和性能
1. 测试:软件开发最重要的方面 测试软件程序可能是软件开发人员能够做的最重要的事情。通过测试代码的功能,开发人员能够在很大程度上确定程序是有效的。另外,每次修改代码后,开发人员都可运行测试,确认没有引入Bug和衰退。通过测试软件,还能够让软件工程师确认程序按期望…...
回归预测 | Matlab基于CPO-GPR基于冠豪猪算法优化高斯过程回归的多输入单输出回归预测
回归预测 | Matlab基于CPO-GPR基于冠豪猪算法优化高斯过程回归的多输入单输出回归预测 目录 回归预测 | Matlab基于CPO-GPR基于冠豪猪算法优化高斯过程回归的多输入单输出回归预测预测效果基本介绍程序设计参考资料 预测效果 基本介绍 Matlab基于CPO-GPR基于冠豪猪算法优化高斯…...
python 日期字符串转换为指定格式的日期
在Python编程中,日期处理是一个常见的任务。我们经常需要将日期字符串转换为Python的日期对象,以便进行日期的计算、比较或其他操作。同时,为了满足不同的需求,我们还需要将日期对象转换为指定格式的日期字符串。本文将详细介绍如…...
day03-Docker
1.初识 Docker 1.1.什么是 Docker 1.1.1.应用部署的环境问题 大型项目组件较多,运行环境也较为复杂,部署时会碰到一些问题: 依赖关系复杂,容易出现兼容性问题开发、测试、生产环境有差异 例如一个项目中,部署时需要依…...
C语言函数实现冒泡排序
前言 今天我们来看看怎么使用函数的方式实现冒泡排序吧,我们以一个数组为例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分位数-卷积-双向长短期记忆神经网络-核密度估计-回归时间序列区间预测 模型输出展示: (图中是只设置了20次迭代的预测结果,宽度较宽,可自行修改迭代参数,获取更窄的预测区间) 注&am…...
Java 分支结构 - if…else/switch
顺序结构只能顺序执行,不能进行判断和选择,因此需要分支结构。 Java有两种分支结构: if语句switch语句 if语句 一个if语句包含一个布尔表达式和一条或多条语句。 语法 If 语句的用语法如下: if(布尔表达式) {//如果布尔表达…...
【Unity每日一记】如何从0到1将特效图集制作成一个特效
👨💻个人主页:元宇宙-秩沅 👨💻 hallo 欢迎 点赞👍 收藏⭐ 留言📝 加关注✅! 👨💻 本文由 秩沅 原创 👨💻 收录于专栏:Uni…...
磁力链接的示例与解释
磁力链接(Magnet URI scheme)是一种特殊类型的统一资源标识符(URI),它包含了通过特定散列函数(如SHA-1)得到的文件内容的散列值,而不是基于位置或名称的引用。这使得磁力链接成为在分…...
云存储中常用的相同子策略的高效、安全的基于属性的访问控制的论文阅读
参考文献为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的调优 版权声明 本博客的内容基于我个人学习黑马程序员课程的学习笔记整理而成。我特此声明,所有版权属于黑马…...
第十四届蓝桥杯省赛大学C组(C/C++)三国游戏
原题链接:三国游戏 小蓝正在玩一款游戏。 游戏中魏蜀吴三个国家各自拥有一定数量的士兵 X,Y,Z(一开始可以认为都为 0)。 游戏有 n 个可能会发生的事件,每个事件之间相互独立且最多只会发生一次,当第 i 个事件发生时…...
java之static详细总结
static也叫静态,可以修饰成员变量、成员方法。 成员变量 按照有无static分为两种: 类变量:static修饰,属于类,与类一起加载一次,在内存中只有一份,会被类的全部对象共享实例变量(…...
RabbitMQ3.13.x之六_RabbitMQ使用场景
RabbitMQ3.13.x之六_RabbitMQ使用场景 文章目录 RabbitMQ3.13.x之六_RabbitMQ使用场景1. 为什么选择 RabbitMQ?1. 可互操作2. 灵活3. 可靠 2. 常见用户案例1. 服务解耦2. 远程过程调用3. 流处理4. 物联网 1. 为什么选择 RabbitMQ? RabbitMQ 是一个可靠且…...
C++ 类和对象(初篇)
类的引入 C语言中,结构体中只能定义变量,在C中,结构体内不仅可以定义变量,也可以定义函数。 而为了区分C和C我们将结构体重新命名成class去定义 类的定义 标准格式: class className {// 类体:由成员函…...
微软推出GPT-4 Turbo优先使用权:Copilot for Microsoft 365商业用户享受无限制对话及增强图像生成能力
每周跟踪AI热点新闻动向和震撼发展 想要探索生成式人工智能的前沿进展吗?订阅我们的简报,深入解析最新的技术突破、实际应用案例和未来的趋势。与全球数同行一同,从行业内部的深度分析和实用指南中受益。不要错过这个机会,成为AI领…...
Spring Boot Actuator
概述 Spring Boot Actuator是Spring Boot的一个功能模块,用于提供生产环境中常见的监控和管理功能。它提供了各种端点(endpoints),可以用于监视应用程序的运行状况、收集应用程序的指标数据以及与应用程序进行交互。 以下是Spri…...
我与C++的爱恋:类与对象(一)
🔥个人主页:guoguoqiang. 🔥专栏:我与C的爱恋 C语言是面向过程的,关注的是过程,分析出求解问题的步骤,通过函数调用逐步解决问题。 C是基于面向对象的,关注的是对象&…...
os模块篇(十八)
文章目录 os._exit(n)os.forkpty()os.kill(pid, sig, /)os.killpg(pgid, sig, /)os.nice(increment, /)os.pidfd_open(pid, flags0)os.plock(op, /)os.popen(cmd, moder, buffering-1)os.posix_spawn(path, argv, env, *, file_actionsNone, setpgroupNone, resetidsFalse, set…...
Oracle 数据库工作中常用知识点:sql语法与常用函数
.to_date()函数 to_date函数是Oracle特有的函数,该函数用来做日期转换。 举例: SELECT TO_DATE(‘2006-05-01 19:25:34’, ‘YYYY-MM-DD HH24:MI:SS’) FROM DUAL 日期格式: YYYY、YYY、YY 分别代表4位、3位、2位的数字年 …...
软件工程
开发模型 瀑布模型 用于结构化模型开发 适用需求明确或者二次开发 原型模型 适用需求不明确 演化模型 增量模型 适用需求不明确 先做一块,再做一块,这样不断的对核心功能的审视,降低风险 螺旋模型 由多个模型组合成 适用需求不明…...
【御控物联】JavaScript JSON结构转换(17):数组To对象——键值互换属性重组
文章目录 一、JSON结构转换是什么?二、核心构件之转换映射三、案例之《JSON数组 To JSON对象》四、代码实现五、在线转换工具六、技术资料 一、JSON结构转换是什么? JSON结构转换指的是将一个JSON对象或JSON数组按照一定规则进行重组、筛选、映射或转换…...
免注册,ChatGPT可即时访问了!
AI又有啥进展?一起看看吧 Apple进军个人家用机器人 Apple在放弃自动驾驶汽车项目并推出混合现实头显后,正在进军个人机器人领域,处于开发家用环境机器人的早期阶段 报告中提到了两种可能的机器人设计。一种是移动机器人,可以跟…...
探索未来游戏:生成式人工智能AI如何重塑你的游戏世界?
生成式人工智能(Generative AI)正以前所未有的速度改变着各行各业的运作模式。其中,游戏产业作为科技应用的前沿阵地,正经历着前所未有的变革。本文将探讨生成式人工智能如何重塑游戏产业,以及这一变革背后的深远影响。…...
ubuntu23设置kibana后台启动服务
要在Ubuntu 23系统中设置Kibana作为系统服务,以便能够通过systemd管理其启动、停止、重启以及设置开机自动启动,可以按照以下步骤操作: 1. 创建Kibana systemd服务单元 创建一个名为kibana.service的文件在 /etc/systemd/system/ 目录下&am…...
身份证实名制、C#身份核验代码示例、身份证查询
在以前,企业采用人工审核的方式对线上用户进行身份信息真伪的核验,在用户上传身份信息后,人工进行后台审核,虽能满足企业对用户实名认证的需求,但效率慢、耗时长,且存在一定的人为误差,对高度PS…...
【leetcode面试经典150题】15.分发糖果(C++)
【leetcode面试经典150题】专栏系列将为准备暑期实习生以及秋招的同学们提高在面试时的经典面试算法题的思路和想法。本专栏将以一题多解和精简算法思路为主,题解使用C语言。(若有使用其他语言的同学也可了解题解思路,本质上语法内容一致&…...
Elasticsearch如何选择版本
不同版本的ES差异非常大,包括不局限于ES语法、架构、API、集群搭建等等。这些差异足以导致不同版本是否能满足你的业务场景以及后续开发维护成本等各种问题。 先说结论,以个人实践经验及综合考虑推荐使用 7.x 版本中的 7.10版本 ES版本对比 以下是通过…...
正品率最高的购物网站/网络营销的宏观环境
本文实例为大家分享了Python爬取网络图片的具体代码,供大家参考,具体内容如下 代码: import urllib import urllib.request import re #打开网页,下载器 def open_html ( url): requireurllib.request.Request(url) reponseurllib…...
网站开发实验报告/郑州网络推广平台有哪些
为什么80%的码农都做不了架构师?>>> 之前讲过虚拟机中的堆,他是整个内存模型中占用最大的一部分,而且不是连续的。当有需要分配内存的时候,一般有两个方法分配,指针碰撞和空闲列表。该部分的内存回收是由虚…...
做网站 框架/产品推广方式有哪些
Hello, I’m Shendi 最近需要使用到搜索框,搜索框输入内容后出现提示内容,于是选用了 weui 的搜索框 对于 DOM 的操作,我使用的 vue,没有用到 vue 的也可以自己使用js手动循环生成 DOM效果 引入库 <!-- weui --> <lin…...
网站description是指什么/太原网站建设优化
文件过大时,mac 无法将xxx.zip解压缩到下载(错误 - 无此文件或目录) 此时可以修改zip后缀为rar, 使用Unarchiver解压。...
南京雨花台区做网站/佛山网站建设
LeetCode 111:二叉树的最小深度 ⭕️ 解题思路: 分情况讨论,还是利用通过递归函数返回的过程来完成最小深度的计算 ❌ 代码部分: /*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* …...
Wordpress建站用什么系统/网站手机版排名seo
MySQL常用操作之备份表结构及表数据场景描述报错信息原因分析解决方案参考链接场景描述 简介 生产上进行数据变更时,经常担心会对已有数据误操作,一般会先进行备份,这里记录一次MySQL备份失败解决过程。 报错信息 描述 -- 备份语句CREATE T…...