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

【蓝桥杯每日一题】推导部分和——带权并查集

news 来源：原创 2025/6/23 22:40:35

推导部分和

2024-12-11 蓝桥杯每日一题推导部分和带权并查集

题目大意

对于一个长度为 ( N ) 的整数数列 $A_1, A_2, \cdots, A_N$ ，小蓝想知道下标 ( l ) 到 ( r ) 的部分和 $\sum_{i=l}^r A_i = A_l + A_{l+1} + \cdots + A_r$ 是多少？

然而，小蓝并不知道数列中每个数的值是多少，他只知道它的 ( M ) 个部分和的值。其中第 ( i ) 个部分和是下标 $l_i$ 到 $r_i$ 的部分和 $\sum_{j=l_i}^{r_i} A_j = A_{l_i} + A_{l_i+1} + \cdots + A_{r_i}$ ，值是 $S_i$ 。

解题思路

这个题的思维难度有点大，但是实现来很容易，只要理解带权并查集这一概念即可。

先看这个权值是怎么带上的，d 数组就是代表每一个值到根节点的一个距离，然而当 l 和 r在同一个连通块中的时候，之间的距离就是 d[r] - d[l-1] 的值。

每一个连通块代表着是那些可以通过边界值相连的区间的总和，在合并的过程中会发生如下图的数值变化，如图所示 d[l-1] 的值将会在find函数中通过更新父节点的时候更新成 l-1 到根节点的距离，这时候显然l 和 r 之间的距离就是d[r] - d[l-1]

在这里插入图片描述

Accepted

