【No.9】蓝桥杯差分与前缀和|树木打药问题|树木维护问题(C++)

2024-03-19 21:04

本文主要是介绍【No.9】蓝桥杯差分与前缀和|树木打药问题|树木维护问题(C++),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

差分与前缀和是一对互逆的操作,常常用于处理区间问题,差分法是解决区间加减问题,前缀和是解决区间求和问题的常用办法。

差分法

差分法的应用主要是用于处理区间问题。当某一个数组要在很多不确定的区间,加上相同的一个数。我们如果每个都进行加法操作的话,那么复杂度 O(nm) 是平方阶的,非常消耗时间。
如果我们采用差分法,将数组拆分,构造出一个新的拆分数组,通过对数组区间的端点进行加减操作,最后将数组和并就能完成原来的操作。
这样处理后,时间复杂度降低为 O(N),虽然感觉操作变得更加复杂了,但是只用对边界操作确实比操作一整个区间的方法要优秀的多。
差分法的特点:

  1. 将对于区间的加减操作转化为对于端点的操作;
  2. 时间复杂度为 O(n);
  3. 用于维护区间的增减但不能维护乘除;
  4. 差分后的序列比原来的数组序列多一个数。
    差分算法解题的基本思路:
  5. 设定 b[1]=a[1]
  6. 对于第 2 项到第 n 项,利用差分式 b[i]=a[i]−a[i−1];
  7. 对于区间端点进行加减操作;
  8. 进行差分还原(即前缀和);
  9. 注意,这里从 1 开始。如果从 0 开始,还需讨论 i=0 的情况。使用 1 的话,b[1]=a[1]−a[0]=a[1]
如果对差分后的b数字其中一个数字+1会怎么样?

恢复后从这一项开始的每一项都上了1。

同样的-1,等于+(-1),如果对差分后的某一项-1,那么恢复后等于对从此项开始的每一项都-1.
形式化的写为:
如果b[l]=b[]+x(任意值) -> a[l,n]+=x
如果b[r]=b[r]-x -> a[r,n]-=x
r>l,则有 a[],a[l+1],a[l+2],..a[r-1],a[r],a[r+1]...a[n]
等效于:a[l,r-1]+=x

即对差分后的数组 b[l]+=x b[r]-=x就能转化为 区间a[l,r-1]+=x

差分法的一般步骤:
假设有一个数组:

a = [1, 2, 3, 4, 5, 7, 2]

差分后:

b = [1, 1, 1, 1, 1, 2, -5]

一般应用场景是对区间 [l,r] 进行 N 次加减操作。例如:

  • 从第二个元素到第五个元素每个加 3
  • 从第二个元素到第四个元素每个减 2
  • 从第一个元素到第三个元素每个加 1
    对于每个 [l,r] 区间的加减操作都可转化为对端点 l 和 r+1 的操作。例如,从第二个元素到第五个元素每个加 3,可转化为 [l] 加 3 且 [r+1] 减 3。
    原序列变成了:
1 1 1 1 1 2 -5
1 4 1 1 1 -1 -5

然后按照 b[i]=b[i]+b[i−1] 复原:

1 5 6 7 8 7 2

去掉最后一项,跟原序列对比:

1 2 3 4 5 7 2
1 5 6 7 8 7 2

确实是都加上了 3。
继续操作:
从第二个元素到第四个元素每个减 2,可转化为 [l] 减 2 且 [r+1] 加 2。
序列变成了:

1 4 1 1 1 -1 -5
1 2 1 1 3 -1 -5

然后按照 b[i]=b[i]+b[i−1] 复原:

1 3 4 5 8 7 2

与上次复原后对比:

1 5 6 7 8 7 2
1 3 4 5 8 7 2

确实是按照操作执行了。
注意,不需要每次都复原,只需在最后一次复原即可。
最后直接做三次,最后还原:

  • 从第二个元素到第五个元素每个加 3
  • 从第二个元素到第四个元素每个减 2
  • 从第一个元素到第三个元素每个加 1
    原序列差分后:
