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

蓝桥备赛（25）算法篇【差分】

news 来源：原创 2025/8/2 22:20:36

一、差分

前缀和和差分的核心思想是预处理 ， 可以在暴力枚举的过程中，快速给出查询结果，从而优化时间复杂度。

最经典的用空间替换时间的做法。

学完差分之后，大家会发现， 前缀和与差分是一对互逆的运算

二、一维差分

解法一：暴力解法 --> 直接模拟

两层 for 循环 --> O（m*n) = 10^10 (超时了...)

所以我们可以总结出用差分解决问题的模板：

1）创建差分数组

2）利用差分数组处理 m 次修改操作

3）还原成原始数组：

#include <iostream>
using namespace std;typedef long long LL;
const int N = 1e5 + 10;
LL n,m;
LL a[N];
LL f[N];//记录差分数组int main()
{cin >> n >> m;//利用差分数组定义创建差分数组for(int i = 1;i<=n;i++){cin >> a[i];f[i] = a[i] - a[i-1];}//处理 m 次修改操作while(m--){LL l,r,k;cin >> l >> r >> k;f[l] += k;f[r+1] -= k;} //还原出原始的数组for(int i = 1;i<=n;i++){a[i] = a[i-1] + f[i];cout << a[i] << " ";}return 0;
}

三、海底高铁

P3406 海底高铁 - 洛谷

