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

【蓝桥杯每日一题】差分算法

🍎 博客主页:🌙@披星戴月的贾维斯
🍎 欢迎关注:👍点赞🍃收藏🔥留言
🍇系列专栏:🌙 蓝桥杯
🌙我与杀戮之中绽放,亦如黎明的花朵🌙
🍉一起加油,去追寻、去成为更好的自己!

蓝桥杯倒计时 44天

文章目录

  • 🍎、差分
  • 🍎、例题分析
        • 🍇、(AcWing)差分
        • 🍇、(AcWing)差分矩阵
        • 🍇、(AcWing)改变数组元素
  • 🍎、总结

提示:以下是本篇文章正文内容,下面案例可供参考


🍎、差分

🍉、差分的简单概念
    差分在数学领域的理解:有数列a1 a2 a3……an……,其中an+1= an + d( n = 1,2,…n )d为常数,称为公差, 即 d = an+1 -an , 这就是一个差分, 通常用D(an) = an+1- an来表示,于是有D(an)= d , 这是一个最简单形式的差分方程。
    差分在计算机领域的理解:差分是前缀和的逆运算,差分的作用是在O(1)的时间复杂度下,让一段区间,例如是[i, n]区间内的每一个数都加或者减同一个数。

    一维差分的公式:s[L] += c , s[R + 1] -= c;
其中L是区间的左端点,R是区间的右端点。
    二维差分的公式:S[x1][y2] += c;   s[x1][y2 + 1] -= c;
                                 S[x2 + 1] -= c;   s[x2 + 1][y2 + 1] += c;

    对于差分数组的理解:原数组a[]是差分数组b[]的前缀和,a[i] = b[0] + b[1] + b[2] + … + b[i],所以在最后输出结果时一维差分公式:a[i] = a[i - 1] + b[i];
二维差分最后输出结果的公式是: a[i][j] = a[i - 1][j] + a[i][j - 1] + b[i][j]

🍉、图解一维前缀和
在这里插入图片描述
🍉、图解二维前缀和
在这里插入图片描述


🍎、例题分析

🍇、(AcWing)差分

本题链接: 差分
在这里插入图片描述
简单分析题意:就是在q次询问中,每次在原数组的一段区间上加上一个值C,最后输出q次询问后的结果。
代码示例:

