本系列文章我将总结我在刷算法题所用到的知识如果你也在刷算法并且是新手我相信这系列文章会很适合你。【洛谷刷题 | 第四天】今日题目1.最大子段和前缀和贪心知识点前缀和贪心2.领地选择前缀和3.语文成绩差分知识点差分今日题目1.最大子段和前缀和贪心链接P1115 最大子段和给出一个长度为 n 的序列 a选出其中连续且非空的一段使得这段和最大。案例输入 输出742-43-12-43通过前缀和将 “连续子数组和” 转化为差值问题后核心是贪心策略对每个位置尽可能用最小的前缀和去减当前前缀和以得到最大的差值即最大子数组和避免了暴力枚举所有子数组的高复杂度。题解:#includebits/stdc.husingnamespacestd;inta[200009]{0},b[2000009]{0},c[2000009]{0};intmain(){intn;cinn;for(inti0;in;i){cina[i];}b[0]a[0];for(inti1;in;i){b[i]a[i]b[i-1];}intminnmin(0,b[0]);c[0]b[0];for(inti1;in;i){c[i]b[i]-minn;minnmin(b[i],minn);}intmaxx-1e5;for(inti0;in;i){maxxmax(c[i],maxx);}coutmaxx;}知识点前缀和贪心前缀和就是从数组开头到当前位置的所有元素的累加和。假设有数组 a[a₀,a₁,a₂,...,aₙ₋₁]定义前缀和数组 b其中 b[0]a[0]第一个元素的前缀和就是它自己 b[1]a[0]a[1]前2个元素的和 b[2]a[0]a[1]a[2]前3个元素的和...b[i]a[0]a[1]...a[i]前 i1个元素的和前缀和的核心价值快速计算任意连续子数组的和。比如想算数组中从第 j 个元素到第 i 个元素的和j ≤ i 不用重新遍历 j 到 i 累加 直接用公式a[j]a[j1]...a[i]b[i]-b[j-1] 特殊情况如果 j0从第一个元素开始则和为 b[i]因为 b[-1]视为0。贪心就是每一步都做出当前看起来最优的选择不考虑全局后果最终希望通过每一步的局部最优得到全局最优的结果。2.领地选择前缀和链接P2004 领地选择给定一个 N行M列 的二维地图每个位置有对应的土地价值可正可负需要在地图上找到一个 C×C 的正方形区域使得该区域内所有地块的价值总和最大。最终输出这个正方形区域左上角的坐标 (X,Y)题目保证最优解唯一。案例输入 输出342121231-19022011这道题是一维前缀和的提升版 - 二维前缀和。先计算每行的一维前缀和再基于行前缀和累加得到二维前缀和d [i][j] 表示从地图左上角 (1,1) 到 (i,j) 的矩形区域总价值再遍历所有能放下 C×C 正方形的左上角坐标 (i,j)通过二维前缀和公式计算该正方形的总价值最后对比所有合法正方形的总价值记录最大值对应的左上角坐标最终输出该坐标。题解#includebits/stdc.husingnamespacestd;inta[1001][1001],b[1001][1001],d[1001][1001];intmain(){intn,m,c;cinnmc;for(inti1;in;i){for(intj1;jm;j){cina[i][j];b[i][j]a[i][j]b[i][j-1];d[i][j]b[i][j]d[i-1][j];}}intmaxxINT_MIN;;intx1,y1;for(inti1;in;i){for(intj1;jm;j){if((ic-1)n||(jc-1)m)continue;intqd[ic-1][jc-1]d[i-1][j-1]-d[i-1][jc-1]-d[ic-1][j-1];if(maxxq){maxxq;xi,yj;}}}coutx y;}3.语文成绩差分链接P2367 语文成绩给定 n 个学生的初始成绩执行 p 次加分操作每次给第 x 到第 y 个学生每人加 z 分最终输出全班的最低成绩。案例输入 输出322111121231这道题我们可以利用差分数组 d 替代直接遍历区间加分降低复杂度对每次 x 到 y 加 z 的操作仅需在 d[x] 加 z、d[y1] 减 z之后对差分数组 d 做前缀和计算得到每个学生实际需要增加的分数最后将每个学生的初始成绩 a[i] 加上对应加分 d[i]遍历过程中实时记录所有成绩的最小值最终输出该最小值。题解#includebits/stdc.husingnamespacestd;inta[5000009];intd[5000009];intminnINT_MAX;intmain(){intn,p;cinnp;for(inti1;in;i){cina[i];}intx,y,z;for(inti0;ip;i){cinxyz;d[x]z;d[y1]-z;}for(inti1;in;i){d[i]d[i-1];}for(inti1;in;i){a[i]d[i];if(minna[i]){minna[i];}}coutminn;}知识点差分差分是一种预处理数组的技巧核心是用一个 “差分数组” 记录原数组中相邻元素的差值目的是把 “区间批量修改” 转化为 “单点修改”降低操作复杂度。例如原数组 a[a₁,a₂,a₃,...,aₙ]定义差分数组 d d₁a₁第一个元素和原数组一致 dᵢaᵢ-aᵢ₋₁i≥2即当前元素减前一个元素的差值差分的核心价值快速处理数组的区间加减操作。比如想给原数组中从 x 到 y 的所有元素都加 z不用遍历 x 到 y 逐个加 只需对差分数组做 2 次单点修改d[x] z、d[y1] - z最后对差分数组做前缀和就能还原出修改后的原数组。举一个例子假设原成绩a[10,20,30,40]现在要给第2到3个学生各加5分 差分数组初始d[0,0,0,0,0]多开一位避免越界 区间加分d[2]5d[4]-5对 d 做前缀和 d[1]0d[2]055d[3]505d[4]5(-5)0最终成绩10010、20525、30535、40040最后如果我的内容对你有帮助请点赞评论收藏。创作不易大家的支持就是我坚持下去的动力
【洛谷刷题 | 第四天】
发布时间：2026/5/18 0:49:33
本系列文章我将总结我在刷算法题所用到的知识如果你也在刷算法并且是新手我相信这系列文章会很适合你。【洛谷刷题 | 第四天】今日题目1.最大子段和前缀和贪心知识点前缀和贪心2.领地选择前缀和3.语文成绩差分知识点差分今日题目1.最大子段和前缀和贪心链接P1115 最大子段和给出一个长度为 n 的序列 a选出其中连续且非空的一段使得这段和最大。案例输入 输出742-43-12-43通过前缀和将 “连续子数组和” 转化为差值问题后核心是贪心策略对每个位置尽可能用最小的前缀和去减当前前缀和以得到最大的差值即最大子数组和避免了暴力枚举所有子数组的高复杂度。题解:#includebits/stdc.husingnamespacestd;inta[200009]{0},b[2000009]{0},c[2000009]{0};intmain(){intn;cinn;for(inti0;in;i){cina[i];}b[0]a[0];for(inti1;in;i){b[i]a[i]b[i-1];}intminnmin(0,b[0]);c[0]b[0];for(inti1;in;i){c[i]b[i]-minn;minnmin(b[i],minn);}intmaxx-1e5;for(inti0;in;i){maxxmax(c[i],maxx);}coutmaxx;}知识点前缀和贪心前缀和就是从数组开头到当前位置的所有元素的累加和。假设有数组 a[a₀,a₁,a₂,...,aₙ₋₁]定义前缀和数组 b其中 b[0]a[0]第一个元素的前缀和就是它自己 b[1]a[0]a[1]前2个元素的和 b[2]a[0]a[1]a[2]前3个元素的和...b[i]a[0]a[1]...a[i]前 i1个元素的和前缀和的核心价值快速计算任意连续子数组的和。比如想算数组中从第 j 个元素到第 i 个元素的和j ≤ i 不用重新遍历 j 到 i 累加 直接用公式a[j]a[j1]...a[i]b[i]-b[j-1] 特殊情况如果 j0从第一个元素开始则和为 b[i]因为 b[-1]视为0。贪心就是每一步都做出当前看起来最优的选择不考虑全局后果最终希望通过每一步的局部最优得到全局最优的结果。2.领地选择前缀和链接P2004 领地选择给定一个 N行M列 的二维地图每个位置有对应的土地价值可正可负需要在地图上找到一个 C×C 的正方形区域使得该区域内所有地块的价值总和最大。最终输出这个正方形区域左上角的坐标 (X,Y)题目保证最优解唯一。案例输入 输出342121231-19022011这道题是一维前缀和的提升版 - 二维前缀和。先计算每行的一维前缀和再基于行前缀和累加得到二维前缀和d [i][j] 表示从地图左上角 (1,1) 到 (i,j) 的矩形区域总价值再遍历所有能放下 C×C 正方形的左上角坐标 (i,j)通过二维前缀和公式计算该正方形的总价值最后对比所有合法正方形的总价值记录最大值对应的左上角坐标最终输出该坐标。题解#includebits/stdc.husingnamespacestd;inta[1001][1001],b[1001][1001],d[1001][1001];intmain(){intn,m,c;cinnmc;for(inti1;in;i){for(intj1;jm;j){cina[i][j];b[i][j]a[i][j]b[i][j-1];d[i][j]b[i][j]d[i-1][j];}}intmaxxINT_MIN;;intx1,y1;for(inti1;in;i){for(intj1;jm;j){if((ic-1)n||(jc-1)m)continue;intqd[ic-1][jc-1]d[i-1][j-1]-d[i-1][jc-1]-d[ic-1][j-1];if(maxxq){maxxq;xi,yj;}}}coutx y;}3.语文成绩差分链接P2367 语文成绩给定 n 个学生的初始成绩执行 p 次加分操作每次给第 x 到第 y 个学生每人加 z 分最终输出全班的最低成绩。案例输入 输出322111121231这道题我们可以利用差分数组 d 替代直接遍历区间加分降低复杂度对每次 x 到 y 加 z 的操作仅需在 d[x] 加 z、d[y1] 减 z之后对差分数组 d 做前缀和计算得到每个学生实际需要增加的分数最后将每个学生的初始成绩 a[i] 加上对应加分 d[i]遍历过程中实时记录所有成绩的最小值最终输出该最小值。题解#includebits/stdc.husingnamespacestd;inta[5000009];intd[5000009];intminnINT_MAX;intmain(){intn,p;cinnp;for(inti1;in;i){cina[i];}intx,y,z;for(inti0;ip;i){cinxyz;d[x]z;d[y1]-z;}for(inti1;in;i){d[i]d[i-1];}for(inti1;in;i){a[i]d[i];if(minna[i]){minna[i];}}coutminn;}知识点差分差分是一种预处理数组的技巧核心是用一个 “差分数组” 记录原数组中相邻元素的差值目的是把 “区间批量修改” 转化为 “单点修改”降低操作复杂度。例如原数组 a[a₁,a₂,a₃,...,aₙ]定义差分数组 d d₁a₁第一个元素和原数组一致 dᵢaᵢ-aᵢ₋₁i≥2即当前元素减前一个元素的差值差分的核心价值快速处理数组的区间加减操作。比如想给原数组中从 x 到 y 的所有元素都加 z不用遍历 x 到 y 逐个加 只需对差分数组做 2 次单点修改d[x] z、d[y1] - z最后对差分数组做前缀和就能还原出修改后的原数组。举一个例子假设原成绩a[10,20,30,40]现在要给第2到3个学生各加5分 差分数组初始d[0,0,0,0,0]多开一位避免越界 区间加分d[2]5d[4]-5对 d 做前缀和 d[1]0d[2]055d[3]505d[4]5(-5)0最终成绩10010、20525、30535、40040最后如果我的内容对你有帮助请点赞评论收藏。创作不易大家的支持就是我坚持下去的动力