b = [1 1 1 1 1 2 -5]
  • 第 2 个元素加 3
  • 第 6 个元素减 3
  • 第 2 个元素减 2
  • 第 5 个元素加 2
  • 第 1 个元素加 1
  • 第 4 个元素减 1
    差分序列变成:
2 2 1 0 3 -1 -5

复原后:

2 4 5 5 8 7 5

与原序列对比:

1 2 3 4 5 7 2
2 4 5 5 8 7 5

所以,差分算法是非常方便快捷的。
差分与前缀和是逆操作,常在一起出现,但是先做差分还是先做前缀和就是两种不同的算法,做不做另一种操作也决定了算法不同,所以大家要根据题目分析,具体学会使用。

差分算法解决区间加减问题通用框架如下:

//读入原始数据 n,m,a输入n,m
原始数组 a[]
差分数组 b[]for(int i=1;i<=n;i++){输入a[i]
}//差分
for(int i=1;i<=n;i++)b[i]=a[i]-a[i-1]//m次区间操作
while(m--)
{输入l,r,valueb[l]+=valueb[r+1]-=value
}//前缀和还原
for(int i=1;i<n;i++)a[i]=b[i]+a[i-1]
//读入原始数据 n,m,a输入n,m
原始数组 a[]
差分数组 b[]for i (1-n){输入a[i]
}//差分
for i (1-n)b[i]=a[i]-a[i-1]//m次区间操作
while(m--)
{输入l,r,valueb[l]+=valueb[r+1]-=value
}//前缀和还原
for i (1-n)a[i]=b[i]+a[i-1]
//读入原始数据 n,m,a输入n,m
原始数组 a[]
差分数组 b[]for i (1-n){输入a[i]
}//差分
for i (n-2)a[i]=a[i]-a[i-1]//m次区间操作
while(m--)
{输入l,r,valuea[l]+=valuea[r+1]-=value
}//前缀和还原
for i (1-n)a[i]=a[i]+a[i-1]

大学里的树木要打药

题目描述:
教室外有 N 棵树,根据不同的位置和树种,学校要对其上不同的药。
因为树的排列成线性,且非常长,我们可以将它们看作一条直线给他们编号。
树的编号从 0~N-1 且 N<1e6。
对于树的药是成区间分布,比如 3−5 号的树靠近下水道,所以他们要用驱蚊虫的药,20−26 号的树,他们排水不好,容易涝所以要给他们用点促进根系的药。
诸如此类,每种不同的药要花不同的钱。
现在已知共有 M 个这样的区间,并且给你每个区间花的钱,请问最后,这些树木花了多少药费。
输入:
输入描述:
每组输入的第一行有两个整数 N(1<=N<=1000000)和M(1<=M<=100000)。
N 代表马路的共计多少棵树
M代表区间的数目,N 和 M 之间用一个空格隔开。

接下来的 M 行每行包含三个不同的整数,用一个空格隔开,表示一个区域的起始点L 和终止点R 的坐标,以及花费。

输入样例:

500 3
150 300 4
100 200 20
470 471 19

输出描述:
输出包括一行,这一行只包含一个整数,所有的花费。
输出样例:

2662

样例:
输入样例:

3000 8
150 1130 2
1020 1200 3
470 2071 1
1123  211 6
12 222 2
13 23 2
1  213 4
1232  2523 6

输出样例:

2662

运行限制:

1. 最大运行时间:1s
2. 最大运行内存:128M

题目解析:

  1. 利用b[i]=a[i]−a[i−1] 差分式。
    这里由于开始时都是 0,可以用,但是用完都还是 0,所以没有意义,所以直接跳过即可。
  2. 依次读入区间的值,然后将对于区间的操作转化为对于区间端点操作加减。 由于我们从 1 开始,所以数目整体区间要右移 1 位。
    对于每个 [l,r] 区间的加减操作都转化为对端点 l,r+1 的操作。
  3. 差分还原(前缀和)。
