【蓝桥杯每日一题】3.20

“蓝桥杯是编程成人礼——那些崩溃的深夜，终将变成你碾压题海的底气”

        今天我们来点有意思的算法：前缀和

        前缀和与差分的核⼼思想是预处理，可以在暴⼒枚举的过程中，快速给出查询的结果，从⽽优化间复杂度。
        是经典的⽤空间替换时间的做法。

3.19 前缀和

        如图所示，这里有一个数组：

        那么他的前缀和数组（假设数组名为 f ）f [ i ]就是数组a在第 i 个元素前的所有元素的累加，如下图：

        这就是前缀和数组，至于他有什么用，让我们去题目里面一探究竟

一、【模板】前缀和

        题目链接：

        【模板】前缀和

        题目描述：

        解题思路：

        题目的意思是给我们一个数组，在给我们一个范围，我们需要将范围里的数字全部累加最后输出即可。

        这里我们很容易就可以想到一种暴力解法，直接枚举数组中从 l 到 r 的元素全部累加起来就可以了，但是这样的时间复杂度是O(q * n) 的，也就是10^10，必定会超时，因此我们就需要换一个解题的思路，前缀和数组就是为了解决这些问题诞生的数组，专门用于解决数组中连续一段元素的和的问题

        因为我们只需要在前缀和数组中求 f [ r ] - f [ l  - 1 ] 就可以得到我们想要的目标值，理由如图：

        用前缀和数组来处理此问题只需要O(1)的时间复杂度即可

        解题代码：

#include <iostream>using namespace std;typedef long long LL;const int N = 1e5 + 10;LL a[N]; // 原数组
LL f[N]; // 前缀和数组int n, q;int main()
{cin >> n >> q;for(int i = 1; i <= n; i++) // 这里初始化前缀和数组必须从1开始{    cin >> a[i];f[i] = f[i - 1] + a[i];}while(q--){int left, right; cin >> left >> right;cout << f[right] - f[left - 1] << endl;}return 0;
}

二、最大子段和

        题目链接：

        P1115 最大子段和

        题目描述：

        解题思路：

        这题我们依然利用前缀和来解决，题目中要求我们求最大子段和，我们可以用前缀和减去前面的前驱最⼩值

        解题代码：

#include <iostream>using namespace std;typedef long long LL;const int N = 2e5 + 10;LL f[N]; // 预处理前缀和数组int n;int main()
{cin >> n;for (int i = 1; i <= n; i++){LL a; cin >> a;f[i] = f[i - 1] + a; // 初始化前缀和数组}LL prevmin = 0; LL ret = -1e10;for (int i = 1; i <= n; i++){ret = max(ret, f[i] - prevmin);prevmin = min(prevmin, f[i]);}cout << ret << endl;return 0;
}

三、⼆维前缀和

        题目链接：

        【模板】二维前缀和

        题目描述：

        解题思路：

        我们直接看图吧，比如我们需要求 f [ i ][ j ] 的二维前缀和

         这里我们可以得到构造二维前缀和数组的公式：

        f[i][j] = f[i][j - 1] + f[i - 1][j] - f[i - 1][j - 1] + a[i][j]

         如果想求出题目中给定区域的和，就需要我们在思考一下

        如上图，我们就可以得到另一个公式：

        sum = f[x2][y2] - f[x1 - 1][y2] - f[x2][y1 - 1] + f[x1- 1][y1 - 1]

        有了上面两个公式就可以写代码啦 

        解题代码：

#include <iostream>using namespace std;typedef long long LL;const int N = 1010;LL f[N][N];
int n, m, q;int main()
{cin >> n >> m >> q;// 预处理前缀和数组for(int i = 1; i <= n; i++){for(int j = 1; j <= m; j++){LL a; cin >> a;f[i][j] = f[i][j - 1] + f[i - 1][j] - f[i - 1][j - 1] + a;}}while(q--){int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;cout << f[x2][y2] - f[x1 - 1][y2] - f[x2][y1 - 1] + f[x1 - 1][y1 - 1] << endl;}return 0;
}

四、激光炸弹

        题目链接：

        P2280 [HNOI2003] 激光炸弹

        题目描述：

        解题思路：

        这题直接利用上面的二维前缀和，加上暴力枚举在地图上所有的题目给的正方形就行了

        解题代码：

#include <iostream>using namespace std;const int N = 5010;int a[N][N], f[N][N];int n, m;int main()
{cin >> n >> m;while (n--){int x, y, v; cin >> x >> y >> v;a[x + 1][y + 1] += v; // 处理前缀和数组下标要大于1，因此这里把x,y都+1}int n = 5001, ret = 0; // 地图大小// 预处理前缀和数组for (int i = 1; i <= n; i++){for (int j = 1; j <= n; j++){f[i][j] = f[i - 1][j] + f[i][j - 1] - f[i - 1][j -1] + a[i][j];}}// 暴力枚举所有正方形for (int i = 1; i <= n - m + 1; i++){for (int j = 1; j <= n - m + 1; j++){int x1 = i, y1 = j, x2 = i + m - 1, y2 = j + m - 1;int sum = f[x2][y2] - f[x1 - 1][y2] - f[x2][y1 - 1] +f[x1 - 1][y1 - 1];ret = max(sum, ret);}}cout << ret << endl;return 0;
}

        OK啦，本期内容就到这吧，明天讲差分算法，感兴趣的可以点个关注哈