学习目标
前缀和解决的问题
前缀和概念
前缀和构建方式
前缀和主要解决区间求和问题
练习题1:[前缀和]
【算法分析】 前缀和数组 s 的含义是 s[i] 表示 a[1] ~ a[i] 的和 ,那么 ∑ i=l i=r a[i] = s[r]−s[l−1]。 【参考代码】 #include <iostream> using namespace std; int a[100010], s[100010]; int main() { int n, m; cin >> n >> m; for(int i = 1; i <= n; i++){ cin >> a[i]; s[i] = s[i - 1] + a[i]; } int l, r; while(m--){ cin >> l >> r; cout << s[r] - s[l - 1] << endl; } return 0; }View Code
练习题2:[7的倍数的子序列]
/* 流程解析: 输入数组的长度n。 循环读入n个数组元素,存储在数组a中。 根据题目要求,计算前缀和并对7取模,保存在pre数组中。 初始化左边界l为-1,右边界r为0。 遍历pre数组,更新左边界l和右边界r,确保每个模值pre[i]的最小左边界和最大右边界被记录下来。 遍历0到6之间的所有模值,计算相应模值的子数组长度,保存在ans中。 输出ans作为结果。 这段代码的目标是找到一个子数组,使得该子数组中所有元素相加后对7取模的结果最大。最后输出最大结果ans。 提示1:对结果取余 和对过程取余 是一样的 累加和整体取余:4+5+6+7+8=30 30%4 余2 逐个取余再加在一起再取余:逐个取余 0 1 2 3 0 6%4 = 2 */
#include <iostream> using namespace std; int a[50010], pre[50010]; int r[7]; //记录最后出现的位置 int l[7] = {0, -1 ,-1,-1 ,-1,-1,-1}; // 初始化,记录每个余数最早出现的位置 int main() { int n, ans; // 输入变量和答案变量 cin >> n; // 输入数组长度 for(int i = 1; i <= n; i++){ cin >> a[i]; // 输入数组元素 pre[i] = (pre[i - 1] + a[i]) % 7; // 计算前缀和%7的结果 if(l[pre[i]] == -1) l[pre[i]] = i; // 更新左边界 r[pre[i]] = i; // 更新右边界 } for(int i = 0; i <= 6; i++){ ans = max(ans, r[i] - l[i]); // 计算最长子数组的长度 } cout << ans; // 输出结果 return 0; }
差分数组
差分数组解决的问题
差分构建方式
差分数组解决的使用方式
范围内的数字进行改变的方式
练习题
【算法分析】 差分的定义: 差分指的是在序列中相邻两项之间的差值。 对于一个序列 (a1,a2,a3,⋯),它的差分序列是一个新的数列 (d1,d2,d3,⋯),其中 di=a i+1−ai。也就是说,差分序列中的每一项都是原序列中相邻两项之差。 在进行操作时,[l,r] 之间的数都加上 c,可以在对应的差分序列中做以下操作: b[l] += c; b[r+1] -= c; 操作完成,对差分数组求前缀和即可得到结果。 【参考代码】 #include <iostream> using namespace std; const int N = 100010; int a[N], b[N]; int main(){ int n, m; cin >> n >> m; for(int i = 1; i <= n; i++){ cin >> a[i]; } for(int i = 1; i <= n; i++){ //差分数组 b[i] = a[i] - a[i - 1]; } while(m--){ //m次操作 int l, r, c; cin >> l >> r >> c; b[l] += c; b[r + 1] -= c; } for(int i = 1; i <= n; i++){ //前缀和 b[i] += b[i - 1]; cout << b[i] << " "; } return 0; }View Code
练习2
【算法分析】 这道题只要计算 a[i] 和 a[i+1] 两组的高度差即可: a[i]<a[i+1],即左边的一组比右边的矮,当高度满足左边时,右边的还差一些,那么 ans 加上两堆的高度差; a[i]>=a[i+1],即左边的一组比右边的高,当高度满足左边时,右边的也一定满足了,所以不需要增加 ans。 【参考代码】 #include <iostream> using namespace std; const int N = 100010; int a[N], b[N]; long long ans; int main(){ int n; cin >> n; for(int i = 1; i <= n; i++){ cin >> a[i]; } for(int i = 1; i <= n; i++){ b[i] = a[i] - a[i - 1]; if(b[i] > 0) ans += b[i]; } cout << ans; return 0; }View Code
本节课作业讲解:
链接:https://pan.baidu.com/s/1CRedzyqQEEvF39S2bZHFCA?pwd=n5dl
提取码:n5dl
标签:pre,10,前缀,int,U4,差分,C++,数组,ans From: https://www.cnblogs.com/jayxuan/p/17928058.html