#include <iostream>using namespace std;const int N = 100010;
typedef long long ll;
ll n,m,q;
ll d[N],p[N];ll find(int x) {if(p[x] != x) {int t = find(p[x]);d[x] += d[p[x]];p[x] = t;}return p[x];
}int main() {cin>>n>>m>>q;for(int i = 1;i <= n;i++) p[i] = i;ll l,r,s;while(m--) {cin>>l>>r>>s;ll pl = find(l-1),pr = find(r);// 直接合并p[pl] = pr;d[pl] = d[r] - d[l-1] - s;}while(q--) {cin>>l>>r;ll pl = find(l-1),pr = find(r);if(pl != pr) cout<<"UNKNOWN"<<endl;else cout<<d[r] - d[l-1]<<endl;}return 0;
}

思考

这个题的思维难度确实高，主要就是带权并查集的使用，得多想想。

备注

想要一起备赛的同学可以评论区留言！！！

【蓝桥杯每日一题】推导部分和——带权并查集

推导部分和 2024-12-11 蓝桥杯每日一题推导部分和带权并查集题目大意对于一个长度为 ( N ) 的整数数列 A 1 , A 2 , ⋯ , A N A_1, A_2, \cdots, A_N A1,A2,⋯,AN ，小蓝想知道下标 ( l ) 到 ( r ) 的部分和 ∑ i l r A i A l A l 1 ⋯ A r \sum_{…...

编程日记 2025/6/23 22:40:35

【Linux服务器nginx前端部署详解】ubantu22.04，前端Vue项目dist打包

本文主要讲一下在Linux系统环境下（以ubantu22.04为例），如何用nginx部署前端Vue项目打包的dist静态资源。有些具体的命令就不展开讲了，可以自行查看其他博主的文章，我主要讲整体的步骤和思路。一、ubantu系统安装ngin…...

编程日记 2025/6/4 8:22:09

Groovy 语法快速入门

文章目录 1. Groovy 的特点2. 基本语法2.1. 变量2.2. 字符串2.3. 条件语句 3. 集合操作3.1. 列表（List）3.2. 映射（Map） 4. 循环语句4.1. 普通循环4.2. 闭包遍历 5. 方法定义6. 闭包（Closure）6.1. 定义与调用…...

编程日记 2025/6/20 16:01:25

vue3 Textarea在光标定位处，增加一定的关键词。

1、经常碰到这种情况，有一些是系统预留的关键词可以选择，当用户把光标定位到什么地方，我们就要在这个位置插入指定的关键词。 2、光标定位在今天的前面，那么我们点击【逗号】按钮，在这个位置增加一个逗号。 3、代码&…...

编程日记 2025/6/24 3:32:12

硬件设计-电源轨噪声对时钟抖动的影响

目录定义实际案例总结定义首先了解抖动的定义，在ITU-T G.701中有关抖动的定义如下： 数字信号重要瞬间相对于其理想时间位置的短期非累积变化。抖动是时钟或数据信号时序的短期时域变化。抖动包括信号周期、频率、相位、占空比或其他一些定时特…...

编程日记 2025/6/23 15:09:15

Graspness 端到端抓取点估计 | 环境搭建 | 模型推理测试

在复杂场景中实现抓取检测，Graspness是一种端到端的方法； 输入点云数据，输出抓取角度、抓取深度、夹具宽度等信息。开源地址：https://github.com/rhett-chen/graspness_implementation?tabreadme-ov-file 论文地址&#xff1…...

编程日记 2025/6/23 15:58:18

大模型呼入机器人的缺点是什么？(转)

大模型呼入机器人的缺点是什么？(转) 原作者：开源呼叫中心FreeIPCC，其Github：https://github.com/FreeIPCC/FreeIPCC 大模型呼入机器人在提供高效、自动化服务的同时，也存在一些缺点。以下是对其缺点的详细归纳&#…...

编程日记 2025/6/23 8:12:53

ASP.NET ｜日常开发中连接Oracle数据库详解

ASP.NET ｜日常开发中连接Oracle数据库详解前言一、安装和配置 Oracle 数据访问组件1.1 安装ODP.NET（Oracle Data Provider for.NET）：1.2 引用相关程序集： 二、配置连接字符串2.1 连接字符串的基本组成部分&#xff1a…...

编程日记 2025/6/23 7:05:13

Kaggler日志-Day4

进度24/12/14 昨日复盘： Pandas课程完成 Intermediate Mechine Learning2/7 今日记录： Intermediate Mechine Learning之类型变量读两篇讲解如何提问的文章，在提问区里发起一次提问实战：自己从头到尾首先Housing Prices Compe…...

编程日记 2025/6/23 17:01:34

onnx算子的注册详解及案例（完整版）

文章目录 1. 介绍1.1 导出onnx不成功1.2 分析和解决方案2. 案例2.1 Asinh算子注册2.1.1 导出onnx2.1.2 算子注册2.2 自定义算子的注册2.1 直接导出自定义算子2.2 自定义算子的注册并导出2.3 导出带deformable conv 的onnx2.3.1 直接导出deformable conv2.3.2 注册并导出deforma…...

编程日记 2025/6/22 13:28:28

2024生命科学前沿技术

前沿技术是指高技术领域中具有前瞻性、先导性和探索性的重大技术，是未来高技术更新换代和新兴产业发展的重要基础，是国家高技术创新能力的综合体现。选择前沿技术的主要原则一是代表世界高技术前沿的发展方向。二是对国家未来新兴产业的形成和发展具有引…...

编程日记 2025/6/21 11:37:32

游戏引擎学习第47天

仓库: https://gitee.com/mrxiao_com/2d_game 昨天我们花了一点时间来修复一个问题，但基本上是在修复这个问题的过程中，我们决定添加一个功能，那就是在屏幕上控制多个实体。所以如果我有一个手柄，我可以添加另一个角色&#xff0…...

编程日记 2025/6/1 8:11:54

1.编写 Prompt 的原则

一、环境配置使用 OpenAI 的 ChatGPT API，需要有 API_KEY，并安装 OpenAI 库。安装命令：pip install openai 和 pip install zhipuai。配置方法：直接设置 openai.api_key 或通过环境变量设置。二、两个基本原则 2.1 原则一&am…...

编程日记 2025/6/1 16:23:24

【JavaEE】网络（2）

一、网络编程套接字 1.1 基础概念【网络编程】指网络上的主机，通过不同的进程，以编程的方式实现网络通信；当然，我们只要满足进程不同就行，所以即便是同一个主机，只要是不同进程，基于网络来传…...

编程日记 2025/6/20 7:33:13

SAS - Subtractive Port

在SAS（串行连接SCSI，Serial Attached SCSI）协议中，subtractive port 是一种特殊类型的端口，主要用于设备间的路由功能。它的作用是在路径选择过程中充当默认路径，以处理未明确指定路径的请求。以下是它的定…...

编程日记 2025/6/3 15:37:26

Unity3D项目为什么要使用FairyGUI

前言 Unity3D项目选择使用FairyGUI的原因是多方面的，主要涵盖性能优化、设计模式、编辑器支持、跨平台兼容性以及丰富的功能特性。以下是对这些方面的详细解析以及相关的代码实现。对惹，这里有一个游戏开发交流小组，希望大家可以点击进来一…...

编程日记 2025/6/23 19:05:07

Pytest接口自动化测试框架Python自动化测试开发

一、引言在软件开发过程中，接口测试是确保软件各个组件之间数据传输和功能交互正常工作的重要环节。通过接口测试，可以提高软件的整体质量和稳定性。Pytest是一个流行的Python自动化测试框架，提供了丰富的断言方法和灵活的测试组织结构&…...

编程日记 2025/6/2 5:58:53

MySQL追梦旅途之性能优化

1、索引优化索引可以显著加速查询操作，但过多或不适当的索引也会带来负面影响（如增加写入开销）。因此，选择合适的索引至关重要。创建索引： 为经常用于WHERE子句、JOIN条件和ORDER BY排序的列创建索引。 CREATE I…...

编程日记 2025/6/4 7:22:51

数字校园：信息时代的教育新形态

现如今，我们生活在一个信息爆炸的时代，每一天都有海量的信息产生。而在教育领域，也正在经历一场数字化的变革，这就是所谓的“数字校园”。数字校园可不是简单的把课本搬到电脑上那么简单，它其实是一个综合性的平台&…...

编程日记 2025/6/20 5:43:56

数字产业化和产业数字化到底是什么？

“数字产业化”和“产业数字化”在很多官方文件和领导人讲话中都是成对出现的，这两个术语看起来非常相似，但它们作为数字经济的两个重要组成部分，既有联系又有区别。在谈数字产业化和产业数字化之前，我这里需要先给大家介绍一个概…...

编程日记 2025/6/22 18:20:20

每日十题八股-2024年12月14日

1.类加载器有哪些？ 2.双亲委派模型的作用 3.讲一下类加载过程？ 4.讲一下类的加载和双亲委派原则 5.什么是Java里的垃圾回收？如何触发垃圾回收？ 6.判断垃圾的方法有哪些？ 7.垃圾回收算法是什么，是为了解决了…...

编程日记 2025/6/23 20:52:03

大模型呼入机器人有哪些功能特点？(转)

大模型呼入机器人有哪些功能特点？(转) 原作者：开源呼叫中心FreeIPCC，其Github：https://github.com/lihaiya/freeipcc 大模型呼入机器人，作为现代通信技术与人工智能深度融合的产物，正逐渐成为企业提升服务…...

编程日记 2025/5/25 11:56:00

EasyExcel设置表头上面的那种大标题（前端传递来的大标题）

1、首先得先引用easyExcel的版本依赖，我那 <dependency><groupId>com.alibaba</groupId><artifactId>easyexcel</artifactId><version>2.2.6</version> </dependency> 2、然后得弄直接的实体类，&…...

编程日记 2025/6/20 15:49:35

[笔记] 编译LetMeowIn（C++汇编联编程序）过程

文章目录前言过程下载源码vs2017 创建空项目引入编译文件改项目依赖属性改汇编编译属性该项目还需注意编译运行总结前言编译LetMeowin 项目发现是个混编项目，c调用汇编的程序，需要配置一下，特此记录一下过程下载源码首先下载源码…...

编程日记 2025/6/20 16:02:34

（三）机器学习 - 标准差/方差

标准差标准差是统计学中一个非常重要的概念，它用来衡量一组数据的离散程度，即数据点与平均值之间的偏离程度。标准差越大，表示数据点越分散；标准差越小，表示数据点越集中。标准差的计算步骤如下： 计算数…...

编程日记 2025/6/20 1:52:42

笔记：在WPF中InvalidateMeasure，InvalidateArrange，InvalidateVisual，UpdateLayout主要功能

一、目的：简要介绍在WPF中InvalidateMeasure，InvalidateArrange，InvalidateVisual，UpdateLayout主要功能在 WPF 中，InvalidateMeasure、InvalidateArrange、InvalidateVisual 和 UpdateLayout 是用于控制布局系统的四…...

编程日记 2025/6/1 18:20:47

[笔记]Qt下使用SendMessage、PostMessage和接收window消息

1.头文件和库引用首先必须要包含windows.h这个头文件，如果使用一些扩展函数，还需要包含windowsx.h。网上说使用FindWindow要添加头文件winuser.h，不过应该windows.h是自动包含这个依赖的（我没有添加） #include <…...

编程日记 2025/6/20 6:18:50

使用echarts实现3d柱状图+折线图

以下代码有问题请直接问国内直连GPT/Claude HTML 需要注意threeDchart一定要设置宽度高度，不然图不显示,然后echarts版本不要太低，不然也不显示 <div id"threeDchart" class"threeDchart"></div>js set3DBarChart2(dat…...

编程日记 2025/6/20 16:18:33

【经验分享】容器云搭建的知识点

最近忙于备考没关注，有次点进某小黄鱼发现首页出现了我的笔记还被人收费了虽然我也卖了一些资源，但我以交流、交换为主，笔记都是免费给别人看的由于当时刚刚接触写的并不成熟，为了避免更多人花没必要的钱，所以决定公…...

编程日记 2025/6/20 23:04:37

JAVA ｜日常开发中Websocket详解

JAVA ｜日常开发中Websocket详解前言一、Websocket 概述1.1 定义1.2 优势二、Websocket 协议基础2.1 握手过程2.2 消息格式2.3 数据传输方式三、Java 中使用 Websocket3.1 Java WebSocket API（JSR - 356）3.2 第三方库（如 Tyrus&…...

编程日记 2025/6/3 13:27:48

30.攻防世界unserialize3

进入场景解读一下这个类 xctf 中有一个公共属性 $flag ，其值为 111 ，并且定义了一个 __wakeup 魔术方法，当对象被反序列化时会自动调用该方法，该方法会输出 bad requests 并终止程序的执行。 ?code提示了参数 <?php clas…...

编程日记 2025/6/20 6:52:05

IS-IS协议

IS-IS协议介绍 IS-IS（Intermediate System to Intermediate System）协议是一种链路状态的内部网关协议（IGP），用于在同一个自治系统（Autonomous System, AS）内部的路由器之间交换路由信息。IS-I…...

编程日记 2025/6/23 13:35:28

接口文档之swagger、kinife4j的基本使用

1.swagger3的使用： 1.1pom.xml中加入依赖： <dependency><groupId>io.springfox</groupId><artifactId>springfox-boot-starter</artifactId><version>3.0.0</version> </dependency> <!--swagger的…...

编程日记 2025/6/4 4:39:36

Oracle plsqldev1106 安装及TNS配置

Oracle plsqldev1106 安装及TNS配置下载好安装包，直接双击安装点击 I Agree 默认是C盘的，我改了D盘，根据自己实际情况修改这里用默认的for current user 也可以，我选了for all user 点Finish，等待安装完成即可 …...

编程日记 2025/6/21 15:37:49

[数据结构]无向图的深度优先非递归遍历

采用邻接表存储实现无向图的深度优先非递归遍历。输入格式: 先输入两个整数（m,n）（分别表示待创建的图顶点数和边数），之后是m个顶点的信息，再之后是n 条边。输出格式: 对每一组输入，在一行…...

编程日记 2025/6/20 2:02:51

Android后端签到flask迁移到rust的axum的过程-签到性能和便携

本次变更了以下内容: 为了使用之前ip2sta的ip到端点名的python,dic变量,将其存入redis hashset.使用地址/api/ip2dic 手动执行之.并且定义在/station/init,这个每天初始化redis的路径下.在rust axum使用redis 连接池在test中 ip2dic,IP转端点名,转本日此端网址.在前端的人名下…...

编程日记 2025/6/23 19:35:06

Android13开机向导

文章目录前言需求-场景第三方资料说明需求思路按照平台思路从配置上去 feature换个思路，去feature。SimMissingActivity 判断跳过逻辑SetupWizardUtils 判断SIM 、 hasSystemFeature FEATURE_TELEPHONYPackageManager.FEATURE_TELEPHONYApplicationPackageManage…...

编程日记 2025/6/20 2:00:56

泷羽sec学习打卡-brupsuite6暴力破解与验证码识别绕过

声明学习视频来自B站UP主泷羽sec,如涉及侵权马上删除文章笔记的只是方便各位师傅学习知识,以下网站只涉及学习内容,其他的都与本人无关,切莫逾越法律红线,否则后果自负关于brupsuite的那些事儿-验证码绕过以及字典爆破如何利用brpsuite进行验证码绕过呢？1、下…...

编程日记 2025/6/22 12:42:22

vue季度选择器(antd2.0 版本无此控件，单独写一个)

vue季度选择器效果显示效果显示 <template><div><a-popoverplacement"bottom"overlayClassName"season-picker"trigger"click"v-model"showSeason"><template #content><div class"season-picker-b…...

编程日记 2025/6/21 21:46:57

Microsemi Libero使用技巧11——CoreUARTAPB RX管脚分配时不显示

调用串口IP核CoreUARTAPB，并例化到顶层设计，发现UART_RX管脚在进行管脚分配时没有显示出来，最后发现是CoreAPB3总线IP核配置不对导致，改为如下配置后正常。...

编程日记 2025/5/30 19:35:34

回归预测 | MATLAB实现SVM-Adaboost集成学习结合支持向量机多输入单输出回归预测

回归预测 | MATLAB实现SVM-Adaboost集成学习结合支持向量机多输入单输出回归预测目录回归预测 | MATLAB实现SVM-Adaboost集成学习结合支持向量机多输入单输出回归预测基本介绍程序设计基本介绍 SVM-Adaboost集成学习是一种将支持向量机（SVM）与AdaBoost算法相结合的集成学习…...

编程日记 2025/6/1 6:24:22

Keil-MDK开发环境编译后axf自动转换bin格式文件

编译选项添加如下，调用fromelf工具自动完成转换： fromelf --bin -o "$LL.bin" "#L"...

编程日记 2025/5/26 16:43:26

计算机组成原理（五）：程序装载

在计算机组成原理中，程序装载（Program Loading）是指将程序从外存（如磁盘）加载到内存中，并为其运行做好准备的过程。程序装载是实现程序从静态存储状态到动态运行状态的关键环节，涉及地址映射、内…...

编程日记 2025/6/23 19:53:19

开发EDA工具常用的三方开源

EDA软件是制造芯片重要工具，是现在举国的大难题。这个工具难在哪里，几句话说不清，但它确实也有一些非常通用的功能，这些功能依赖一些成熟的轮子，这些轮子，就是三方的开源项目，下面列举一些常用的…...

编程日记 2025/4/20 7:14:05

微信小程序中 crypto-js 加解密全攻略

一、引言在微信小程序开发中，数据的安全至关重要。加解密技术在保护用户数据和应用程序的安全性方面起着关键作用。小程序在与服务器进行数据交互时，面临着数据泄露、篡改等安全风险。为了确保用户信息的安全，选择合适的加解密算法变得尤为…...

编程日记 2025/6/22 13:57:20

Vue2 - 最新实现将多个文件批量导出为ZIP压缩包格式并下载功能，纯前端下载多个文件打包输出成zip格式，vue2将文件批量下载打包成ZIP下载保存本地（后端二进制文件流/base64图片/url

前言 Vue3 版本，请访问这篇文章。在 vue2 | nuxt2 项目开发中，详解实现把多个文件组合成一个ZIP压缩包格式下载到用户本地，将文件批量下载打包成zip格式并自定义压缩包命名名称，vue批量下载文件并导出为压缩包的功能，如何将后端返回的二进制文件流打包成zip格式，支持任…...

编程日记 2025/6/3 6:41:50

The Rise and Potential of Large Language ModelBased Agents:A Survey---摘要、背景、引言

题目基于大语言模型的Agent的兴起与发展前景论文地址：https://arxiv.org/pdf/2309.07864.pdf 项目地址：https:/github.com/WooooDyy./LLM-Agent–Paper-List 摘要长期以来，人类一直在追求等同于或超越人类水平的人工智能(A)，…...

编程日记 2025/6/23 14:54:05