ACM - 其他算法 - 基础（前缀和 + 差分）

一、前缀和

模板

//一维前缀和
S[i] = a[1] + a[2] + ... a[i]
a[l] + ... + a[r] = S[r] - S[l - 1]//二维前缀和
S[i, j] = 第i行j列格子左上部分所有元素的和
以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵的和为：
S[x2, y2] - S[x1 - 1, y2] - S[x2, y1 - 1] + S[x1 - 1, y1 - 1]

例题1、区间余数求K倍区间个数：AcWing 1230. K倍区间

原题链接: https://www.acwing.com/problem/content/1232/

(原题来源: 第八届蓝桥杯省赛C++B组,第八届蓝桥杯省赛JAVAB组)

import java.util.Scanner;public class Main{public static int[] sum = new int[100010];  //前缀和取模后public static int[] cnt = new int[100010];  //个数public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();int k = sc.nextInt();long ans = 0;cnt[0] = 1;for (int i = 1; i <= n; ++ i) {sum[i] = sum[i - 1] + sc.nextInt(); //计算前缀和sum[i] %= k;  //求出k的整数次倍剩下的数ans += cnt[sum[i]];  //相当于减去前面的余数,得出以i为终点的合法子序列的种数++ cnt[sum[i]];     //更新}System.out.println(ans);}
}

例题2、前缀和+哈希求最长个数平分子串:Leetcode 面试题 17.05 字母与数字

原题链接:https://leetcode-cn.com/problems/find-longest-subarray-lcci/

思路

字母+1,数字-1,获得array的前缀和数组arr,同时记录和维护当前的sum的最远索引位置,比如对于A 1 A A 1 1 A 1 1 1 A 1 1 A,可以获得前缀和数组:1 0 1 2 1 0 1 0 -1 -2 -1.
我们可以发现对于第一个A来说,能和它匹配的最长子数组是最后一个0的位置.
以此类比,假如当前位置是字母,其前缀和为a,那么最远能匹配的位置一定是最远的前缀和为a-1的地方;
反之,假如当前位置是数字,其前缀和为a,那么最远能匹配的位置一定是最远的前缀和为a+1的地方.

class Solution {
public:static const int N = 100000;int book[N * 2 + 20], arr[N + 20];vector<string> findLongestSubarray(vector<string>& array) {int num = 0, length = array.size();for (int i = 0; i < length; ++ i) {if (isNum(array[i][0])) -- num;else ++ num;book[num + N] = i;arr[i] = num;}vector<string> ans;int maxx = 0, l = -1, r = -1;for (int i = 0; i < length; ++ i) {if (isNum(array[i][0])) { int a = book[N + arr[i] + 1];if (a > i && a - i > maxx) {maxx = a - i;l = i, r = a;}}else {int a = book[N + arr[i] - 1];if (a > i && a - i > maxx) {maxx = a - i;l = i, r = a;}}}if (maxx == 0) return ans;else {for (int i = l; i <= r; ++ i) {ans.push_back(array[i]);}return ans;}}bool isNum(char c) {return c >= '0' && c <= '9';}
};

二、差分

1、一维差分

AcWing 797. 差分

原题链接：https://www.acwing.com/problem/content/799/

差分定义

首先给定一个原数组a：a[1], a[2], a[3]……a[n];

然后我们构造一个数组b ： b[1] ,b[2] , b[3]…… b[i];

使得 a[i] = b[1] + b[2 ]+ b[3] +…… + b[i]

也就是说，a数组是b数组的前缀和数组，反过来我们把b数组叫做a数组的差分数组。
换句话说，每一个a[i]都是b数组中从头开始的一段区间和。

解法

给区间[l, r]中的每个数加上c：B[l] += c, B[r + 1] -= c

代码

#include<bits/stdc++.h>using namespace std;const int N = 100010;//add为差分数组，表示当前位置的变化
int nums[N], add[N];int main() {int n, m;cin >> n >> m;for (int i = 1; i <= n; ++ i) cin >> nums[i];while (m --) {int l, r, c;cin >> l >> r >> c;add[l] += c;add[r + 1] -= c;}for (int i = 1; i <= n; ++ i) {add[i] += add[i - 1];nums[i] += add[i];cout << nums[i] << " ";}return 0;
}

2、二维差分

AcWing 798. 差分矩阵
原题链接：https://www.acwing.com/problem/content/800/


看代码应该就差不多了。

#include <bits/stdc++.h>using namespace std;const int N = 1010;int nums[N][N], add[N][N];  //add为差分矩阵void insert(int x1, int y1, int x2, int y2, int c) {add[x1][y1] += c;add[x1][y2 + 1] -= c;add[x2 + 1][y1] -= c;add[x2 + 1][y2 + 1] += c;
}int main() {int n, m, q;cin >> n >> m >> q;for (int i = 1; i <= n; ++ i) {for (int j = 1; j <= m; ++ j) {cin >> nums[i][j];}}while (q --) {int x1, y1, x2, y2, c;cin >> x1 >> y1 >> x2 >> y2 >> c;insert(x1, y1, x2, y2, c);}for (int i = 1; i <= n; ++ i) {for (int j = 1; j <= m; ++ j) {add[i][j] += add[i - 1][j] + add[i][j - 1] - add[i - 1][j - 1];nums[i][j] += add[i][j];cout << nums[i][j] << " ";}cout << endl;}return 0;
}