for (int i = 1; i < n; i++)b[i] = a[i] - a[i - 1]
答案解析
#include <iostream>
using namespace std;
int b[100005];
int main()
{int n; //n层int m; // m个区间cin >> n >> m;while (m--){//因为l,r是从0开始的,差分要求从1开始,整体右移int l, r, value;cin >> l >> r >> value;l = l + 1;r = r + 1;b[l] += value;b[r+1] -= value;}for (int i = 1; i <= n; i++)b[i] = b[i] + b[i - 1];//统计结果long long sum = 0;for (int i = 1; i <= n; i++)sum += b[i];/*也可以一次性搞定int sum=b[1];for(int i=1; i<=n; i++){b[i]=b[i]+b[i-1];sum+=b[i]}*/cout << sum << endl;
}

前缀和

前缀和法的应用主要也是用于处理区间问题。
前缀和是指某序列的前 n 项和,可以把它理解为数学上的数列的前 n 项和。当对于某一数组区间进行多次询问,[L,r] 的和时,如果正常处理,那么我们每次都要 [l,r]。查询 N 次,那么时间复杂度也是 O(nm) 也是平方阶的。
如果我们采用前缀和,构造出一个前缀和数组,通过对于端点的值的减法操作就能 O(1) 的求出 [l,r] 的和。然后 N 次查询的,就将复杂度降低为 O(n)。
同差分一样,感觉操作变得更加复杂了,但是只用对端点值的操作确实比一整个区间相加的方法要优秀的多。听到这里大家很期待了,我们接着进行讲解。
前缀和的特点:

  1. 将对于区间的求和操作转化为对于端点值的减法的操作;
  2. 区间求和操作的时间复杂度为 O(1);
  3. 数组存放时要从 1 开始;
  4. 前缀和数组比原来的数组序列多一个数,第 0个元素为 0。
    前缀和算法解题的基本思路:
  5. 利用 sum[i]=a[i]+sum[i−1] 差分式;
  6. 从第 1 项到 n 项,且第 0 项无数据默认为 0;
  7. 对于区间求和的操作转化为端点值相减。
设l<r:
Sum[l]=a[1]+a[2]..+a[l]
Sum[r]=a[1]+a[2]..+a[l]+a[l+1]+..a[r]Sum[r]-Sum[l]=a[l+1]+..a[r]
所以前缀和sum[r]-sum[l] 可以转换为 l+1,r区间内a[i]的和

前缀和:

首先假设有一个数组:1 2 3 4 5 7 2前缀和后:0 1 3 6 10 15 22 24一般应用场景:让你对区间 [l,r] 求和操作N次如:从第二个元素到第五个元素的和
从第二个元素到第四个元素的和
从第一个元素到第三个元素的和
....这里我们先演示前三个:对于每个 [l,r] 区间的求和操作转化为区间端点的加减操作sum[l,r] =[r]-[l-1]从第二个元素到第五个元素的和:转化为:[5]-[1]那么Sum[2,5]=[5]-[1]=14且 2+3+4+5=14确实是相等的,就是这么神奇。我们继续操作:从第二个元素到第四个元素的和转化为:[4]-[1]那么Sum[2,4]=[4]-[1]=9且 2+3+4=9我们继续操作:从第一个元素到第三个元素的和转化为:[3]-[0]那么Sum[1,3]=[3]-[0]=6且 1+2+3=6符合题意,验证结束,咱么做个题目看一看

前缀和一般解题过程:

输 入 N 和 M输入 N 个值 并计算前缀和
for( int i=1;i<=N;i++)输入a[i]并计算sum[i]=sum[i-1]+a[i]输入 M 个区间,计算结果while(M)M-=1输入 L , R计算 [r]-[l-1],并输出

大学里的树木要维护

