算法竞赛之差分进阶——等差数列差分 python
目录
- 前置知识
- 进入正题
- 实战演练
前置知识
给定区间 [ l, r ],让我们把数组中的[ l, r ] 区间中的每一个数加上c,即 a[ l ] + c , a[ l + 1 ] + c , a[ l + 2] + c , a[ r ] + c;
怎么做?很简单,差分一下即可
还不会的小伙伴点此进入学习
进入正题
进阶一下:
给定区间 [ l, r ],把数组[ l, r ] 区间中的数加上一个首项s、末项e、公差为d的等差数列,
即 a[ l ] + s , a[ l + 1 ] + s+d , a[ l + 2 ] + s+2d ······a[ r ] + e
怎么实现?先给出结论
a[l] += s,
a[l + 1] += d - s
a[r + 1] -=d + e
a[r + 2] += e
再对a数组做两次前缀和,即得到ans
为何?
下面听我娓娓道来~
简单举个例子:
假设数组a=【0,0,0,0,0,0,0,0】
现要求对 a[1] 到 a[5] 这5个数字 分别加上以s为首项,d为公差,e为末项的等差数列,即a=【0,s,s+d,s+2d,s+3d,s+4d(e),0,0】
如何得到呢?我们先做一次差分试试:
diff1=【0,s,d,d,d,d,-e,0】什么也看不出来对吧。
再对差分数组做差分:
diff2=【0,s,d-s,0,0,0,-e-d,e】
哎,这不是一开始所进行的操作吗?
a[1]+=s
a[2]+=d-s
a[6]-=d+e
a[7]+=e
一切终成闭环
好了,实际运用的时候到了
实战演练
P4231 三步必杀 https://www.luogu.com.cn/problem/P4231