#include <iostream>
using namespace std;typedef long long LL;const int N = 1e5 + 10;int n,m;
LL f[N];//差分数组 int main()
{cin >> n >> m;//x->yint x,y;cin >> x;//处理差分数组 for(int i = 2;i<=m;i++){cin >> y;//x->yif(x > y)f[y]++,f[x]--;else f[x]++,f[y]--;x = y;}//利用差分数组，还原出原数组for(int i = 1;i<=n;i++){f[i] += f[i-1];} //直接求结果LL ret = 0;for(int i = 1;i<=n;i++){LL a,b,c;cin >> a >> b >> c;ret += min(a*f[i],c+b*f[i]);} cout << ret << endl;return 0;}

四、二维差分

第一个能想到的就是暴力枚举，到了目标区域，直接进行操作，

但是时间复杂度太高了， OJ平台是不会给过的~

借助二维差分数组：

画图！了解二维差分数组的性质，等再次使用的时候，上手会很快！！！

#include <iostream>
using namespace std;typedef long long LL;
const int N = 1001;
LL n,m,q;
LL f[N][N];//差分矩阵 //差分矩阵的性质 
void insert(int x1,int y1,int x2, int y2,int k)
{f[x1][y1] += k;f[x1][y2+1] -= k;f[x2+1][y1] -=k;f[x2+1][y2+1] +=k; 
}int main()
{cin >> n >> m >> q;//预处理--构造差分矩阵 for(int i = 1;i<=n;i++){for(int j = 1;j<=m;j++){LL x;cin >> x;//[i,j] 为左上角，[i,j]为右下角的矩阵，统一加上xinsert(i,j,i,j,x); }}//处理q次修改操作while(q--){int x1,y1,x2,y2,k;cin >> x1 >> y1 >> x2 >> y2 >> k;insert(x1,y1,x2,y2,k);} //利用前缀和还原修改之后的数组for(int i = 1;i<=n;i++){for(int j = 1;j<=m;j++){f[i][j] = f[i-1][j] + f[i][j-1] - f[i-1][j-1] + f[i][j];cout << f[i][j] << " ";}cout << endl;} return 0;
}

五、地毯

P3397 地毯 - 洛谷

差分数组走起来，简简单单~

#include <iostream>
using namespace std;const int N = 1010;
int f[N][N];
int n,m; void insert(int x1,int y1,int x2,int y2)
{f[x1][y1]++;f[x2+1][y1]--;f[x1][y2+1]--;f[x2+1][y2+1]++;
}
int main()
{cin >> n >> m;while(m--){int x1,y1,x2,y2;cin >> x1 >> y1 >> x2 >> y2;insert(x1,y1,x2,y2);}//借助前缀和还原成原数组for(int i = 1;i<=n;i++){for(int j = 1;j<=n;j++){	f[i][j] = f[i-1][j] + f[i][j-1] - f[i-1][j-1] + f[i][j];cout << f[i][j] << " ";	}cout << endl;}return 0;
}

在理解的基础上可以背背，但是尽量不要背，理解为主

蓝桥备赛（25）算法篇【差分】

一、差分前缀和和差分的核心思想是预处理 ， 可以在暴力枚举的过程中 ， 快速给出查询结果 ， 从而优化时间复杂度。最经典的用空间替换时间的做法。学完差分之后 ， 大家会发现 ， 前缀和与差分是一对互逆的运算二、一…...

编程日记 2025/8/2 22:20:36

Linux|fork命令及其使用的写时拷贝技术

fork复制进程 fork通过以下步骤来复制进程： 分配新的进程控制块：内核为新进程分配一个新的进程控制块（PCB），用于存储进程的相关信息，如进程 ID、状态、寄存器值、内存指针等。复制进程地址空间&#xff1…...

编程日记 2025/8/2 7:24:41

sgpt 终端使用指南

1. 什么是 sgpt？ sgpt 是一个基于 OpenAI API 的命令行工具，允许用户在终端中与 AI 进行交互，支持自然语言对话、代码生成、Shell 命令生成等功能。本文将介绍 sgpt 的安装方法、基本用法、配置文件路径及修改方式，并提供完整的配…...

编程日记 2025/8/1 22:58:59

python如何提取html中所有的图片链接

在Python中，你可以使用BeautifulSoup库来解析HTML内容，并提取其中所有的图片链接（即<img>标签的src属性）。以下是一个示例代码，展示了如何做到这一点： 首先，确保你已经安装了BeautifulSo…...

编程日记 2025/8/2 9:07:06

第十一章 | 智能合约主网部署与验证详解

📚 第十一章 | 智能合约主网部署与验证详解 ——让你的合约真正上线、公开、透明！ ✅ 本章导读前面我们写了各种合约，ERC20、NFT、DAO…… 但只在本地测试或测试网上部署运行，项目还没“上链”！ 主网上线部署&#…...

编程日记 2025/8/2 22:20:34

一文读懂Python之json模块（33）

一、json模块介绍 json模块的功能是将序列化的json数据从文件里读取出来或者存入文件。json是一种轻量级的数据交换格式，在大部分语言中，它被理解为数组（array）。 json模块序列化与反序列化的过程分别是 encoding和 decoding。e…...

编程日记 2025/8/2 22:19:19

TextView、AppCompatTextView和MaterialTextView该用哪一个？Android UI 组件发展史与演进对照表

在 Android 开发中，UI 组件一直在不断演进，从最初的原生组件，到 Support Library（AppCompat 兼容库），再到如今的 Material Design 组件。这篇文章将梳理 Android UI 组件的发展历史，并提供详细的…...

编程日记 2025/8/2 16:40:39

三层网络（服务器1 和服务器2 在不同网段）

服务器1 和服务器2 在不同网段，并且通过三层交换机实现通信 1. 网络拓扑假设网络拓扑如下： 服务器1： mac0：IP 地址 192.168.1.10/24，网关 192.168.1.1 mac1：IP 地址 10.0.1.10/24，网关 10.0…...

编程日记 2025/8/2 21:12:02

23种设计模式-创建型模式-工厂方法

文章目录简介场景问题1. 直接依赖具体实现2. 违反开闭原则3. 条件分支泛滥4. 代码重复风险解决根本问题完整类图完整代码说明核心优势代码优化静态配置表动态策略总结简介工厂方法是一种创建型设计模式，它提供了在父类中创建对象的接口，但允许子类…...

编程日记 2025/8/2 22:18:25

el-table单元格编辑，动态增删行，回车/上下左右箭头切换单元格

🤵 作者：coderYYY 🧑 个人简介：前端程序媛，目前主攻web前端，后端辅助，其他技术知识也会偶尔分享🍀欢迎和我一起交流！🚀（评论和私信一般会回！！） 👉 个人专栏推荐：《前端项目教程以及代码》基于 Element UI 实现表格单元格编辑与键盘导航功能 Element UI …...

编程日记 2025/7/30 1:20:46

基于springboot的新闻推荐系统（045）

摘要随着信息互联网购物的飞速发展，国内放开了自媒体的政策，一般企业都开始开发属于自己内容分发平台的网站。本文介绍了新闻推荐系统的开发全过程。通过分析企业对于新闻推荐系统的需求，创建了一个计算机管理新闻推荐系统的方案。文章介绍了…...

编程日记 2025/7/30 1:17:36

解决Selenium滑动页面到指定元素,点击失效的问题

White graces：个人主页 🙉专栏推荐:Java入门知识🙉 🐹今日诗词:君失臣兮龙为鱼，权归臣兮鼠变虎🐹 ⛳️点赞 ☀️收藏⭐️关注💬卑微小博主🙏 ⛳️点赞 ☀️收藏⭐️关注&#x1f4…...

编程日记 2025/7/29 15:28:38

医学图像白血病分割数据集labelme格式245张5类别

数据集格式：labelme格式(不包含mask文件，仅仅包含jpg图片和对应的json文件) 图片数量(jpg文件个数)：245 标注数量(json文件个数)：245 标注类别数：5 标注类别名称:["basophil Leukemia","Lymphocyte…...

编程日记 2025/8/2 22:16:36

第一章 Python语言概述与生态体系 1.3 Python在工业界的应用场景 # 示例：使用FastAPI构建RESTful接口 from fastapi import FastAPI from pydantic import BaseModelapp = FastAPI()class Item(BaseModel):name: strprice: float@app.post("/items/") async def cr…...

编程日记 2025/8/2 22:17:17

DHCPv6 Stateless Vs Stateful Vs Stateless Stateful

DHCPv6常见配置模式在 IPv6 网络中，DHCPv6 的 Stateless（无状态）、Stateful（有状态）和 Stateless + Stateful（混合模式）是三种常见的配置模式。它们的主要区别在于客户端如何获取 IPv6 地址和其他网络配置信息（如 DNS 服务器）。 Stateless（无状态）模式 Statele…...

编程日记 2025/8/2 22:20:35

Redis Cluster 详解

Redis Cluster 详解 1. 为什么需要 Redis Cluster？ Redis 作为一个高性能的内存数据库，在单机模式下可能会遇到以下问题： 单机容量受限：Redis 是基于内存存储的，单机的内存资源有限，单实例的 Redis 只能…...

编程日记 2025/8/2 19:03:58

Spring(8)——MyBatis入门(2)

一、Mybatis的xml配置文件 Mybatis的开发有两种方式： 注解xml 上一篇博客介绍了用注解的方式操作数据库，这一篇介绍通过xml配置文件的方式操作数据库。 1.1 xml配置文件规则在Mybatis中使用XML映射文件方式开发，需要符合一定的规范&…...

编程日记 2025/7/23 15:29:06

解析DeepSeek的技术内核：混合专家架构如何重塑AI效能

解析DeepSeek的技术内核：混合专家架构如何重塑AI效能在当今大型语言模型（LLM）竞争激烈的赛道上，中国AI企业DeepSeek凭借其独特的技术路线脱颖而出。其核心优势之一，便是对混合专家（Mixture of Experts&…...

编程日记 2025/8/2 22:19:18

Android在kts中简单使用AIDL

Android在kts中简单使用AIDL AIDL相信做Android都有所了解，跨进程通信会经常使用，这里就不展开讲解原理跨进程通信的方式了，最近项目换成kts的方式，于是把aidl也换成了统一的方式，其中遇到了很多问题，这里…...

编程日记 2025/8/2 22:19:19

【C++】类和对象（匿名对象）

匿名对象用类型(实参) 定义出来的对象叫做匿名对象，相比之前我们定义的类型对象名(实参) 定义出来叫有名对象匿名对象生命周期只在当前一行，一般临时定义一个对象当前用一下即可，就可以定义匿名对象。 class A { public:A(int a 0):_a…...

编程日记 2025/8/2 22:16:35

Spring boot 3.4 后 SDK 升级，暨 UI API/MCP 计划

PS 写这篇文章后看到 A Deep Dive Into MCP and the Future of AI Tooling | Andreessen HorowitzWe explore what MCP is, how it changes the way AI interacts with tools, what developers are already building, and the challenges that still need solving. https://a1…...

编程日记 2025/8/2 22:19:20

使用Helm安装、升级、回滚Kubernetes应用

前言在我之前做的项目里，我们对Microk8s微服务的更新是通过自制tar包的方式做的, tar包存储了镜像和YAML文件。每次升级时，我们需要先删除所有的YAML资源，然后重新创建新的资源。这种方式存在以下问题： 服务中断：…...

编程日记 2025/8/2 22:20:35

Text-to-SQL将自然语言转换为数据库查询语句

有关Text-To-SQL方法，可以查阅我的另一篇文章，Text-to-SQL方法研究直接与数据库对话-text2sql Text2sql就是把文本转换为sql语言，这段时间公司有这方面的需求，调研了一下市面上text2sql的方法，比如阿里的Chat2DB,麻…...

编程日记 2025/7/30 7:09:24

gin学习

gin学习笔记，不仅包含了基本的增删查改外，还包括参数传递，上传下载，模版、session与中间件等，方便收藏自习可用文章目录获得个请求get打印字符串get请求xmlget请求跳转http方法路由可以通过Context的Param方法来获取…...

编程日记 2025/8/2 11:33:11

【HarmonyOS NEXT】关键资产存储开发案例

在 iOS 开发中 Keychain 是一个非常安全的存储系统，用于保存敏感信息，如密码、证书、密钥等。与文件系统不同，Keychain 提供了更高的安全性，因为它对数据进行了加密，并且只有经过授权的应用程序才能访问存储的数据。那…...

编程日记 2025/7/27 6:06:51

高德终端技术总结：高可用架构如何练成？

前言高德地图作为国民级应用，特别是出行场景的独特性，要确保在线导航高并发和交通安全级的超稳定性，这对技术团队提出异乎寻常的高要求，无论是终端、云端，还是“终端-云端”之间的连接，都必须实现“高可用…...

编程日记 2025/8/2 19:13:31

STM32八股【3】------RAM和片上FLASH

1、RAM和FLASH构成 1.RAM ┌──────────────────────────┐ │ 栈区 (Stack) │ ← 从RAM顶端向下扩展（存储局部变量、函数调用信息） │--------------------------│ │ 堆区 (Heap) │ ← …...

编程日记 2025/8/2 12:44:05

Apache Doris

Apache Doris介绍 Apache Doris 是一个基于 MPP 架构的高性能、实时的分析型数据库，以极速易用的特点被人们所熟知，仅需亚秒级响应时间即可返回海量数据下的查询结果，不仅可以支持高并发的点查询场景，也能支持高吞吐的复杂分析场…...

编程日记 2025/8/1 19:22:38

Debezium介绍

1.什么是Debezium Debezium 是一个开源的分布式平台，用于捕获数据库的变更事件（CDC，Change Data Capture）。它能够实时捕获数据库中的行级更改，并将这些更改作为事件流发送到消息中间件（如 Apache Kafka&a…...

编程日记 2025/7/30 15:23:32

奇迹科技：蓝牙网关赋能少儿篮球教育的创新融合案例研究

一、引言本文研究了福建奇迹运动体育科技有限公司（简称‘奇迹科技’）如何利用其创新产品体系和桂花网蓝牙网关M1500，与少儿篮球教育实现深度融合。重点分析其在提升教学效果、保障训练安全、优化个性化教学等方面的实践与成效，为…...

编程日记 2025/7/29 12:41:30

Python散点图(Scatter Plot)：高阶分析、散点图矩阵、三维散点图及综合应用

散点图：数据分析的利器在数据分析领域，散点图是一种直观且强大的可视化工具，广泛应用于揭示变量间的相关性以及识别数据集中的异常值。本文将深入探讨散点图的这两种关键功能，并结合实际案例与Python代码示例，带您全面了解散点图的应用。一、散点图如何展示变量间的相…...

编程日记 2025/7/28 1:20:56

计算机网络层超全解析：从IP协议到路由算法

🌐 （专业详解生活化类比，逻辑一镜到底） 📖 网络层的核心使命核心任务：在不同网络间为数据包选择最佳路径，实现端到端通信。类比：快递公司总部（网络层）根据…...

编程日记 2025/8/2 19:46:30

RoboVQA

RoboVQA：面向机器人技术的多模态长时推理摘要我们提出了一种可扩展、自下而上且具有内在多样性的数据收集方案，适用于中长时高级推理任务，其吞吐量比传统的自上而下分步收集方法高2.2倍。通过在3栋办公楼内使用多种实体（机器人、人类、使用抓取工具的人类）执行任意用…...

编程日记 2025/7/25 11:23:36

javascript语法入门

一、变量声明在JavaScript中，可以使用var、let和const来声明变量。 javascript var name "张三"; let age 20; 二、数据类型 JavaScript中有7种基本数据类型：undefined、null、boolean、string、symbol、number，以及object。…...

编程日记 2025/7/30 1:10:59

前端字段名和后端不一致？解锁 JSON 映射的“隐藏规则” ！！！

🚀 前端字段名和后端不一致？解锁 JSON 映射的“隐藏规则” 🌟 嘿，技术冒险家们！👋 今天我们要聊一个开发中常见的“坑”：前端传来的 JSON 参数字段名和后端对象字段名不一致，会发生…...

编程日记 2025/7/30 14:31:13

Java——ArrayList集合

ArrayList：基于动态数组实现，支持随机访问，适合频繁的随机访问操作，但在插入和删除元素时性能较差。技术层面介绍所属类库：ArrayList 位于 java.util 包中，它实现了 List 接口，因此具备 Lis…...

编程日记 2025/7/31 20:06:42

基于python+django的图书借阅网站-图书借阅管理系统源码+运行步骤

该系统是基于pythondjango开发的在线图书借阅管理系统。系统适合场景：大学生、课程作业、系统设计、毕业设计。演示地址前台地址： http://book.gitapp.cn 后台地址：http://book.gitapp.cn/#/admin 后台管理帐号： 用户名&…...

编程日记 2025/8/1 8:13:44

Flutter运行错误：UG! exception in phase ‘semantic analysis‘

最近在Mac Mini M4上通过Android Studio导入Flutter项目并运行，结果一直跑不起来，错误日志如下： 执行命令查看版本信息： flutter doctor --verbose通过输出信息Java version OpenJDK Runtime Environment (build 21.0.41242208…...

编程日记 2025/7/17 4:34:29

Python-docx库详解：轻松实现Word文档自动化生成与图片尺寸控制

Python-docx库详解：轻松实现Word文档自动化生成与图片尺寸控制在现代办公自动化的浪潮中，文档处理是一项不可或缺的任务。Python作为一种强大的编程语言，提供了丰富的库来简化这些任务。其中，python-docx库是处理Word文档的有力…...

编程日记 2025/8/1 19:18:58

【NLP 42、实践 ⑪ 用Bert模型结构实现自回归语言模型的训练】

目录数据文件一、模型定义 1.模型初始化代码运行流程 2.前向传播，计算损失 ⭐ 代码运行流程二、加载语料代码运行流程三、随机生成样本代码运行流程四、建立模型五、采样策略选择代码运行流程六、模型效果测试代码运行流程七、模型训练代码运行流程 …...

编程日记 2025/7/29 5:00:07

HTTPS

目录一 HTTPS是什么二加密三加密方案四 CA机构/证书五最终方案(对称密钥/非对称密钥/CA证书)和总体流程一 HTTPS是什么在应用层存在SSL，TLS(HTTP之下，传输层之上)加密/解密安全协议，如果HTTP经过这个协议，对端也走…...

编程日记 2025/7/31 16:15:46

electron框架（4.0）electron-builde和electron Forge的打包方式

----使用electron-builder打包（需要魔法） --安装electron-builder: npm install electron-builder -D--package.json中进行相关配置： {"name": "video-tools","version": "1.0.0","main&quo…...

编程日记 2025/7/23 11:14:19

SaaS系统的销售微服务与权限微服务边界设计

在设计SaaS系统的销售微服务与权限微服务的边界时，需要结合领域驱动设计（DDD）和微服务拆分原则，确保高内聚、低耦合。以下是结合微服务架构原则、多租户SaaS需求及权限管理场景的完整设计方案，整合了权限服务与销售服务…...

编程日记 2025/7/29 10:42:55

Unity-AI-Deepseek生成的生成模型代码

结果能用，不是很理想，从左到右，分别是body,眼睛,演睫毛,手指套（如果你知道这是什么）结果不是很理想 (下面代码已包含，修复的切线只能传Vector3参数，Unity2022测试） 你们帮我看看…...

编程日记 2025/7/31 2:02:23

Django REST Framework 请求封装源码解析与实现流程

版本说明： Django: V4.2.20 Django Rest Framework: V3.15.2 一、核心封装流程示意图 #mermaid-svg-qXJLIa9Bx1TCiPSN {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-qXJLIa9Bx1TCiPSN .error-icon{fill…...

编程日记 2025/8/2 19:34:42

简介PyCDE：Python CIRCT Design Entry

简介PyCDE：Python CIRCT Design Entry 引言在硬件设计和验证领域，随着设计复杂性的增加，传统的方法往往难以满足现代设计的需求。PyCDE（Python CIRCT Design Entry）作为CIRCT项目的一部分，旨在为硬件设计…...

编程日记 2025/8/1 5:43:49

Python实现deepseek接口的调用

简介：DeepSeek 是一个强大的大语言模型，提供 API 接口供开发者调用。在 Python 中，可以使用 requests 或 httpx 库向 DeepSeek API 发送请求，实现文本生成、代码补全，知识问答等功能。本文将介绍如何在 Python 中调用 …...

编程日记 2025/8/1 5:43:55

考研课程安排（自用）

文章目录 408数据结构（王道）计算机组成原理（王道）操作系统（王道）计算机网络（湖科大版） 数学一高等数学（微积分）线性代数和概率论 408 数据结构（王…...

编程日记 2025/7/23 13:25:37

Mybatis操作数据库（注解+xml两个方式）

文章目录 1.个人回顾2.关于mybatis注解的说明3.字段和属性不匹配的解决方案3.1第一个方案3.2第二个方案3.3第三个方案 4.xml路径配置5.xml里面的字段映射 1.个人回顾刚刚翻看了一下自己的这个之前写的博客，上一次和这个javaee相关的博客还是去年写的，也…...

编程日记 2025/7/31 1:39:19

文心快码使用体验与介绍

一、文心快码的核心作用文心快码是百度基于文心大模型开发的智能代码助手，核心价值包括： 代码生成与补全通用开发：根据注释生成HTML/CSS/JS、Python、Java等代码C专项：生成类定义、STL容器操作、智能指针代码（如st…...

编程日记 2025/8/1 20:34:48

一、差分

二、一维差分

三、海底高铁

四、二维差分

五、地毯

相关文章：