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

蓝桥杯-小明的彩灯(差分)

news 来源：原创 2025/9/20 12:54:28

问题描述：

在这里插入图片描述

差分数组

1. 什么是差分数组？

差分数组 c 是原数组 a 的“差值表示”，其定义如下：

c[0] = a[0]
c[i] = a[i] - a[i-1] （i ≥ 1）

差分数组记录了相邻元素的差值。例如，原数组 a = [1, 3, 5, 2] 对应的差分数组为 c = [1, 2, 2, -3]。

2. 差分数组的优势

通过差分数组，可以将区间操作转换为两次单点操作：

若要将区间 [l, r] 的所有元素增加 k，只需执行：
- c[l] += k
- c[r+1] -= k
  这一操作的时间复杂度为 O(1)，彻底避免了遍历区间。

3. 还原原数组

对差分数组进行前缀和运算即可还原原数组：

a[i] = c[0] + c[1] + ... + c[i]
前缀和的本质是逐步累加差分值，恢复出原数组的实际数值。

解题思路详解

步骤1：构建差分数组

初始化差分数组 c，长度为 n+1（多一位用于处理右边界）。
根据原数组 a 的相邻差值填充 c，确保 c[i] = a[i] - a[i-1]。

步骤2：处理区间操作

对于每个操作 [l, r, k]：

将 c[l] += k，表示从 l 开始的所有元素增加 k。
将 c[r+1] -= k，表示在 r+1 处抵消多余的 k，保证操作仅作用于 [l, r]。

步骤3：还原修改后的数组

通过前缀和还原最终的数组：

从 c[1] 开始，依次累加 c[i] += c[i-1]，最终 c[0...n-1] 即为修改后的原数组。

代码：

