【CSP考题扩展】前缀和/差分练习

本文主要是介绍【CSP考题扩展】前缀和/差分练习，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

【深进1.例1 求区间和】

题目描述

给定 $n$ 个正整数组成的数列 $a_1, a_2, \cdots, a_n$ 和 $m$ 个区间 $l_i,r_i]$ ，分别求这 $m$ 个区间的区间和。

对于所有测试数据， $n,m\le10^5,a_i\le 10^4$

输入格式

第一行，为一个正整数 $n$ 。

第二行，为 $n$ 个正整数 $a_1,a_2, \cdots ,a_n$

第三行，为一个正整数 $m$ 。

接下来 $m$ 行，每行为两个正整数 $l_i,r_i$ ，满足 $1\le l_i\le r_i\le n$

输出格式

共 $m$ 行。

第 $i$ 行为第 $i$ 组答案的询问。

$1\le n, m\le 10^5$ ， $\le a_i\le 10^4$

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;long long n, m, t, a, b;int main() {cin >> n;vector<int>perfix(n + 1, 0), arr(n);for (size_t i = 0; i < n; i++){cin >> arr[i];}for (size_t i = 0; i < n; i++){perfix[i + 1] = perfix[i] + arr[i];}cin >> m;for (size_t i = 0; i < m; i++){cin >> a >> b;cout << perfix[b] - perfix[a - 1] << endl;}return 0;
}

【最大加权矩形】

题目描述

为了更好的备战 NOIP2013，电脑组的几个女孩子 LYQ,ZSC,ZHQ 认为，我们不光需要机房，我们还需要运动，于是就决定找校长申请一块电脑组的课余运动场地，听说她们都是电脑组的高手，校长没有马上答应他们，而是先给她们出了一道数学题，并且告诉她们：你们能获得的运动场地的面积就是你们能找到的这个最大的数字。

校长先给他们一个 $n\times n$ 矩阵。要求矩阵中最大加权矩形，即矩阵的每一个元素都有一权值，权值定义在整数集上。从中找一矩形，矩形大小无限制，是其中包含的所有元素的和最大。矩阵的每个元素属于 $[- 127, 127]$ ,例如

 0 –2 –7  0 9  2 –6  2
-4  1 –4  1 
-1  8  0 –2

在左下角：

9  2
-4  1
-1  8

和为 $15$ 。

几个女孩子有点犯难了，于是就找到了电脑组精打细算的 HZH，TZY 小朋友帮忙计算，但是遗憾的是他们的答案都不一样，涉及土地的事情我们可不能含糊，你能帮忙计算出校长所给的矩形中加权和最大的矩形吗？

输入格式

第一行： $n$ ，接下来是 $n$ 行 $n$ 列的矩阵。

输出格式

最大矩形（子矩阵）的和。

#include <iostream>
#include <vector>
#include <climits> // For INT_MIN
#include <algorithm>
using namespace std;int n, maxSum = INT_MIN;int main() {cin >> n;vector<vector<int>> matrix(n, vector<int>(n));vector<vector<int>> prefixMatrix(n + 1, vector<int>(n + 1, 0));for (auto& it : matrix) {for (auto& jt : it) {cin >> jt;}}for (size_t i = 1; i < n + 1; i++) {for (size_t j = 1; j < n + 1; j++) {prefixMatrix[i][j] = prefixMatrix[i][j - 1] + prefixMatrix[i - 1][j] - prefixMatrix[i - 1][j - 1] + matrix[i - 1][j - 1];}}// 遍历所有可能的左上角位置for (size_t i = 1; i <= n; i++) {for (size_t j = 1; j <= n; j++) {// 遍历所有可能的右下角位置for (size_t k = i; k <= n; k++) {for (size_t p = j; p <= n; p++) {// 使用前缀和矩阵计算当前矩形的和// sum 表示从 (i, j) 到 (k, p) 形成的矩形的加权和int sum = prefixMatrix[k][p] - prefixMatrix[i - 1][p] - prefixMatrix[k][j - 1] + prefixMatrix[i - 1][j - 1];// 更新最大加权和maxSum = max(maxSum, sum);}}}}cout << maxSum;return 0;
}

【语文成绩】

题目背景

语文考试结束了，成绩还是一如既往地有问题。

题目描述

语文老师总是写错成绩，所以当她修改成绩的时候，总是累得不行。她总是要一遍遍地给某些同学增加分数，又要注意最低分是多少。你能帮帮她吗？

输入格式

第一行有两个整数 $n$ ， $p$ ，代表学生数与增加分数的次数。

第二行有 $n$ 个数， $a_1 \sim a_n$ ，代表各个学生的初始成绩。

接下来 $p$ 行，每行有三个数， $x$ ， $y$ ， $z$ ，代表给第 $x$ 个到第 $y$ 个学生每人增加 $z$ 分。

输出格式

输出仅一行，代表更改分数后，全班的最低分。

#include <iostream>
#include <vector>
#include <climits> // For INT_MIN
#include <algorithm>
using namespace std;long long n, p, x, y, z, minGrade = INT_MAX;int main() {cin >> n >> p;vector<long long>grade(n);vector<long long>diffGrade(n);vector<long long>finalGrade(n);for (size_t i = 0; i < n; i++){cin >> grade[i];}// 构建差分数组diffGrade[0] = grade[0];for (size_t i = 1; i < n; i++){diffGrade[i] = grade[i] - grade[i - 1];}// 批量增减for (size_t i = 0; i < p; i++){cin >> x >> y >> z;diffGrade[x - 1] += z;if (y < n) diffGrade[y] -= z;}// 恢复原数组finalGrade[0] = diffGrade[0];for (size_t i = 1; i < n; i++){finalGrade[i] = finalGrade[i - 1] + diffGrade[i];}for (size_t i = 0; i < n; i++){minGrade = min(minGrade, finalGrade[i]);}cout << minGrade;return 0;
}

【地毯】

题目描述

在 $n\times n$ 的格子上有 $m$ 个地毯。

给出这些地毯的信息，问每个点被多少个地毯覆盖。

输入格式

第一行，两个正整数 $n, m$ 。意义如题所述。

接下来 $m$ 行，每行两个坐标 $x_1,y_1)$ 和 $x_2,y_2)$ ，代表一块地毯，左上角是 $x_1,y_1)$ ，右下角是 $x_2,y_2)$ 。

输出格式

输出 $n$ 行，每行 $n$ 个正整数。

第 $i$ 行第 $j$ 列的正整数表示 $(i, j)$ 这个格子被多少个地毯覆盖。

#include <iostream>
#include <vector>
using namespace std;int n, m, xx1, xx2, yy1, yy2;int main() {cin >> n >> m;vector<vector<int>>diffArea(n, vector<int>(n, 0));vector<vector<int>>resultArea(n, vector<int>(n, 0));for (size_t i = 0; i < m; i++){cin >> xx1 >> yy1 >> xx2 >> yy2;for (size_t i1 = xx1 - 1; i1 < xx2; i1++) // 将二维差分数组视为n个大小为n的一维差分数组{diffArea[i1][yy1 - 1] += 1;if (yy2 < n) diffArea[i1][yy2] -= 1;}}for (size_t i = 0; i < n; i++){resultArea[i][0] = diffArea[i][0];for (size_t j = 1; j < n; j++){resultArea[i][j] = resultArea[i][j - 1] + diffArea[i][j];}}for (auto& it : resultArea) {for (auto& jt : it) {cout << jt << " ";}cout << endl;}return 0;
}