算法竞赛之差分进阶——等差数列差分 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 文件通过层级…...
conda相比python好处
Conda 作为 Python 的环境和包管理工具,相比原生 Python 生态(如 pip 虚拟环境)有许多独特优势,尤其在多项目管理、依赖处理和跨平台兼容性等方面表现更优。以下是 Conda 的核心好处: 一、一站式环境管理:…...
【根据当天日期输出明天的日期(需对闰年做判定)。】2022-5-15
缘由根据当天日期输出明天的日期(需对闰年做判定)。日期类型结构体如下: struct data{ int year; int month; int day;};-编程语言-CSDN问答 struct mdata{ int year; int month; int day; }mdata; int 天数(int year, int month) {switch (month){case 1: case 3:…...
突破不可导策略的训练难题:零阶优化与强化学习的深度嵌合
强化学习(Reinforcement Learning, RL)是工业领域智能控制的重要方法。它的基本原理是将最优控制问题建模为马尔可夫决策过程,然后使用强化学习的Actor-Critic机制(中文译作“知行互动”机制),逐步迭代求解…...
从WWDC看苹果产品发展的规律
WWDC 是苹果公司一年一度面向全球开发者的盛会,其主题演讲展现了苹果在产品设计、技术路线、用户体验和生态系统构建上的核心理念与演进脉络。我们借助 ChatGPT Deep Research 工具,对过去十年 WWDC 主题演讲内容进行了系统化分析,形成了这份…...
从零实现富文本编辑器#5-编辑器选区模型的状态结构表达
先前我们总结了浏览器选区模型的交互策略,并且实现了基本的选区操作,还调研了自绘选区的实现。那么相对的,我们还需要设计编辑器的选区表达,也可以称为模型选区。编辑器中应用变更时的操作范围,就是以模型选区为基准来…...
在HarmonyOS ArkTS ArkUI-X 5.0及以上版本中,手势开发全攻略:
在 HarmonyOS 应用开发中,手势交互是连接用户与设备的核心纽带。ArkTS 框架提供了丰富的手势处理能力,既支持点击、长按、拖拽等基础单一手势的精细控制,也能通过多种绑定策略解决父子组件的手势竞争问题。本文将结合官方开发文档,…...
Vue3 + Element Plus + TypeScript中el-transfer穿梭框组件使用详解及示例
使用详解 Element Plus 的 el-transfer 组件是一个强大的穿梭框组件,常用于在两个集合之间进行数据转移,如权限分配、数据选择等场景。下面我将详细介绍其用法并提供一个完整示例。 核心特性与用法 基本属性 v-model:绑定右侧列表的值&…...
关于iview组件中使用 table , 绑定序号分页后序号从1开始的解决方案
问题描述:iview使用table 中type: "index",分页之后 ,索引还是从1开始,试过绑定后台返回数据的id, 这种方法可行,就是后台返回数据的每个页面id都不完全是按照从1开始的升序,因此百度了下,找到了…...
大语言模型如何处理长文本?常用文本分割技术详解
为什么需要文本分割? 引言:为什么需要文本分割?一、基础文本分割方法1. 按段落分割(Paragraph Splitting)2. 按句子分割(Sentence Splitting)二、高级文本分割策略3. 重叠分割(Sliding Window)4. 递归分割(Recursive Splitting)三、生产级工具推荐5. 使用LangChain的…...
Nuxt.js 中的路由配置详解
Nuxt.js 通过其内置的路由系统简化了应用的路由配置,使得开发者可以轻松地管理页面导航和 URL 结构。路由配置主要涉及页面组件的组织、动态路由的设置以及路由元信息的配置。 自动路由生成 Nuxt.js 会根据 pages 目录下的文件结构自动生成路由配置。每个文件都会对…...