题目描述:
教室外有 N 棵树,根据不同的位置和树种,学校已经对其进行了多年的维护。因为树的排列成线性,且非常长,我们可以将它们看作一条直线给他们编号。
树的编号从 1−N 且 N<1e6。由于已经维护了多年,每一个树都由学校的园艺人员进行了维护费用的统计。
每棵树的前期维护费用各不相同,但是由于未来需要要打药,所以有些树木的维护费用太高的话,就要重新种植。由于维护费用也称区间分布,所以常常需要统一个区间里的树木的维护开销。
现在园艺人员想知道,某个区间内的树木维护开销是多少。共计 M 个区间需要查询。
输入描述:
每组输入的第一行有两个整数 N(1<=N<=1000000)和 M(1<=M<=100000)。
N 代表马路的共计多少棵树,M 代表区间的数目,N 和 M 之间用一个空格隔开。接下来的一行,包含 N 个数,每个数之间用空格隔开。
接下来的M行每行包含两个不同的整数,用一个空格隔开,表示一个区域的起始点L和终止点R的坐标。
输入样例:

10 3
7 5 6 4 2 5 0 8 5 3
1 5
2 6
3 7

输出描述:
输出包括 M 行,每一行只包含一个整数,所有的花费。
输出样例:

24
22
17

样例:
输入样例

30 28 
172 723 580 822 718 798 941 625 450 716 540 252 16 666 115 679 274 323 875 233 99 538 881 486 610 462 319 878 930 735 
6 22 
7 21 
3 16 
7 20 
9 17 
0 21 
13 27 
7 19 
10 23 
2 14 
21 22 
15 17 
6 13 
16 23 
21 21 
11 15 
5 12 
9 11 
8 22 
10 16 
3 8 
15 27 
5 16
4 8 
0 27 
4 8 
7 21 
20 21

输出样例

8140 
6804 
7918 
6705 
3708 
10617 
6576 
6472 
6207 
7847 
637 
1068 
4338 
3902 
99 
1589 
5040 
1706 
6401 
2984 
4484 
5894 
6516 
3904 
13913 
3904 
6804 
332

运行限制:

1. 最大运行时间:1s
2. 最大运行内存:128M

题目解析:

  1. 利用sum[i]=a[i]+sum[i−1] 前缀和式在输入时求出前缀和;
  2. 依次读入区间的值,然后将对于区间的求和操作转化为对于区间端点操作加减,对于每个 [l,r] 区间的求和操作都转化为对端点[r]-[l-1]的操作。
  3. 输出答案。
答案解析
#include <iostream>
using namespace std;
int a[100005];
int sum[100005];int main()
{int n;int m;cin >> n >> m;for (int i = 1; i <= n; i++){cin >> a[i];sum[i] = a[i] + sum[i - 1];}while (m > 0){m -= 1;int l, r;cin >> l >> r;cout << sum[r] - sum[l - 1] << endl;}
}

这个代码有个问题,虽然是能通过的,但是他是一个输入对应一个输出的,我们之前讲过,这对大部分的测评机是没问题。
终端输出:

10 3
7 5 6 4 2 5 0 8 5 3
1 5
24
2 6
22
3 7
17Process returned 0 (0x0)   execution time : 1.741 s
Press any key to continue.

但是如果有想要规规矩矩的处理,或者说题目要求必须全部读入后输出。我们可这样操作。

#include<bits/stdc++.h>
using namespace std;
int a[100005];
int sum[100005];
vector<int>ss;
int main()
{int n ;int m;cin>>n>>m;for(int i=1;i<=n;i++){cin>>a[i];sum[i]=a[i]+sum[i-1];}while(m>0){m-=1;int l,r;cin>>l>>r;ss.push_back(sum[r]-sum[l-1]);}for(auto sss:ss) cout<<sss<<endl;
}

终端输出:

10 3
7 5 6 4 2 5 0 8 5 3
1 5
2 6
3 7
24
22
17Process returned 0 (0x0)   execution time : 6.235 s
Press any key to continue.

都可以,大家看自己需求和心情选择即可。

这篇关于【No.9】蓝桥杯差分与前缀和|树木打药问题|树木维护问题(C++)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