#include<iostream>
using namespace std;
const int N = 100010;
int n, m;
int a[N], b[N];
void insert(int l, int r, int c)
{b[l] += c;b[r + 1] -= c;
}
int main ()
{cin >> n >> m;for(int i = 1; i <= n; i++){cin >> a[i];insert(i, i, a[i]);//对b[i]的初始化}while(m --){int l, r, c;cin >> l >> r >> c;insert(l, r, c);}for(int i = 1; i <= n; i++){a[i] = a[i - 1] + b[i];cout << a[i] << ' ';}cout << endl;return 0;
}

🍇、(AcWing)差分矩阵

本题链接: 差分矩阵
在这里插入图片描述
简单分析题意:就是在q次查询中,每次在一个区间内加/减一个值。
代码示例:

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1010;
int b[N][N], a[N][N];
int n, m, q;
void add(int x1, int y1, int x2, int y2, int c)
{b[x1][y1] += c;b[x1][y2 + 1] -= c;b[x2 + 1][y1] -= c;b[x2 + 1][y2 + 1] += c;
}
int main ()
{cin >> n >> m >> q;for(int i = 1; i <= n; i++)for(int j = 1; j <= m; j++){scanf("%d", &a[i][j]);add(i, j, i, j, a[i][j]); // 每次输入一个a[i],就要初始化一下b差分数组}while(q --){int x1, y1, x2, y2, c;cin >> x1 >> y1 >> x2 >> y2 >> c;add(x1, y1, x2, y2, c);}for(int i = 1; i <=n;  i++){for(int j = 1; j <= m; j++){a[i][j] = a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1] + b[i][j];//这里使用二维前缀和公式printf("%d ", a[i][j]);}puts("");}return 0;
}

🍇、(AcWing)改变数组元素

本题链接: 改变数组元素
在这里插入图片描述
分析题意:
在这里插入图片描述
代码示例:

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;const int N = 200010;
int b[N];
int n;
int main ()
{int t;cin >> t;while(t --){scanf("%d", &n);memset(b, 0, 4 * (n + 1));for(int i = 1; i <= n; i++){int x;scanf("%d", &x);x = min(x, i);int l = i - x + 1, r = i;//差分数组的左右两端b[l]++, b[r + 1]--; //差分操作的模板}    //求原数组,就是差分数组的前缀和for(int i = 1; i <= n; i++){b[i] += b[i - 1]; //差分和前缀和是互逆操作}for(int i = 1; i <= n; i++)printf("%d ", !!b[i]); // 原来是0的还是0,原来大于等于1的就变为1了。puts("");}return 0;
}

🍎、总结

    本文简要介绍了差分的简要概念和几道差分的经典例题,希望大家读后能有所收获!

相关文章:

【蓝桥杯每日一题】差分算法

&#x1f34e; 博客主页&#xff1a;&#x1f319;披星戴月的贾维斯 &#x1f34e; 欢迎关注&#xff1a;&#x1f44d;点赞&#x1f343;收藏&#x1f525;留言 &#x1f347;系列专栏&#xff1a;&#x1f319; 蓝桥杯 &#x1f319;我与杀戮之中绽放&#xff0c;亦如黎明的花…...

MyBatis Plus 数据库字段加密处理

目录1.场景介绍2.Maven依赖2.AESUtil.java 加解密工具类3.字段处理类4.修改 MyBatis Plus 查询4.1 修改表对应实体类4.2 修改加密字段对应属性4.3 修改 xml 使用 ResultMap4.4 修改 xml 中 el 表达式5.测试结果6.MyBatis Plus 缺陷补充&#xff1a;测试实例1 查询测试1.1 查询信…...

openpose在win下环境配置

1.下载OpenPose库 以下二选一进行下载源码 (1)git进行下载 打开GitHub Desktop或者Powershell git clone https://github.com/CMU-Perceptual-Computing-Lab/openpose cd openpose/ git submodule update --init --recursive --remote(2)在github上手动下载 由于下载环境问…...

【剑指offer-C++】JZ16:数值的整数次方

【剑指offer】JZ16&#xff1a;数值的整数次方题目描述解题思路题目描述 描述&#xff1a;实现函数 double Power(double base, int exponent)&#xff0c;求base的exponent次方。 注意&#xff1a; 1.保证base和exponent不同时为0。 2.不得使用库函数&#xff0c;同时不需要…...

了解Axios及其运用方式

Axios简介 axios框架全称&#xff08;ajax – I/O – system&#xff09;&#xff1a; 基于promise用于浏览器和node.js的http客户端&#xff0c;因此可以使用Promise API 一、axios是干啥的 说到axios我们就不得不说下Ajax。在旧浏览器页面在向服务器请求数据时&#xff0c;…...

【LeetCode】剑指 Offer(7)

目录 写在前面&#xff1a; 题目剑指 Offer 17. 打印从1到最大的n位数 - 力扣&#xff08;Leetcode&#xff09; 题目的接口&#xff1a; 解题思路&#xff1a; 代码&#xff1a; 过啦&#xff01;&#xff01;&#xff01; 题目&#xff1a;剑指 Offer 18. 删除链表的节…...

Python:try except 异常处理整理

目录 一、try except异常处理的语句格式 二、获取相关异常信息 &#xff08;1&#xff09;sys.exec_info() 三、traceback模块的常用方式 &#xff08;1&#xff09;traceback.print_tb(tb, limitNone, fileNone) 打印指定堆栈异常信息 &#xff08;2&#xff09;tracebac…...

Redis Lua脚本的详细介绍以及使用入门

Redis Lua脚本的详细介绍以及使用入门。 文章目录Redis Lua脚本的引入开源软件的可扩展性Redis的扩展性脚本Redis Lua脚本的基本使用通过EVAL命令执行Lua脚本通过脚本与Redis交互Java中调用Redis Lua脚本Java调用Lua脚本的方式Redis Lua脚本的使用建议脚本缓存脚本缓存稳定性脚…...

synchronized和ReentrantLock有什么区别呢?

第15讲 | synchronized和ReentrantLock有什么区别呢&#xff1f; 从今天开始&#xff0c;我们将进入 Java 并发学习阶段。软件并发已经成为现代软件开发的基础能力&#xff0c;而 Java 精心设计的高效并发机制&#xff0c;正是构建大规模应用的基础之一&#xff0c;所以考察并发…...

SVHN数据集下载及使用方法

街景门牌号数据集&#xff08;SVHN&#xff09;&#xff0c;这是一个现实世界数据集&#xff0c;用于开发目标检测算法。它需要最少的数据预处理过程。它与 MNIST 数据集有些类似&#xff0c;但是有着更多的标注数据&#xff08;超过 600,000 张图像&#xff09;。这些数据是从…...

产业安全公开课:2023年DDoS攻击趋势研判与企业防护新思路

2023年&#xff0c;全球数字化正在加速发展&#xff0c;网络安全是数字化发展的重要保障。与此同时&#xff0c;网络威胁日益加剧。其中&#xff0c;DDoS攻击作为网络安全的主要威胁之一&#xff0c;呈现出连年增长的态势&#xff0c;给企业业务稳定带来巨大挑战。2月21日&…...

Docker 容器命令 和安装各种镜像环境

CentOS安装Docker 1.1.卸载&#xff08;可选&#xff09; 如果之前安装过旧版本的Docker&#xff0c;可以使用下面命令卸载&#xff1a; yum remove docker \docker-client \docker-client-latest \docker-common \docker-latest \docker-latest-logrotate \docker-logrotat…...

【数据结构】顺序表的深度剖析

&#x1f307;个人主页&#xff1a;平凡的小苏 &#x1f4da;学习格言&#xff1a;别人可以拷贝我的模式&#xff0c;但不能拷贝我不断往前的激情 &#x1f6f8;C语言专栏&#xff1a;https://blog.csdn.net/vhhhbb/category_12174730.html &#x1f680;数据结构专栏&#xff…...

当面试官问“你的SQL能力怎么样”时,怎么回答才不会掉进应聘陷阱?

在某平台看到一个比较实际的问题&#xff0c;在这里分享给职场新人。 SQL已经是职场最常用的一种编程语言&#xff0c;所以应聘技术或非技术岗位&#xff0c;都可能会被问道一个问题&#xff1a;你的SQL能力怎么样&#xff1f; 对于职场新人来说&#xff08;SQL高手可以无视下…...

AI作画—中国画之山水画

山水画&#xff0c;简称“山水”&#xff0c;中国画的一种&#xff0c;描写山川自然景色为主体的绘画。山水画在我国绘画史中占有重要的地位。 山水画形成于魏晋南北朝时期&#xff0c;但尚未从人物画中完全分离。隋唐时始终独立&#xff0c;五代、北宋时趋于成熟&#xff0c;…...

Java:Java与Python — 编码大战

Java和Python是目前市场上最热门的两种编程语言&#xff0c;因为它们具有通用性、高效性和自动化能力。两种语言都有各自的优点和缺点&#xff0c;但主要区别在于Java 是静态类型的&#xff0c;Python是动态类型的。它们有相似之处&#xff0c;因为它们都采用了“一切都是对象”…...

山东专精特新各地市扶持政策

青岛市奖励政策&#xff1a;新认定为市隐形、省“专精特新”及省瞪羚、角兽的我市企业&#xff0c;分别给予50万元、30万元、50万元、300万元的一次性奖励。奖励金额&#xff1a;省级30万济南市奖励政策&#xff1a;对被认定的国家专精特新 “小巨人”企业一次性给予200万元奖励…...

持续事务管理过程中的事件驱动

比较官方的定义&#xff1a;事件驱动是指在持续事务管理过程中&#xff0c;进行决策的一种策略&#xff0c;即跟随当前时间点上出现的事件&#xff0c;调动可用资源&#xff0c;执行相关任务&#xff0c;使不断出现的问题得以解决&#xff0c;防止事务堆积。在计算机编程、公共…...

【手把手一起学习】(三) Altium Designer 20 原理图库添加元件

1 添加元件 元件符号是元件在原理图上的表现形式&#xff0c;主要由边框、管脚、名称等组成&#xff0c;原理图库中的元件管脚(顺序&#xff0c;间距等)与电子元件实物的引脚严格对应&#xff0c;绘制原理图库时&#xff0c;一定参考元件规格书和芯片数据手册中的说明&#xf…...

设计模式-行为型模式:观察者模式

目录 1、简介 2、组成部分 3、优缺点 4、使用场景 5、代码实现 1、简介 观察者模式是一种软件设计模式&#xff0c;它定义了一种一对多的依赖关系&#xff0c;让多个观察者对象同时监听一个主题对象&#xff0c;当主题对象发生变化时&#xff0c;所有的观察者对象都会得到…...

mongodb源码分析session执行handleRequest命令find过程

mongo/transport/service_state_machine.cpp已经分析startSession创建ASIOSession过程&#xff0c;并且验证connection是否超过限制ASIOSession和connection是循环接受客户端命令&#xff0c;把数据流转换成Message&#xff0c;状态转变流程是&#xff1a;State::Created 》 St…...

在四层代理中还原真实客户端ngx_stream_realip_module

一、模块原理与价值 PROXY Protocol 回溯 第三方负载均衡&#xff08;如 HAProxy、AWS NLB、阿里 SLB&#xff09;发起上游连接时&#xff0c;将真实客户端 IP/Port 写入 PROXY Protocol v1/v2 头。Stream 层接收到头部后&#xff0c;ngx_stream_realip_module 从中提取原始信息…...

如何为服务器生成TLS证书

TLS&#xff08;Transport Layer Security&#xff09;证书是确保网络通信安全的重要手段&#xff0c;它通过加密技术保护传输的数据不被窃听和篡改。在服务器上配置TLS证书&#xff0c;可以使用户通过HTTPS协议安全地访问您的网站。本文将详细介绍如何在服务器上生成一个TLS证…...

【JavaSE】绘图与事件入门学习笔记

-Java绘图坐标体系 坐标体系-介绍 坐标原点位于左上角&#xff0c;以像素为单位。 在Java坐标系中,第一个是x坐标,表示当前位置为水平方向&#xff0c;距离坐标原点x个像素;第二个是y坐标&#xff0c;表示当前位置为垂直方向&#xff0c;距离坐标原点y个像素。 坐标体系-像素 …...

如何理解 IP 数据报中的 TTL?

目录 前言理解 前言 面试灵魂一问&#xff1a;说说对 IP 数据报中 TTL 的理解&#xff1f;我们都知道&#xff0c;IP 数据报由首部和数据两部分组成&#xff0c;首部又分为两部分&#xff1a;固定部分和可变部分&#xff0c;共占 20 字节&#xff0c;而即将讨论的 TTL 就位于首…...

【Oracle】分区表

个人主页&#xff1a;Guiat 归属专栏&#xff1a;Oracle 文章目录 1. 分区表基础概述1.1 分区表的概念与优势1.2 分区类型概览1.3 分区表的工作原理 2. 范围分区 (RANGE Partitioning)2.1 基础范围分区2.1.1 按日期范围分区2.1.2 按数值范围分区 2.2 间隔分区 (INTERVAL Partit…...

Xen Server服务器释放磁盘空间

disk.sh #!/bin/bashcd /run/sr-mount/e54f0646-ae11-0457-b64f-eba4673b824c # 全部虚拟机物理磁盘文件存储 a$(ls -l | awk {print $NF} | cut -d. -f1) # 使用中的虚拟机物理磁盘文件 b$(xe vm-disk-list --multiple | grep uuid | awk {print $NF})printf "%s\n"…...

蓝桥杯 冶炼金属

原题目链接 &#x1f527; 冶炼金属转换率推测题解 &#x1f4dc; 原题描述 小蓝有一个神奇的炉子用于将普通金属 O O O 冶炼成为一种特殊金属 X X X。这个炉子有一个属性叫转换率 V V V&#xff0c;是一个正整数&#xff0c;表示每 V V V 个普通金属 O O O 可以冶炼出 …...

【MATLAB代码】基于最大相关熵准则(MCC)的三维鲁棒卡尔曼滤波算法(MCC-KF),附源代码|订阅专栏后可直接查看

文章所述的代码实现了基于最大相关熵准则(MCC)的三维鲁棒卡尔曼滤波算法(MCC-KF),针对传感器观测数据中存在的脉冲型异常噪声问题,通过非线性加权机制提升滤波器的抗干扰能力。代码通过对比传统KF与MCC-KF在含异常值场景下的表现,验证了后者在状态估计鲁棒性方面的显著优…...

通过 Ansible 在 Windows 2022 上安装 IIS Web 服务器

拓扑结构 这是一个用于通过 Ansible 部署 IIS Web 服务器的实验室拓扑。 前提条件&#xff1a; 在被管理的节点上安装WinRm 准备一张自签名的证书 开放防火墙入站tcp 5985 5986端口 准备自签名证书 PS C:\Users\azureuser> $cert New-SelfSignedCertificate -DnsName &…...