797. 差分(acwing)

2024-03-08 06:52
文章标签 acwing 差分 797

本文主要是介绍797. 差分(acwing),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文章目录

  • 797. 差分
    • 题目描述
    • 差分

797. 差分

题目描述

输入一个长度为 n nn 的整数序列。

接下来输入 m mm 个操作,每个操作包含三个整数 l,r,c, 表示将序列中 [l,r] 之间的每个数加上 c 。

请你输出进行完所有操作后的序列。

输入格式
第一行包含两个整数 n 和 m 。

第二行包含 n 个整数,表示整数序列。

接下来 m 行,每行包含三个整数 l,r,c,表示一个操作。

输出格式
共一行,包含 n 个整数,表示最终序列。

数据范围
1≤n,m≤100000,
1≤l≤r≤n,
-1000≤c≤1000,
-1000≤整数序列中元素的值≤1000

输入样例:

6 3
1 2 2 1 2 1
1 3 1
3 5 1
1 6 1

输出样例:

3 4 5 3 4 2

差分

#include<bits/stdc++.h> // 包含大部分标准库
using namespace std;const int z = 100010; // 设置数组的最大长度,因为数据范围是1≤n,m≤100000
int a[z], b[z]; // a是原始的序列,b是差分数组int main()
{int n, m; // n是序列的长度,m是操作的次数scanf("%d %d", &n, &m); // 读入n, mfor(int i = 1; i <= n; i++){scanf("%d", &a[i]); // 读入序列b[i] = a[i] - a[i - 1]; // 计算差分数组,差分数组的前缀和是原序列}while(m--){int l, r, c; // 操作的区间和要加上的值scanf("%d %d %d", &l, &r, &c); // 读入操作//因为在差分数组中,标记位加了一个数,还原成原数组的时候,后面的数都会累加,然后再r+1位 再减去这个数停止累加 b[l] += c; // 在左端点加上cb[r + 1] -= c; // 在右端点的下一个位置减去c}for(int i = 1; i <= n; i++){a[i] = a[i - 1] + b[i]; // 求差分数组的前缀和,即还原原始序列printf("%d ", a[i]); // 输出最终序列}return 0;
}

这段代码的核心思想是差分数组。差分数组是一种特殊的数组,它记录了原始序列每个数与前一个数之差的变化。通过对差分数组进行一系列操作,可以快速更新原始序列中的数。

在代码中,首先读入原始序列,并计算出差分数组。差分数组的计算是通过当前元素等于原始序列中当前元素减去前一个元素得到的。

接下来,根据输入的操作,对差分数组进行更新。每个操作表示一个区间 [l, r],将区间内的每个数都加上给定的值c。这是通过将区间的左端点加上c,右端点的下一个位置减去c来实现的。

最后,通过差分数组和原始序列的关系,计算出最终的序列,并输出每个数。最终序列的计算是通过原始序列中每个数等于前一个数加上差分数组中对应位置的数得到的。

这篇关于797. 差分(acwing)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/786361

相关文章

poj 3159 (spfa差分约束最短路) poj 1201

poj 3159: 题意: 每次给出b比a多不多于c个糖果,求n最多比1多多少个糖果。 解析: 差分约束。 这个博客讲差分约束讲的比较好: http://www.cnblogs.com/void/archive/2011/08/26/2153928.html 套个spfa。 代码: #include <iostream>#include <cstdio>#i

poj 3169 spfa 差分约束

题意: 给n只牛,这些牛有些关系。 ml个关系:fr 与 to 牛间的距离要小于等于 cost。 md个关系:fr 与 to 牛间的距离要大于等于 cost。 隐含关系: d[ i ] <= d[ i + 1 ] 解析: 用以上关系建图,求1-n间最短路即可。 新学了一种建图的方法。。。。。。 代码: #include <iostream>#include

POJ 1364差分约束

给出n个变量,m个约束公式 Sa + Sa+1 + .... + Sa+b < ki or > ki ,叫你判断是否存在着解满足这m组约束公式。 Sa + Sa+1   +   .+ Sa+b =  Sum[a+b] - Sum[a-1]  . 注意加入源点n+1 。 public class Main {public static void main(Strin

【AcWing】851. 求最短路

spfa算法其实是对贝尔曼福特算法做一个优化。 贝尔曼福特算法会遍历所有边来更新,但是每一次迭代的话我不一定每条边都会更新,SPFA是对这个做优化。 如果说dist[b]在当前这次迭代想变小的话,那么一定是dist[a]变小了,只有a变小了,a的后继(b)才会变小。 用宽搜来做优化,用一个队列,队列里边存的就是所有变小了的结点(队列里存的是待更新的点)。 基本思路就是我更新过谁,我再拿

Python中差分进化differential_evolution的调用及参数说明

在场景应用中,要求我们的函数计算结果尽可能的逼近实际测量结果,可转化计算结果与测量结果的残差,通过最小化残差,便可求出最优的结果。但使用最小二乘等方法来计算时,常常会使迭代的结果显然局部最优点而导致结算错误。 差分进化原理 差分进化(Differential Evolution,DE)是一种基于群体差异的进化算法,其计算思想主要包括以下几个方面: 一、初始化种群 首先,随机生成一个初始种群

【AcWing】852. spfa判断负环

#include<iostream>#include<algorithm>#include<cstring>#include<queue>using namespace std;const int N= 1e5+10;int n,m;int h[N],w[N],e[N],ne[N],idx;int dist[N],cnt[N];//cnt存最短路径的边数bool st[N];v

力扣 797. 所有可能路径【DFS】

1. 题目 2. 代码 DFS , 直接见代码 class Solution {public:vector<int> path;vector<vector<int>> res; // 结果集void dfs(vector<vector<int>>& graph, int cur, int n){// 找出所有从节点 0 到节点 n-1 的路径// 下标从 0 开始的if (

RS485差分信号不对称

在RS485总线通信中,差分信号不对称的问题时常出现,尤其是在总线未接从机设备的情况下。这一问题不仅影响通信质量,还可能导致信号传输错误。通过对实际波形、芯片手册及电路的深入分析,可以找出引发差分信号不对称的根本原因,并采取相应的解决措施。 问题描述 在RS485通信测试中,当总线上没有从机设备连接时,观察到RS485差分信号(A、B)关于地(GND)不对称。理想情况下,RS485的差分信

【POJ】3169 Layout 【HDU】3592 World Exhibition 差分约束

传送门:  【POJ】3169 Layout、【HDU】3592 World Exhibition 题目分析:我会说我只是凭直觉写的吗。。。。。。。 如果有B-A>=C形式的,则建边(B,A,-C)。 如果有B-A<=C形式的,则建边(A,B,C)。 对所有的点X,建边(X,X-1,0)。 最后跑一遍最短路。如果存在负环输出-1,如果点N不可达输出-2,否则输出点N的值(最短路径长

Xilinx FPGA 原语解析(二):IBUFDS差分输入缓冲器(示例源码及仿真)

目录 前言: 一、原语使用说明 二、原语实例化代码模版 三、使用示例 1.设计文件代码 2.仿真文件代码 3.仿真结果 前言: 本文主要参考资料xilinx手册,《Xilinx 7 Series FPGA and Zynq-7000 All Programmable SoC Libraries Guide for HDL Designs》UG768 (v14.7) Octob