不了解异或运算可点此进入
题解code:
n, m = map(int, input().split())
ans = [0] * (n + 3)
for i in range(m):l, r, s, e = map(int, input().split())d = int((e - s) / (r - l))ans[l] += sans[l + 1] += d - sans[r + 1] -= d + eans[r + 2] += e # 实现等差数列差分for i in range(1, len(ans)):ans[i] += ans[i - 1]
for i in range(1, len(ans)):ans[i] += ans[i - 1] # 两次前缀和xor = 0
for i in ans:xor ^= i
print(f'{xor} {max(ans)}')
如果有更多问题或需要进一步的帮助,可以在评论区留言讨论哦!
如果喜欢的话,请给博主点个关注 谢谢
相关文章:
算法竞赛之差分进阶——等差数列差分 python
目录 前置知识进入正题实战演练 前置知识 给定区间 [ l, r ],让我们把数组中的[ l, r ] 区间中的每一个数加上c,即 a[ l ] c , a[ l 1 ] c , a[ l 2] c , a[ r ] c; 怎么做?很简单,差分一下即可 还不会的小伙伴点此进入学习 进入正题 …...
20250121在Ubuntu20.04.6下使用Linux_Upgrade_Tool工具给荣品的PRO-RK3566开发板刷机
sudo upgrade_tool uf update.img 20250121在Ubuntu20.04.6下使用Linux_Upgrade_Tool工具给荣品的PRO-RK3566开发板刷机 2025/1/21 11:54 百度:ubuntu RK3566 刷机 firefly rk3566 ubuntu upgrade_tool烧写详解 https://wiki.t-firefly.com/Core-3566JD4/03-upgrad…...
【Elasticsearch】Springboot编写Elasticsearch的RestAPI
RestAPI 初始化RestClient创建索引库Mapping映射 判断索引库是否存在删除索引库总结 ES官方提供了各种不同语言的客户端,用来操作ES。这些客户端的本质就是组装DSL语句,通过http请求发送给ES。 官方文档地址 由于ES目前最新版本是8.8,提供了全…...
Python数据可视化(够用版):懂基础 + 专业的图表抛给Tableau等专业绘图工具
我先说说文章标题中的“够用版”啥意思,为什么这么写。 按照我个人观点,在使用Python进行数据分析时,我们有时候肯定要结合到图表去进行分析,去直观展现数据的规律和特定,那么我们肯定要做一些简单的可视化࿰…...
1.21学习
misc buuctf-爱因斯坦 下载附件后是一个图片,用stegsolve查看一下,各个色都没有问题,然后看一下数据分析,除此之外无其他信息,再看看图片属性,不知道是啥,用随波逐流进行binwalk文件提取然后得…...
SoftGNSS软件接收机源码阅读(一)程序简介、运行调试、执行流程
原始 Markdown文档、Visio流程图、XMind思维导图见:https://github.com/LiZhengXiao99/Navigation-Learning 文章目录 一、softGNSS 简介1、概述2、相关工作3、我用 softGNSS 做的事4、文件结构5、程序执行流程图 二、程序使用1、射频前端2、参数设置3、处理开源数据…...
Spring Boot AOP实现动态数据脱敏
依赖&配置 <!-- Spring Boot AOP起步依赖 --> <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-aop</artifactId> </dependency>/*** Author: 说淑人* Date: 2025/1/18 23:03* Desc…...
Leetcode刷题-二分查找
灵神的二分视频:二分查找 红蓝染色法_哔哩哔哩_bilibili 34 class Solution:def searchRange(self, nums: List[int], target: int) -> List[int]:right len(nums) - 1left 0res [-1,-1]mid int((right left)/2)while right > left:if nums[mid] < …...
凭证Account Assignment的校验(FAGL_VALIDATE)
本文主要介绍在S4 HANA OP中凭证Account Assignment的校验配置。具体请参照如下内容: 目录 1. 定义Account Assignment校验策略(FAGL_VALIDATE) 1.1 Derivation Rule 1.2 Assignment 1.3 Initialize 1.4 Enhancement 2. 分配Account Assignment校验策略给公司…...
【20】Word:小许-质量管理-论文❗
目录 题目 NO1.2.3.4.5 NO6.7 NO8 NO9 NO10.11 题目 NO1.2.3.4.5 另存为“Word.docx”文件在考生文件夹下,F12Fn是另存为的作用布局→页面设置对话框→纸张:大小A4→页边距:上下左右不连续ctrl选择除表格外的所有内容→开始→字体对…...
二十八、Qos服务质量
Qos服务质量 一、产生原因 Resources也不是万能的,使用一段时间后,资源总量可能会超过接节点配置。 根据这个情况,我们可以设置,清除资源。给pod配置,按顺序删除 二、服务质量QoS分类 Guaranteed:最高服务质量(保证),当宿主机内存不够时,会先kill掉QoS为BestEffort…...
Flutter 改完安卓 applicationId 后App 闪退问题。
一、问题 当我们项目创建完,想 build.gradle 改 applicationId 的时候,再次执行的时候可能会出现 app 闪退问题, 控制台不显示任何错误提示 也不出现 Exit 停止运行的情况。(像下方这样, 而 app 只是在模拟器中一闪而…...
es 3期 第25节-运用Rollup减少数据存储
#### 1.Elasticsearch是数据库,不是普通的Java应用程序,传统数据库需要的硬件资源同样需要,提升性能最有效的就是升级硬件。 #### 2.Elasticsearch是文档型数据库,不是关系型数据库,不具备严格的ACID事务特性ÿ…...
小菜鸟系统学习Python第三天
1.优先级问题: 结论: 幂运算>正负号>加减乘除和整除>比较运算符>逻辑运算符 2.三元运算符 3.assert断言:抛出AssertionError异常 4.for循环 4. 5.break和continue...
七.网络模型
最小(支撑)树问题 最小部分树求解: 破圈法:任取一圈,去掉圈中最长边,直到无圈; 加边法:取图G的n个孤立点{v1,v2,…, vn }作为一个支撑图,从最短…...
1170 Safari Park (25)
A safari park(野生动物园)has K species of animals, and is divided into N regions. The managers hope to spread the animals to all the regions, but not the same animals in the two neighboring regions. Of course, they also realize that t…...
数字图像处理:实验五
uu们!大家好,欢迎来到数字图像处理第五章节内容的学习,在本章中有关空间滤波的理论学习是十分重要的,所以建议大家要去用心的学习本章,在之后的传感器的相关图像采集时,不可避免的会有噪声等的影响…...
2024我在csdn走过的路
自我介绍 ✏️博客名✏️: zy_destiny 🌸粉丝数🌸: 1万 🌿擅长领域🌿: 人工智能 👀欢迎访问👀: 我的主页 我的2024 回顾下2024年,起点要从去年写…...
网络安全等级保护基本要求——等保二级
《信息安全技术网络安全等级保护基本要求》GB/T22239-2019 7.1 安全通用要求 7.1.1 安全物理环境 7.1.1.1 物理位置选择 本项要求包括: a) 机房场地应选择在具有防震、防风和防雨等能力的建筑内;b) 机房场地应避免设在建筑物的顶层或地下室,否则应加…...
了解 .mgJSON 文件
.mgJSON (Motion Graphics JSON)是一个基于标准 JSON 格式的文件扩展名,专门用于存储和交换与动态图形、动画和多媒体应用相关的数据。该格式支持静态和动态数据流,能够精确描述动画、物体变换、图形效果等。 .mgJSON 文件通过层级…...
应用升级/灾备测试时使用guarantee 闪回点迅速回退
1.场景 应用要升级,当升级失败时,数据库回退到升级前. 要测试系统,测试完成后,数据库要回退到测试前。 相对于RMAN恢复需要很长时间, 数据库闪回只需要几分钟。 2.技术实现 数据库设置 2个db_recovery参数 创建guarantee闪回点,不需要开启数据库闪回。…...
基于距离变化能量开销动态调整的WSN低功耗拓扑控制开销算法matlab仿真
目录 1.程序功能描述 2.测试软件版本以及运行结果展示 3.核心程序 4.算法仿真参数 5.算法理论概述 6.参考文献 7.完整程序 1.程序功能描述 通过动态调整节点通信的能量开销,平衡网络负载,延长WSN生命周期。具体通过建立基于距离的能量消耗模型&am…...
系统设计 --- MongoDB亿级数据查询优化策略
系统设计 --- MongoDB亿级数据查询分表策略 背景Solution --- 分表 背景 使用audit log实现Audi Trail功能 Audit Trail范围: 六个月数据量: 每秒5-7条audi log,共计7千万 – 1亿条数据需要实现全文检索按照时间倒序因为license问题,不能使用ELK只能使用…...
Matlab | matlab常用命令总结
常用命令 一、 基础操作与环境二、 矩阵与数组操作(核心)三、 绘图与可视化四、 编程与控制流五、 符号计算 (Symbolic Math Toolbox)六、 文件与数据 I/O七、 常用函数类别重要提示这是一份 MATLAB 常用命令和功能的总结,涵盖了基础操作、矩阵运算、绘图、编程和文件处理等…...
Mobile ALOHA全身模仿学习
一、题目 Mobile ALOHA:通过低成本全身远程操作学习双手移动操作 传统模仿学习(Imitation Learning)缺点:聚焦与桌面操作,缺乏通用任务所需的移动性和灵活性 本论文优点:(1)在ALOHA…...
代码规范和架构【立芯理论一】(2025.06.08)
1、代码规范的目标 代码简洁精炼、美观,可持续性好高效率高复用,可移植性好高内聚,低耦合没有冗余规范性,代码有规可循,可以看出自己当时的思考过程特殊排版,特殊语法,特殊指令,必须…...
【LeetCode】3309. 连接二进制表示可形成的最大数值(递归|回溯|位运算)
LeetCode 3309. 连接二进制表示可形成的最大数值(中等) 题目描述解题思路Java代码 题目描述 题目链接:LeetCode 3309. 连接二进制表示可形成的最大数值(中等) 给你一个长度为 3 的整数数组 nums。 现以某种顺序 连接…...
深入解析光敏传感技术:嵌入式仿真平台如何重塑电子工程教学
一、光敏传感技术的物理本质与系统级实现挑战 光敏电阻作为经典的光电传感器件,其工作原理根植于半导体材料的光电导效应。当入射光子能量超过材料带隙宽度时,价带电子受激发跃迁至导带,形成电子-空穴对,导致材料电导率显著提升。…...
Appium下载安装配置保姆教程(图文详解)
目录 一、Appium软件介绍 1.特点 2.工作原理 3.应用场景 二、环境准备 安装 Node.js 安装 Appium 安装 JDK 安装 Android SDK 安装Python及依赖包 三、安装教程 1.Node.js安装 1.1.下载Node 1.2.安装程序 1.3.配置npm仓储和缓存 1.4. 配置环境 1.5.测试Node.j…...
如何做好一份技术文档?从规划到实践的完整指南
如何做好一份技术文档?从规划到实践的完整指南 🌟 嗨,我是IRpickstars! 🌌 总有一行代码,能点亮万千星辰。 🔍 在技术的宇宙中,我愿做永不停歇的探索者。 ✨ 用代码丈量世界&…...
