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

蓝桥杯冲刺：一维差分

news 来源：原创 2025/9/13 10:34:39

系列文章目录

蓝桥杯系列：一维差分

文章目录

系列文章目录
前言
一、一维差分：
- 差分数组的意义：
二、差分的性质：
- 差分和前缀和的关系
三、一维差分代码实现：
四、典型真题（利用一维差分来实现）
- 这里面为什么只需要累计正差分呢？
- 这里面为什么负差分会包括进去呢？
- 最后的调整（减1）是为什么？
总结

前言

前段时间我们讲了一维前缀和，这次我们来讲讲一维差分，就是跟一维前缀和是两个类似的概念，来快速处理区间加减的问题，下面我们来详细的讲解一下

一、一维差分：

差分数组是一种简单而高效的数据结构，常用于快速处理区间加减的问题。

对于一个长度为n的数组a，我们构造一个差分数组b，其定义为：

b[i] = a[i] - a[i-1],对于i>=2,b[1] = a[1];

从差分数组还原原数组：

通过对差分数组求前缀和可以还原出原数组：

a[i]=k=0∑id[k]

差分数组的意义：

差分数组中的每个元素b[i]表示原数组中a[i]相对于a[i-1]的变化量。

二、差分的性质：

1. 原数组求差分：

从原数组构造差分数组时，每次仅需要O(n)。

2.差分数组求前缀和:

从差分数组恢复原数组，每次查询或还原数组均为O(n)。

3.快速区间修改：

通过调整差分数组可以高效完成原数组的区间操作。

对区间[l,r]的每个元素加上一个值d,只需:

b[l] += d， b[r+1] -= d.

在完成所有修改后，通过对差分数组求前缀和即可得到最终的结果数组。

画图表示：

差分和前缀和的关系：

原数组求前缀和 = 前缀和数组

差分数组求前缀和=原数组

前缀和数组求差分=原数组

原数组求差分=差分数组

三、一维差分代码实现：

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scan = new Scanner(System.in);int T = 1;while (T > 0) {solve(scan);T--;}scan.close();}public static void solve(Scanner scan) {int n = scan.nextInt();int m = scan.nextInt();int[] arr = new int[n + 2];  // 原数组int[] b = new int[n + 2];  // 差分数组arr[0] = 0;b[0] = 0;// 读取原数组for (int i = 1; i <= n; i++) {arr[i] = scan.nextInt();}// 构建差分数组for (int i = 1; i <= n; i++) {b[i] = arr[i] - arr[i - 1];}// 区间更新while (m > 0) {int l = scan.nextInt();int r = scan.nextInt();int d = scan.nextInt();b[l] += d;b[r + 1] -= d;m--;}// 恢复原数组for (int i = 1; i <= n; i++) {b[i] = b[i] + b[i - 1];}// 输出恢复后的数组for (int i = 1; i <= n; i++) {System.out.print(b[i] + " ");}}
}

四、典型真题（利用一维差分来实现）