好题——hdu2522(小数问题:求1/n的第一个循环节)

好喜欢这题,第一次做小数问题,一开始真心没思路,然后参考了网上的一些资料。 知识点***********************************无限不循环小数即无理数,不能写作两整数之比*****************************(一开始没想到,小学没学好) 此题1/n肯定是一个有限循环小数,了解这些后就能做此题了。 按照除法的机制,用一个函数表示出来就可以了,代码如下

hdu1043(八数码问题,广搜 + hash(实现状态压缩) )

利用康拓展开将一个排列映射成一个自然数,然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu

【C++ Primer Plus习题】13.4

大家好,这里是国中之林! ❥前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,忍不住分享一下给大家。点击跳转到网站。有兴趣的可以点点进去看看← 问题: 解答: main.cpp #include <iostream>#include "port.h"int main() {Port p1;Port p2("Abc", "Bcc", 30);std::cout <<

C++包装器

包装器 在 C++ 中,“包装器”通常指的是一种设计模式或编程技巧,用于封装其他代码或对象,使其更易于使用、管理或扩展。包装器的概念在编程中非常普遍,可以用于函数、类、库等多个方面。下面是几个常见的 “包装器” 类型: 1. 函数包装器 函数包装器用于封装一个或多个函数,使其接口更统一或更便于调用。例如,std::function 是一个通用的函数包装器,它可以存储任意可调用对象(函数、函数

C++11第三弹:lambda表达式 | 新的类功能 | 模板的可变参数

🌈个人主页: 南桥几晴秋 🌈C++专栏: 南桥谈C++ 🌈C语言专栏: C语言学习系列 🌈Linux学习专栏: 南桥谈Linux 🌈数据结构学习专栏: 数据结构杂谈 🌈数据库学习专栏: 南桥谈MySQL 🌈Qt学习专栏: 南桥谈Qt 🌈菜鸡代码练习: 练习随想记录 🌈git学习: 南桥谈Git 🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈�

【C++】_list常用方法解析及模拟实现

相信自己的力量,只要对自己始终保持信心,尽自己最大努力去完成任何事,就算事情最终结果是失败了,努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一:什么是list? •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二:list常用接口 •🌰1.默认成员函数 🔥构造函数(⭐) 🔥析构函数 •🌰2.list对象

06 C++Lambda表达式

lambda表达式的定义 没有显式模版形参的lambda表达式 [捕获] 前属性 (形参列表) 说明符 异常 后属性 尾随类型 约束 {函数体} 有显式模版形参的lambda表达式 [捕获] <模版形参> 模版约束 前属性 (形参列表) 说明符 异常 后属性 尾随类型 约束 {函数体} 含义 捕获:包含零个或者多个捕获符的逗号分隔列表 模板形参:用于泛型lambda提供个模板形参的名

购买磨轮平衡机时应该注意什么问题和技巧

在购买磨轮平衡机时,您应该注意以下几个关键点: 平衡精度 平衡精度是衡量平衡机性能的核心指标,直接影响到不平衡量的检测与校准的准确性,从而决定磨轮的振动和噪声水平。高精度的平衡机能显著减少振动和噪声,提高磨削加工的精度。 转速范围 宽广的转速范围意味着平衡机能够处理更多种类的磨轮,适应不同的工作条件和规格要求。 振动监测能力 振动监测能力是评估平衡机性能的重要因素。通过传感器实时监

缓存雪崩问题

缓存雪崩是缓存中大量key失效后当高并发到来时导致大量请求到数据库,瞬间耗尽数据库资源,导致数据库无法使用。 解决方案: 1、使用锁进行控制 2、对同一类型信息的key设置不同的过期时间 3、缓存预热 1. 什么是缓存雪崩 缓存雪崩是指在短时间内,大量缓存数据同时失效,导致所有请求直接涌向数据库,瞬间增加数据库的负载压力,可能导致数据库性能下降甚至崩溃。这种情况往往发生在缓存中大量 k

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