首页 > 编程语言 >C++U4-第10课-前缀和与差分

C++U4-第10课-前缀和与差分

时间:2023-12-26 14:35:03浏览次数:38  
标签:pre 10 前缀 int U4 差分 C++ 数组 ans

学习目标

 前缀和解决的问题

 前缀和概念

 前缀和构建方式

 

 前缀和主要解决区间求和问题

练习题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

相关文章

  • Cisco Firepower 4100 Series FTD Software 7.4.1 & ASA Software 9.20.2
    CiscoFirepower4100SeriesFTDSoftware7.4.1&ASASoftware9.20.2FirepowerThreatDefense(FTD)Software请访问原文链接:https://sysin.org/blog/cisco-firepower-4100/,查看最新版。原创作品,转载请保留出处。作者主页:sysin.org为什么选择CiscoSecure防火墙?Cisco......
  • Cisco Firepower 2100 Series FTD Software 7.4.1 & ASA Software 9.20.2
    CiscoFirepower2100SeriesFTDSoftware7.4.1&ASASoftware9.20.2FirepowerThreatDefense(FTD)Software请访问原文链接:https://sysin.org/blog/cisco-firepower-2100/,查看最新版。原创作品,转载请保留出处。作者主页:sysin.org为什么选择CiscoSecure防火墙?Cisco......
  • Cisco Secure Firewall 3100 Series, Firepower Threat Defense (FTD) Software 7.4.1
    CiscoSecureFirewall3100Series,FirepowerThreatDefense(FTD)Software7.4.1&ASASoftware9.20.2FirepowerThreatDefense(FTD)Software请访问原文链接:https://sysin.org/blog/cisco-firepower-2100/,查看最新版。原创作品,转载请保留出处。作者主页:sysin.org为......
  • Cisco Firepower 1000 Series FTD Software 7.4.1 & ASA Software 9.20.2
    CiscoFirepower1000SeriesFTDSoftware7.4.1&ASASoftware9.20.2请访问原文链接:https://sysin.org/blog/cisco-firepower-1000/,查看最新版。原创作品,转载请保留出处。作者主页:sysin.org面向小型办公室的企业级保护在企业发展的过程中为企业保驾护航。Firepower1000......
  • MySQL8.0 OCP 103
    Choosethree.Whichthreerequirementsmustbeenabledforgroupreplication?对于组复制,必须启用哪些三个要求?A)replicationfiltersB)semi-syncreplicationpluginC)slaveupdateslogging更新日志记录D)binarylogchecksumE)primarykeyorprimarykeyequ......
  • Win10遇到服务器启动失败 80端口被占用如何解决
    Win10提示"服务器启动失败,80端口被占用"怎么办?具体解决方法如下步骤如下:1、以管理员身份运行cmd;2、输入:netstophttp注:如果提示是否真的需要停止这些服务,则选择"Y";3、完成后输入:scconfighttpstart=disabled其他方法:(若80端口不能解除占用,可使用下方解决方案)解决方......
  • Qt/C++音视频开发61-多屏渲染/一个解码渲染到多个窗口/画面实时同步
    一、前言多屏渲染就是一个解码线程对应多个渲染界面,通过addrender这种方式添加多个绘制窗体,我们经常可以在展会或者卖电视机的地方可以看到很多电视播放的同一个画面,原理应该类似,一个地方负责打开解码播放,将画面同步传输到多个显示的地方,完全保证了画面的一致性。这样相当于复用......
  • C++基础 -12- 类的析构函数
    ———————标准输入输出——————— ......
  • C++大内存分配错误
    C++无法分配大内存当影像较大时,m和n是int类型时,char*a=newchar[m*n]可能出现无法分配内存的错误原因分析:由于早期数据处理需求对内存需要较小,例如早期影像较小,影像长宽的积较小,char*a=newchar[m*n]不会出错。时代变化,影像体积变大,老代码仍旧使用int类型申请内存,将会出错。......
  • 【选择排序】之C++实现
    描述选择排序(SelectionSort)是一种简单直观的排序算法。它的基本思想是:每一轮从待排序的数据中选择最小(或最大)的一个元素,然后与待排序数据的第一个元素交换位置。对剩余未排序的数据重复这个过程,直到所有数据排序完成。实现思路遍历数组,找到最小元素的下标。将最小元素与当前......