import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改public class Main {public static void main(String[] args) {Scanner scan = new Scanner(System.in);int n = scan.nextInt();  // 读取nint[] arr = new int[n + 1];  // 创建数组，大小为n+1// 输入数组arrfor (int i = 1; i <= n; i++) {arr[i] = scan.nextInt();  // 读取每个元素}// 创建b数组int[] b = new int[n + 1];b[1] = arr[1];  // b[1]等于arr[1]// 计算b数组的差值for (int i = 2; i <= n; i++) {b[i] = arr[i] - arr[i - 1];}// 计算结果long ans = b[1] - 1;for (int i = 2; i <= n; i++) {if (b[i] > 0) {ans += b[i];  // 如果b[i]大于0，加到答案上}}// 输出结果System.out.println(ans);scan.close();  // 关闭扫描器}
}

这里面我们要注意的是就是不管是什么竞赛都要严格按样例进行输入输出，要不就是逻辑对的样例也是过不去的，所以一定要按照样例进行输入输出。

这里面为什么只需要累计正差分呢？

假设原数组为 a = [a₁, a₂, ..., aₙ]，目标是所有元素变为1。

差分数组 d[i] = a[i] - a[i-1]（假设 a[0] = 0）。
正差分（d[i] > 0）：表示当前元素比前一个元素多出的“层数”。这些层数必须通过新增操作覆盖。
负差分（d[i] ≤ 0）：表示当前元素比前一个元素低或相等。这些层数已经被之前的操作覆盖，无需额外处理。

例子：

数组 [3, 2, 2] 的差分数组为 d = [3, -1, 0]。
- d[1] = 3（必须覆盖的层数）。
- d[2] = -1（已被之前的操作覆盖，无需新增）。
- d[3] = 0（同样被覆盖）。

这里面为什么负差分会包括进去呢？

因为每次操作可以覆盖一个区间。

负差分的位置（如 d[i] < 0）：表示当前元素比前一个元素低，之前的操作已经覆盖了它的减少需求。
操作示例：
- 原数组 [3, 2, 2]，需要减少到 [1, 1, 1]。
- 操作1：对整个数组减1 → [2, 1, 1]。
- 操作2：仅对第一个元素减1 → [1, 1, 1]。
- 负数差分（如 d[2] = -1）：在操作1中已经被覆盖，无需额外处理。

最后的调整（减1）是为什么？

差分数组的初始值：d[1] = a[1] - a[0] = a[1] - 0 = a[1]。
实际需求：第一个元素只需减少到1，而不是从0开始。因此，d[1] 中多计算了从0到1的冗余层数，需减去1。

例子：

数组 [3, 2, 2] 的差分和 sum(d) = 3 + (-1) + 0 = 2，但实际应为 3 - 1 = 2。
调整后：3（累加正差分） - 1（冗余层数） = 2，与实际操作次数一致。

正差分：必须通过新增操作覆盖。
负差分：已被之前的操作覆盖，无需处理。
减1调整：修正差分初始值的冗余计算。

总结

一维差分和前缀和都很重要，都是可以对区间进行快速的操作，所以我们需要尽量掌握，接下来会持续更新算法的。

蓝桥杯冲刺：一维差分

系列文章目录蓝桥杯系列：一维差分文章目录系列文章目录前言一、一维差分： 差分数组的意义： 二、差分的性质： 差分和前缀和的关系三、一维差分代码实现：四、典型真题（利用一维差分来实现） 这…...

编程日记 2025/9/13 10:34:39

理解企业内部信息集成

目录 1. 技术平台集成 2. 数据集成 3. 应用集成 4. 业务过程集成 5. 应用集成与企业内部信息集成的区别企业内部信息集成是将分散的技术、数据、应用和业务流程整合为一个协同的整体，以提高效率、减少冗余和增强决策能力。企业内部信息集成一般可以分为4个方…...

编程日记 2025/9/13 10:24:41

论文学习：《利用图注意力网络增强单细胞多组学数据的整合》

原文标题：Enhanced Integration ofSingle-Cell Multi-Omics Data Using Graph Attention Networks 原文链接：https://pubs.acs.org/doi/abs/10.1021/acssynbio.4c00864 跨不同组学层的数据集成面临的挑战：高维度、异质性和稀疏性。变分自编码…...

编程日记 2025/9/13 10:24:41

HumanDil-Ox-LDL：保存：2-8℃保存，避免强光直射，不可冻存

化学试剂的基本介绍： /// 英文名称：HumanDil-Oxidized LowDensityLipoprotein /// 中文名称：人源红色荧光标记氧化型低密度脂蛋白 /// 浓度：1.0-4.0 mg/ml /// 外观：乳状液体 /// 缓冲液组分：PBS&…...

编程日记 2025/9/12 12:58:12

基于3d相机的点云物体检测与路径规划

🧩 代码结构和解释： 点云预处理 (preprocess_point_cloud)： 使用 Voxel 下采样来减少点云数据量，去除不必要的噪声。使用统计滤波器去除离群点，以提高后续拟合的精度。 V型焊缝路径拟合 (fit_weld_path_v)&…...

编程日记 2025/9/13 10:33:08

日语学习-日语知识点小记-构建基础-JLPT-N4阶段（2）：んです

日语学习-日语知识点小记-构建基础-JLPT-N4阶段（2）：んです 1、前言（1）情况说明（2）工程师的信仰2、知识点（1）～んです　＆　～の（２）意味（いみ）＆形（かたち）＆使い方（つかいかた）（３）そうなんですか　＆　そうなんだ。（４）何をしているんですか　＆　何を…...

编程日记 2025/9/13 10:33:08

yolov8在windows系统的C++版本的onnxruntime部署方法

1.各个软件的的环境需要保持在统一的版本。 onnxruntime需要和cuda的版本对应上，版本号：onnxruntime-win-x64-gpu-1.18.1 ，链接： NVIDIA - CUDA | onnxruntime cuda:本机显卡支持的版本，cuda11.7，链接：CUDA Toolkit Archive | NVIDIA Developer cudnn:需要对应到cud…...

编程日记 2025/9/13 10:33:07

AD软件的系统设置

设置 1.自动保存（DATA -> backup） 2.原理图-复制元器件递增位号 3.原理图-用斜线表示负信号 4.PCB-选择移动重叠的元器件 5.PCB-十字光标全屏大小 6.PCB-选择部分连接网络的走线全亮/显示多个网络的颜色（TP） 7.PCB-DRC报错的图…...

编程日记 2025/9/10 1:26:38

算法---子序列[动态规划解决]（最长递增子序列）

最长递增子序列说白了，要用到双层循环！ 用双层循环中的dp[i] class Solution { public:int lengthOfLIS(vector<int>& nums) {vector<int> dp(nums.size(),1);for(int i 0;i<nums.size();i){for(int j0;j<i;j){if(nums[i]>num…...

编程日记 2025/9/13 10:31:04

快速幂（模板）

快速幂取余运算性质：(a*b*c)%d (a%d * b%d * c%d)%d ; #include <iostream> using namespace std; int main() {long long b,p,k;//b(底数)p(指数)k(取模数)cin>>b>>p>>k;long long ret1;b%k;//防止底数过大//模版，记&#xf…...

编程日记 2025/9/8 5:27:11

蓝桥杯好数【暴力、基础知识】

题目： AC代码： #include<bits/stdc.h> using namespace std; int ans0; int n; bool check(int x){int cnt1;while(x!0){int tx%10;if(cnt%21){ if(t%20) return false; //奇数位置是偶数} if(cnt%20){if(t%21) return false; //偶数位是奇数}cnt…...

编程日记 2025/9/10 18:37:06

【Kubernetes】Kubernetes中如何实现灰度发布

Kubernetes中实现灰度发布一、基于Ingress-nginx的流量切分（适用中小规模） 权重分流在Ingress资源中通过nginx.ingress.kubernetes.io/canary-weight注解设置新版本流量比例apiVersion: networking.k8s.io/v1 kind: Ingress metadata:annotations:ng…...

编程日记 2025/9/8 5:01:37

【Reinforcement Learning For Quadruped Control】1

强化学习（RL）是一种机器学习范式，代理通过与环境的互动来学习做出决策。强化学习的核心概念围绕以下几个方面展开：a) 代理agent，做出决策；b) 环境environment，响应代理的决策；c) 状态…...

编程日记 2025/8/17 20:57:08

工程企业如何实现四算联动？预算-核算-决算系统解析

在工程行业，项目管理的高效性直接决定了企业的盈利能力和市场竞争力。尤其是在EPC（工程总承包）模式下，工程企业面临着复杂的业务场景和多维度的成本管控需求。如何通过“四算联动”（概算、预算、核算、决算&#xff09…...

编程日记 2025/9/1 14:37:13

【SpringBoot】处理actuator风险漏洞

最近给系统做渗透测试，扫描出了一个actuator风险漏洞，属于高危级别，通过actuator接口可以拿到用户敏感信息。这个问题处理起来倒也简单，禁用actuator或者限制访问就可以了 # 禁用actuator接口配置 management:server:port: -1# 限…...

编程日记 2025/9/7 6:29:50

MACOS15版本安装 python mysqlclient 以连接mysql 8.0

MACOS14/15 版本安装 python mysqlclient 以连接mysql 8.0 主要用于macos django4 mysql8.0 开发项目准备材料 macos > 13.0 python > 3.10.0 （不强制） mysql > 8.0 安装步骤安装 brew 使用国内源安装brew /bin/zsh -c "$(curl -f…...

编程日记 2025/9/9 14:21:41

KV Cache大模型推理加速功能

KV Cache KV Cache是大模型标配的推理加速功能，也是推理过程中，显存资源巨大开销的元凶之一。在模型推理时，KV Cache在显存占用量可达30%以上。目前大部分针对KV Cache的优化工作，主要集中在工程上。比如著名的VLLM&#xff0c…...

编程日记 2025/8/17 21:01:25

Windows下安装WSL2下的Ubuntu、docker容器的IP地址（上）

既然容器支持多个应用，那么容易想到应该有对应的ip地址和端口，这样才能和Ubuntu主机进行通讯，ubuntu访问外网也应该有ip能连接到外网才行，要搞清楚这些ip地址的关系才行。前面两篇文章中说了怎么实现windows和wsl2下的ubuntu的文…...

编程日记 2025/9/6 15:12:20

vue实现中英文切换

第一步：安装插件vue-i18n，npm install vue-i18n 第二步：在src下新建locales文件夹，并在locales下新建index.js、EN.js、CN.js文件第三步：在EN.js和CN.js文件下配置你想要的字段，例如： //CN.js…...

编程日记 2025/9/10 15:22:49

探索 Vue 3 中 vue-router 的 router.resolve () API

一、router.resolve() 是什么 router.resolve() 就好比是一个精准的 “导航参谋”。当我们在 Vue 3 应用里需要明确某个路由地址对应的详细信息时，它就能派上用场。我们给它传入路由信息，像路径、参数等，它会解析出对应的路由对象&#xff0…...

编程日记 2025/9/11 20:53:02

Excel 插件推荐：提升Excel能力的效率神器！

一、Excel玩家的觉醒时刻在财务部的深夜加班现场，李师傅的咖啡杯上凝结着第3圈水渍。眼前的Excel窗口堆叠如俄罗斯方块：重复值删除进度15%、VLOOKUP公式报错3处、合并单元格序号乱成毛线团…这场景是否也戳中了你的痛点？ 每个Excel高手都经…...

编程日记 2025/9/10 14:58:17

leetcode_383. 赎金信_java

383. 赎金信https://leetcode.cn/problems/ransom-note/ 1、题目给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。如果可以，返回 true ；否则返回 false 。 magazine 中的每个字…...

编程日记 2025/9/11 20:03:45

应用安全系列之四十五：日志伪造（Log_Forging）之三

1、简介针对Java的日志系统有多种，本文主要描述如何通过修改配置文件来解决logback和log4j的日志伪造问题。 2、logback 2.1、系统提供的解决方案在logback.xml中配置编码器自动转义特殊字符： 复制 <configuration><appender name"C…...

编程日记 2025/9/4 15:02:46

FTPClient开发遇到的坑

1. 生成文件夹乱序这里用分隔符把路径划分开，意在一层一层创建目录这里可能会出现乱序正确的代码先换一下分隔符再一次生成所有路径 2.ftpClient 需要指定被动模式才能绕开端口限制有些服务器没有打开指定端口，上传文件会出现 425 Canno…...

编程日记 2025/9/9 0:27:06

leetcode0155. 最小栈-medium

1 题目：最小栈官方标定难度：中设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。实现 MinStack 类: MinStack() 初始化堆栈对象。 void push(int val) 将元素val推入堆栈。 void pop() 删…...

编程日记 2025/9/9 16:53:46

操作系统 3.6-内存换出

换出算法总览页面置换算法 FIFO（先进先出）： 最简单的页面置换算法，淘汰最早进入内存的页面。优点：实现简单。缺点：可能会导致Belady异常，即增加内存反而降低性能。如果刚换入的页面马上又要…...

编程日记 2025/9/3 11:20:45

Python中的数值运算函数及math库详解

文章目录 Python中的数值运算函数及math库详解一、内置数值运算函数1. 基本数值运算函数2. 类型转换函数3. 进制转换函数二、math库中的数学常数三、math库常用数学函数1. 数论与表示函数2. 幂函数与对数函数3. 三角函数4. 角度转换5. 双曲函数6. 特殊函数四、实际应用示例1.…...

编程日记 2025/9/3 9:43:54

安卓开发提示Android Gradle plugin错误

The project is using an incompatible version (AGP 8.9.1) of the Android Gradle plugin. Latest supported version is AGP 8.8.0-alpha05 See Android Studio & AGP compatibility options. 改模块级 build.gradle（如果有独立配置）：…...

编程日记 2025/9/10 8:12:47

《Uniapp-Vue 3-TS 实战开发》一键授权登录

在使用 UniApp 结合 Vue 3 和 TypeScript 开发时，实现一键授权登录功能通常涉及到调用微信小程序的授权接口（如 wx.getUserProfile 或 wx.login）来获取用户信息和登录凭证，然后将这些信息发送到后端进行验证和处理。以下是一个完整的实现示例，展示如何在 UniApp 中实现一键…...

编程日记 2025/9/8 1:28:53

Windows 图形显示驱动开发-WDDM 1.2功能_WDDM 1.2 和 Windows 8

简介 WDDM 是随 Windows Vista 一起引入的，以取代 Windows XP 或 Windows 2000 显示驱动程序模型 (XDDM) 。随着 Windows Vista 中的引入，WDDM 体系结构提供了启用新功能的功能，例如桌面组合、增强的容错、视频内存管理器、GPU 计划程序、D…...

编程日记 2025/9/10 8:31:17

155.最小栈

1.题目解析题目是让我们设计一个栈，它于STL库中栈的区别是支持检索到了最小元素的栈但是需要时间复杂度为常数，我们很容易想到的是记录最小值。但是如果中途删除的话最小值可能失效，所以我们选择用2个栈来实现。 2.算法原理我们创建2个栈…...

编程日记 2025/9/8 18:27:32

[C语言笔记]10、字符串

前言： C语言的相关知识点的笔记均在下面的专栏链接中，欢迎订阅！ c语言笔记_1zero10的博客-CSDN博客 10-1字符数组与字符串 1、字符数组就是一个数组，数组的每一个元素都是一个字符首先利用字符数组，回顾以前学过…...

编程日记 2025/9/13 3:24:57

Windows系统备份和还原点

一、简介系统的还原点存储了当前系统的主要状态，包括一些关键的配置信息和参数（包括注册表、系统服务设置、设备驱动程序设置等）。将此时的状态进行备份，在系统发生故障时，可以还原到此还原点的状态中，这…...

编程日记 2025/9/10 8:43:51

内联汇编知识点earlyclobber=

arm64内联汇编格式： asm volatile ("汇编指令1\n\t""汇编指令2\n\t""汇编指令3": 输出操作数列表: 输入操作数列表: 可能被修改的寄存器列表 );示例1：简单的寄存器操作 uint64_t add_numbers(uint64_t a, uint64_t b) {…...

编程日记 2025/9/8 12:39:01

修改ESP32CAM的示例CameraWebServer里的camera_index.h的方法

在这里，默认你已经会使用Arduino IDE或者PlatformIO通过烧录底座对ESP32CAM（如下图）进行烧录，并能通过浏览器对其进行访问。我们访问到下图的界面时，不禁有个疑问，这个界面是如何生成的，如果我…...

编程日记 2025/9/10 13:40:26

Python学习笔记（二）（字符串）

文章目录编写简单的程序一、标识符 (Identifiers)及关键字命名规则：命名惯例：关键字二、变量与赋值 (Variables & Assignment)变量定义：多重赋值：变量交换：（很方便哟） 三、输入与输出 (In…...

编程日记 2025/9/9 15:48:02

ViewModel vs AndroidViewModel：核心区别与使用场景详解

在 Android 的 MVVM 架构中，ViewModel 和 AndroidViewModel 都是用于管理 UI 相关数据的组件，但二者有一些关键区别： 1. ViewModel 基本用途：用于存储和管理与 UI 相关的数据，生命周期与 Activity/Fragment 解耦&…...

编程日记 2025/9/4 8:09:06

Windows环境下全屏显示某个字符串

case WM_PAINT: {PAINTSTRUCT ps;HDC hdc BeginPaint(hWnd, &ps);// 获取完整客户区尺寸RECT rc;GetClientRect(hWnd, &rc);// 全屏时：整个窗口作为显示区域RECT displayRect rc;// 纯黑背景FillRect(hdc, &displayRect, (HBRUSH) GetStockObject(BLA…...

编程日记 2025/9/13 3:43:44

禅道MCP Server开发实践与功能全解析

一、简介 1、MCP Server核心定义 MCP Server（Meta Command Protocol Server）是一种基于客户端-服务器架构的轻量级服务程序，采用统一的mcp协议格式，通过连接多样化数据源和工具为AI应用提供扩展能力。它作为中间层，实…...

编程日记 2025/9/11 22:53:49

Vue.js组件安全开发实战：从架构设计到攻防对抗

目录开篇总述：安全视角下的Vue组件开发新范式一、Vue.js组件开发现状全景扫描二、安全驱动的Vue组件创新架构三、工程化组件体系构建指南四、深度攻防对抗实战解析五、安全性能平衡策略结语：安全基因注入前端开发的未来展望下期预告&…...

编程日记 2025/9/9 0:46:07

代发考试战报：4月份最新锐捷RCNA RCNP 考试通过战报

锐捷 RCNA云计算 R4111 考试通过，RCNA 安全 R3111 考试通过，RCNP无线 R5211考试通过，RCNP路由考试通过，等等成绩单战报...

编程日记 2025/8/31 20:15:48

卫星互联网技术加速发展，遨游卫星电话为生命添一份“保险”

卫星互联网通过高中低轨卫星组网，实现了对海洋、沙漠、极地等“信息盲区”的全域覆盖。据国际电信联盟（ITU）统计，截至2024年底，全球在轨卫星数量已突破1万颗，其中我国“千帆星座”“GW星座”等低轨计划加速…...

编程日记 2025/9/9 5:46:56

文件IO7（中文字库的原理与应用/目录检索原理与应用/并发编程的原理与应用）

中文字库的原理与应用 ⦁ 基本概念一般在项目中都会显示汉字，都采用中文简体字符集，计算机早期只有ANSI组织设计的ANSII码，其实也属于字符集，这套字符集并未收录中文，只收录256个字符。所以后期中国国家标准总局设…...

编程日记 2025/9/11 3:46:01

达梦数据库-学习-16-常用SQL记录（持续更新）

目录一、环境信息二、介绍三、查询SQL 1、数据库的总使用空间大小 2、各个表空间的总大小 3、使用空间最大的50个对象 4、使用率最高的50个sequence 5、使用空间率最高的50个自增列 6、定位锁 7、支持HINT 8、表数据页使用率 9、备份文件相关信息 10、初始化库参…...

编程日记 2025/9/7 18:32:42

使用setTimeout模拟setInterval

const SECOND 1000 const MINUTE 60 * SECOND const HOUR 60 * MINUTE const DAY 24 * HOUR/*** description: 根据传入的毫秒值格式化为时间* param {*} time：毫秒值* returns：{days, hours, minutes, seconds, milliseconds}*/ function parseTime…...

编程日记 2025/8/31 20:15:30