public static void main(String[] args) {//通过原数组计算 差分 数组//再通过计算出的 差分 数组做 数据操作，例如（要将[l,r]区间所有数组+1）就将c[l]+1 c[r+1]-1//对差分数组，做前缀和操作得到原数组//有一个坑，虽然数据都是在int范围内，但是会涉及到相加操作，可能会超出int范围，所以我们的差分数组应该设置为longScanner sc = new Scanner(System.in);int n = sc.nextInt();int m = sc.nextInt();int[] a = new int[n];//在创建差分数组的时候长度要设置为a.length + 1这是很有必要的,防止数组越界 这个边界操作(c[r + 1] -= 1;)long[] c = new long[n + 1];a[0] = sc.nextInt();//初始化差分数组c[0] = a[0];for (int i = 1; i < n; i++) {a[i] = sc.nextInt();c[i] = a[i] - a[i - 1];}
//        System.out.println("原数组a:" + Arrays.toString(a));
//        System.out.println("差分数组c:" + Arrays.toString(c));//要将[l,r]区间所有数组+cfor (int i = 0; i < m; i++) {int l = sc.nextInt();int r = sc.nextInt();int sum = sc.nextInt();c[l - 1] += sum;c[r] -= sum;}for (int i = 1; i < n; i++) {//这里复原的原理其实很简单// 例如对 1 2 3 4 5的[2,4]区间做+1操作，// 由于差分数组记录的是第i个数比第i-1个数大多少，之前i比i-1大1，+1操作之后，就是i比i-1大2了，// 但是由于我们要求在到[l,r]区间，所以r之后的差分就得还原 所以再做一个-1操作还原// 所以还原的时候，就能得到题目要求的数组了c[i] += c[i - 1];}for (int i = 0; i < n; i++) {if (c[i] < 0) {System.out.print(0 + " ");} elseSystem.out.print(c[i] + " ");}}

蓝桥杯-小明的彩灯(差分)

问题描述： 差分数组 1. 什么是差分数组？ 差分数组 c 是原数组 a 的“差值表示”，其定义如下： c[0] a[0]c[i] a[i] - a[i-1] （i ≥ 1） 差分数组记录了相邻元素的差值。例如，原数组 a [1, …...

编程日记 2025/9/20 12:54:28

vim定位有问题的脚本/插件的一般方法

在使用vim的过程中可能会遇到一些报错或其他不符合预期的情况，本文介绍一些我自己常用的定位有问题脚本/插件的方法（以下方法同样适用于neovim） 执行了某些命令的情况这种情况最简单，使用:h 命令，如果插件有文档的话…...

编程日记 2025/9/9 3:29:41

EasyExcel实现图片导出功能（记录）

背景：在旧系统的基础上，导出一些工单信息时，现需要新添加处理人的签名或者签章，这就涉及图片的上传、下载、写入等几个操作。 1、EasyExcel工具类 （1）支持下拉框的导出。 import com.alibaba.excel.Easy…...

编程日记 2025/9/20 12:51:46

PCL版本 1.15.0 main.cpp #include<vector> #include<iostream> #include <array> #include <string> #include <windows.h> #include <omp.h> #include <charconv> // C17 #include <cstdlib> #include<chrono> #in…...

编程日记 2025/9/19 11:10:16

ansible 实现达梦7数据库初始化数据脚本写入

关于使用ansible 对ARM版达梦7的k8s自动化部署参考我的这篇操作 ansible-playbook 写arm版达梦7数据库的一键安装脚本-CSDN博客文章浏览阅读303次，点赞5次，收藏3次。达梦官方提供镜像目前是dm8_x86 版本，因为众所周知的国产化方面的需求&…...

编程日记 2025/9/18 14:20:01

leetcode每日刷题

Day18 Title45.jump(跳跃游戏 II) 解法一：动态规划依然分三步走： 1.状态方程 2.dp[i]的意义 3.边界条件及初始值优先思考第二个问题： dp[i]表示到达i时需要的最少跳数第一个问题： dp[ij]min(dp[i]1,dp[ij]) 为什么&am…...

编程日记 2025/9/18 19:58:22

Ubuntu安装Nginx

Ubuntu安装Nginx 由于 Ubuntu 的 apt 命令内置了 nginx 源，因此不用配置 apt 就可以直接下载安装： apt install nginx -y查看 nginx 是否启动： ps -ef |grep nginx如果没有启动则需要手动启动： nginx1. 配置Nginx 使用浏览器…...

编程日记 2025/9/20 12:52:20

Hadoop的序列化

（一）什么是序列化与反序列化序列化就是把内存中的对象，转换成字节序列（或其他数据传输协议）以便于存储到磁盘（持久化）和网络传输。反序列化就是将收到字节序列（或其他数据传输协议…...

编程日记 2025/9/20 12:53:51

拼多多商品详情接口爬虫实战指南

一、引言在电商运营和数据分析中，获取商品详情数据是至关重要的一步。拼多多作为国内知名的社交电商平台，提供了丰富的商品详情接口，允许开发者通过API获取商品的详细信息。本文将详细介绍如何通过爬虫技术结合拼多多商品详情接口&#xff…...

编程日记 2025/9/16 5:34:56

python网络爬虫

一、Python爬虫核心库 HTTP请求库 requests：简单易用的HTTP请求库，处理GET/POST请求。aiohttp：异步HTTP客户端，适合高并发场景。 HTML/XML解析库 BeautifulSoup：基于DOM树的解析库，支持多种解析器&#xf…...

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

java线程安全-单例模式-线程通信

首先看看单例模式的写法首先我们先来回顾一下饿汉式单例模式： class Singleton{private static Singleton singletonnew Singleton();private Singleton(){}public static Singleton getInstrance(){return singleton;} } public class Test{public static void …...

编程日记 2025/9/16 8:36:46

ASP.NET中将 PasswordHasher 使用的 PBKDF2 算法替换为更现代的 Scrypt 或 Argon2 算法

相关博文： .Net实现SCrypt Hash加密_scrypt加密-CSDN博客密钥派生算法介绍及 PBKDF2(过时)＜Bcrypt(开始淘汰)＜Scrypt＜ Argon2(含Argon2d、Argon2i、Argon2id)简介-CSDN博客浅述.Net中的Hash算法（顺带对称、非对称…...

编程日记 2025/9/20 7:28:41

力扣刷题-热题100题-第34题（c++、python）

23. 合并 K 个升序链表 - 力扣（LeetCode）https://leetcode.cn/problems/merge-k-sorted-lists/?envTypestudy-plan-v2&envIdtop-100-liked 顺序合并合并两个有序链表作为子函数，创建一个空链表，然后对含有多个链表的数组进…...

编程日记 2025/9/9 12:41:39

【SpringCloud】从入门到精通【上】

今天主播我把黑马新版微服务课程MQ高级之前的内容都看完了，虽然在看视频的时候也记了笔记，但是看完之后还是忘得差不多了，所以打算写一篇博客再温习一下内容。课程坐标:黑马程序员SpringCloud微服务开发与实战微服务认识单体架构单体架…...

编程日记 2025/9/20 4:36:17

如何给路由器配置代理IP？更改网络ip地址时出现错误怎么解决？

在现代网络环境中，无论是家庭用户还是企业用户，经常需要配置路由器以实现网络访问的灵活性和匿名性。其中，给路由器配置代理IP是一个常见的需求，尤其是在需要绕过地域限制、增强网络安全或进行匿名浏览时。然而，配置过…...

编程日记 2025/9/15 3:28:04

程序化广告行业（70/89）：ABTester系统助力落地页优化实践

程序化广告行业（70/89）：ABTester系统助力落地页优化实践在程序化广告领域摸爬滚打多年，深知持续学习和知识共享的重要性。写这篇博客，就是希望能和大家一起深入探索程序化广告行业，共同学习、共同进步。今…...

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

远程监控系统项目里练习

1、项目目标设备端： （1）基于stm32mp157开发板，裁剪linux5.10.10，完成ov5640摄像头移植； （2）完成用户层程序，完成对摄像头的控制及与云端服务的数据交互。云端&…...

编程日记 2025/9/18 11:48:25

Spring Boot 通过全局配置去除字符串类型参数的前后空格

1、问题避免前端输入的字符串参数两端包含空格，通过统一处理的方式，trim掉空格 2、实现方式 /*** 去除字符串类型参数的前后空格* author yanlei* since 2022-06-14*/ Configuration AutoConfigureAfter(WebMvcAutoConfiguration.class) public clas…...

编程日记 2025/9/10 14:51:35

设计模式 --- 观察者模式

设计模式 --- 观察者模式什么是观察者模式观察者模式典型应用 --- C#中的事件使用观察者模式实现事件处理机制什么是观察者模式观察者模式（Observer Pattern）是一种行为型设计模式，用于在对象之间建立一对多的依赖关系。当一个对象&#x…...

编程日记 2025/9/11 13:38:44

组播网络构建：IGMP、PIM 原理及应用实践

IP组播基础组播基本架构组播IP地址一个组播IP地址并不是表示具体的某台主机，而是一组主机的集合，主机声明加入某组播组即标识自己需要接收目的地址为该组播地址的数据IP组播常见模型分为ASM模型和SSM模型ASM：成员接收任意源组播数据&…...

编程日记 2025/9/10 5:23:35

Java常见的23种设计模式

Java常见的23种设计模式大家好，我是钢板兽！ 本文将系统梳理 Java 的设计模式，涵盖创建型、结构型和行为型三大类，结合定义、原理、优点、应用场景、示例代码，帮助你初步了解常见的23种设计模式。一、设计模式分类…...

编程日记 2025/9/13 9:31:06

兔单B细胞单抗制备服务

1.兔单B细胞技术原理兔单B细胞技术是近年来新发展的一类快速制备单克隆抗体的技术，是一种通过分离和单克隆化兔子体内的B细胞来制备单一来源的高特异性抗体的方法。基于流式细胞分选技术进行单B细胞单抗制备，利用每个B细胞只含有一个功能性重链可变区D…...

编程日记 2025/9/11 7:59:52

MySQL基础 [六] - 内置函数+复合查询+表的内连和外连

内置函数一般要用select调用内置函数日期函数 current_date函数 current_date函数用于获取当前的日期。如下： current_time函数 current_time函数用于获取当前的时间。如下： now函数 now函数用于获取当前的日期时间。如下： date函数 dat…...

编程日记 2025/9/15 12:44:17

nginx路径匹配的优先级

在 Nginx 配置中，当请求 /portal/agent/sse 时，会匹配 location ~* /sse$ 规则，而不是 location /portal。原因如下： 匹配规则解析 location ~* /sse$ ~* 表示不区分大小写的正则匹配/sse$ 表示以 /sse 结尾的路径匹配结果&#…...

编程日记 2025/9/8 1:08:49

tcp/ip攻击及防范

作为高防工程师，我每天拦截数以万计的恶意流量，其中TCP/IP协议层攻击是最隐蔽、最具破坏性的威胁之一。常见的攻击手法包括： 1. SYN Flood攻击：攻击者发送大量伪造的SYN包，耗尽服务器连接资源，导致正常用…...

编程日记 2025/9/20 2:11:39

2025年3月中国电子学会青少年软件编程（Python）等级考试试卷（一级）答案 + 解析

更多真题在线练习系统：历年真题在线练习系统一、单选题 1、下列哪个软件不能运行 Python 程序？（ ） A、JupyterNotebook B、Pycharm C、原版的Scratch D、IDLE 正确答案：C 答案解析：本题考察的 Pyt…...

编程日记 2025/9/12 23:04:24

TreeMap 核心知识点与面试题解析

TreeMap 核心知识点与面试题解析一、TreeMap 基础概念 TreeMap 是 Java 集合框架中基于红黑树（Red-Black Tree） 实现的 Map，具有以下特点： 有序性：默认按 key 的自然顺序（Comparable）或自定…...

编程日记 2025/9/4 16:49:45

深入理解 DevOps 与 CI/CD：概念、流程及优势

在当今快速发展的数字化时代，软件开发和交付的速度与质量成为企业在激烈竞争中脱颖而出的关键因素。DevOps 和 CI/CD 作为现代软件开发领域的重要理念和实践，正深刻地改变着软件开发生命周期的运作方式。本文将深入探讨 DevOps 的概念，详细解析 CI/CD 的内涵、管道阶段以及实…...

编程日记 2025/9/16 8:12:46

Flutter BloC 架构入门指南

BLoC (Business Logic Component) 是 Flutter 中一种流行的状态管理架构，它可以帮助你将业务逻辑与 UI 分离，使代码更清晰、可测试性更强。核心概念 1. BloC 的核心组件 Events：用户交互或系统事件（如按钮点击、网络请求完成&…...

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

OpenHarmony-AI调研

OpenHarmony-AI调研文章目录 OpenHarmony-AI调研前言一、当前版本部署组件二、AI架构1.mindspore-lite2.ai_engine3.neural_network_runtime4.intelligent_voice_framework5.HDI驱动三、应用1.命令行以及web运行deepseek-r12.与deepseek通过语音进行交互3.物品识别4.人脸识别…...

编程日记 2025/9/16 1:32:09

zk基础—zk实现分布式功能

1.zk实现数据发布订阅 (1)发布订阅系统一般有推模式和拉模式推模式：服务端主动将更新的数据发送给所有订阅的客户端。拉模式：客户端主动发起请求来获取最新数据(定时轮询拉取)。 (2)zk采用了推拉相结合来实现发布订阅首先客户端需要向服务端注册自己关…...

编程日记 2025/9/16 1:59:43

Tips：用proxy解决前后端分离项目中的跨域问题

在前后端分离项目中，"跨域问题"是浏览器基于同源策略（Same-Origin Policy）对跨域请求的安全限制。当你的前端（如运行在 http://localhost:3000 ）和后端（如运行在 http://localhost:8080 &#…...

编程日记 2025/8/17 21:57:31

JMeterPlugins-Standard-1.4.0 插件详解：安装、功能与使用指南

JMeterPlugins-Standard-1.4.0 是 Apache JMeter（一款流行的开源负载和性能测试工具）的插件包，它扩展了 JMeter 的功能，提供了更多监听器（Listeners）、采样器（Samplers）和辅助组件&a…...

编程日记 2025/9/19 14:29:38

JMeter 中，Token 和 Cookie 的区别及实际应用

在 JMeter 中，Token 和 Cookie 都是用于处理用户会话和身份验证的机制，但它们的工作原理、存储方式和应用场景有显著区别。以下是详细对比和实际应用指南： 1. 核心区别特性Token (如 JWT、OAuth)Cookie存储位置通常存储在 HTTP 请求头（如 Authorization: Bearer <t…...

编程日记 2025/9/16 9:01:35

蓝桥杯真题——好数、R格式

目录蓝桥杯2024年第十五届省赛真题-好数【模拟题】题目描述输入格式输出格式样例输入样例输出提示代码1：有两个案例过不了，超时蓝桥杯2024年第十五届省赛真题-R 格式【vector容器的使用】题目描述输入格式输出格式样例输入…...

编程日记 2025/9/11 13:02:59

JavaScript惰性加载优化实例

这是之前的一位朋友的酒桌之谈，他之前负责的一个电商项目，刚刚开发万，首页加载时间特别长，体验很差，所以就开始排查，发现是在首页一次性加载所有js导致的问题，这个问题在自己学习的时候并不明显…...

编程日记 2025/9/11 3:31:36

0_Pytorch中的张量操作

[引言]张量的概念 1.基本概念张量是一个通用的多维数组，可以表示标量（0 维）、向量（1 维）、矩阵（2 维）以及更高维度的数据。张量是 PyTorch 中的核心数据结构，用于表示和操作数据。…...

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

Java面试43-常见的限流算法有哪些？

限流算法是一种系统保护策略，主要是避免在流量高峰导致系统被压垮，造成系统不可用的问题。常见的限流算法有五种： 计数器限流，一般用在单一维度的访问频率限制上，比如短信验证码每隔60s只能发送一次，或者…...

编程日记 2025/9/12 7:12:07

牛客网：树的高度 ← 根节点为 0 号节点

【题目来源】 https://www.nowcoder.com/questionTerminal/4faa2d4849fa4627aa6d32a2e50b5b25 【题目描述】现在有一棵合法的二叉树，树的节点都是用数字表示，现在给定这棵树上所有的父子关系，求这棵树的高度。【输入格式】输入的第一行表…...

编程日记 2025/9/19 6:35:04

Linux:进程程序替换execl

目录引言 1.单进程版程序替换 2.程序替换原理 3.6种替换函数介绍 3.1 函数返回值 3.2 命名理解 3.3 环境变量参数引言用fork创建子进程后执行的是和父进程相同的程序(但有可能执行不同的代码分支)，我们所创建的所有的子进程，执行的代码&#x…...

编程日记 2025/9/18 3:05:10

⑩数据中心M-LAG 实战

一、配置指导自己去看今天操作的是M-LAG 基础实验二、配置代码信息回顾 ### 1、配置 M-LAG 系统 MAC 地址<H3C>system-view[H3C]m-lag system-mac ?H-H-H MAC address2a7a-53ee-0100 Bridge MAC address[H3C]m-lag system-mac### 2、配置 M-LAG 系统编号…...

编程日记 2025/9/9 6:04:47

delphi idtcpserver 搭建tcp ，ssl协议服务端

如果想用indy idtcpserver实现tcp ssl，那么正是你需要的首先生成证书： 2、windows生成pem证书 - 站着说话不腰疼 - 博客园有证书后 idtcpserver 用的三个证书， IdServerIOHandlerSSLOpenSSL1.SSLOptions.CertFile = ca.crt IdServerIOHandlerSSLOpenSSL1.SSLOptions.…...

编程日记 2025/9/15 4:47:54

如何实现外观模式？

一、模式理解（用快递驿站比喻） 想象你网购了5件商品，分别来自不同快递公司。外观模式就像小区门口的快递驿站，你不需要知道中通怎么分拣、顺丰怎么运输，只要到驿站报取件码就能拿到所有包裹。在前端开发中&#xf…...

编程日记 2025/9/20 0:57:26

深入解析 Linux 文件系统权限：从基础到高级实践

引言在 Linux 系统中，文件系统权限是保障数据安全和多用户协作的核心机制。想象这样一个场景： 你的服务器上有多个团队共享项目文件财务数据必须严格保密，仅允许指定人员访问开发团队需要共同编辑代码，但禁止随意删除他人文…...

编程日记 2025/9/11 7:49:46

GZ036区块链卷一 EtherStore合约漏洞详解

题目 pragma solidity >0.8.3;contract EtherStore {mapping(address > uint) public balances;function deposit() public payable {balances[msg.sender] msg.value;emit Balance(balances[msg.sender]);}function withdraw() public {uint bal balances[msg.sender…...

编程日记 2025/9/19 22:28:22

医药流通行业批发公司IT运维转型：Prometheus+Grafana监控Spring Boot 3应用实践

一、引言：医药流通行业IT运维挑战与工具换代需求在医药流通行业批发领域，业务的核心在于供应链的高效运转、订单处理的精准及时以及库存管理的动态平衡。随着互联网医疗的兴起和电商平台的渗透，传统医药批发企业正加速向数字化、智能化转型…...

编程日记 2025/9/8 1:31:24

编程助手fitten code使用说明(超详细)(vscode)

这两年 AI 发展迅猛，作为开发人员，我们总是追求更快、更高效的工作方式，AI 的出现可以说改变了很多人的编程方式。 AI 对我们来说就是一个可靠的编程助手，给我们提供了实时的建议和解决方，无论是快速修复错误、提升代…...

编程日记 2025/9/9 11:23:09

金融大模型

FinGPT 数据集：https://github.com/AI4Finance-Foundation/FinGPT/tree/master/fingpt/FinGPT-v3 FinGPT v3 系列是在新闻和微博情绪分析数据集上使用 LoRA 方法进行微调的LLM，在大多数金融情绪分析数据集上取得了最佳分数。 FinGPT v3.1 使用 chatgl…...

编程日记 2025/9/10 7:58:22

【Pandas】pandas DataFrame infer_objects

Pandas2.2 DataFrame Conversion 方法描述DataFrame.astype(dtype[, copy, errors])用于将 DataFrame 中的数据转换为指定的数据类型DataFrame.convert_dtypes([infer_objects, …])用于将 DataFrame 中的数据类型转换为更合适的类型DataFrame.infer_objects([copy])用于尝试…...

编程日记 2025/9/11 22:36:21

011_异常、泛型和集合框架

异常、泛型和集合框架异常Java的异常体系异常的作用自定义异常异常的处理方案异常的两种处理方式泛型泛型类泛型接口泛型方法、通配符和上下限泛型支持的类型集合框架集合体系结构Collection Collection集合Collection的遍历方式认识并发修改异常问题解决并发修改异常问题的…...

编程日记 2025/9/14 5:01:52