基础:前缀和&差分
Resolmi Newbie

工作后好久没发新文章了,有些文章其实是很久之前就写完了,但是一直没发。最近搬家了,开始了新的生活,先慢慢找回之前的节奏,把坑都填完

796. 子矩阵的和(模板题)

输入一个列的整数矩阵,再输入个询问,每个询问包含四个整数 ,表示一个子矩阵的左上角坐标和右下角坐标。

对于每个询问输出子矩阵中所有数的和。

输入格式

第一行包含三个整数

接下来行,每行包含个整数,表示整数矩阵。

接下来行,每行包含四个整数,表示一组询问。

输出格式

行,每行输出一个询问的结果。

数据范围

输入样例:

3 4 3
1 7 2 4
3 6 2 8
2 1 2 3
1 1 2 2
2 1 3 4
1 3 3 4

输出样例:

17
27
21

解法一

二维前缀和模板,一维的模板比较简单就不多写了

import java.util.*;
import java.io.*;

class Main {

public static void main(String... args) throws Exception {
PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("./input.txt")));
int[] in = read(br);
int N = in[0], M = in[1], Q = in[2];
int[][] sum = new int[N+1][M+1];
for (int i = 1; i <= N; i++) {
int[] t = read(br);
for (int j = 1; j <= M; j++) {
sum[i][j] = t[j-1] + sum[i][j-1] + sum[i-1][j] - sum[i-1][j-1];
}
}
for (int i = 0; i < Q; i++) {
int[] q = read(br);
int x1 = q[0], y1 = q[1];
int x2 = q[2], y2 = q[3];
out.println(sum[x2][y2]-(sum[x1-1][y2]+sum[x2][y1-1])+sum[x1-1][y1-1]);
}
out.flush();
}

public static int[] read(BufferedReader br) throws Exception {
return Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
}
}

99. 激光炸弹

地图上有个目标,用整数表示目标在地图上的位置,每个目标都有一个价值

注意:不同目标可能在同一位置。

现在有一种新型的激光炸弹,可以摧毁一个包含个位置的正方形内的所有目标。

激光炸弹的投放是通过卫星定位的,但其有一个缺点,就是其爆炸范围,即那个正方形的边必须和轴平行。

求一颗炸弹最多能炸掉地图上总价值为多少的目标。

输入格式

第一行输入正整数,分别代表地图上的目标数目和正方形的边长,数据用空格隔开。

接下来行,每行输入一组数据,每组数据包括三个整数,分别代表目标的坐标,坐标和价值,数据用空格隔开。

输出格式

输出一个正整数,代表一颗炸弹最多能炸掉地图上目标的总价值数目。

数据范围

输入样例:

2 1
0 0 1
1 1 1

输出样例:

1

解法一

其实也是个模板题。.. 注意多个目标会在同一个点

import java.util.*;
import java.io.*;

class Main {

public static void main(String... args) throws Exception {
PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("./input.txt")));
int[] in = read(br);
int MAX = 5010;
int N = in[0], R = in[1];
int[][] w = new int[MAX][MAX];
for (int i = 0; i < N; i++) {
int[] t = read(br);
w[t[0]][t[1]] += t[2];
}
int[][] sum = new int[MAX][MAX];
for (int i = 1; i < MAX; i++) {
for (int j = 1; j < MAX; j++) {
sum[i][j] = w[i-1][j-1] + sum[i][j-1] + sum[i-1][j] - sum[i-1][j-1];
}
}
int res = 0;
for (int i = 1; i < MAX; i++) {
if (i+R-1 >= MAX) break;
for (int j = 1; j < MAX; j++) {
if (j+R-1 >= MAX) break;
int i2 = i+R-1, j2 = j+R-1;
res = Math.max(res, sum[i2][j2]-sum[i-1][j2]-sum[i2][j-1]+sum[i-1][j-1]);
}
}
out.println(res);
out.flush();
}

public static int[] read(BufferedReader br) throws Exception {
return Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
}
}

1292. 元素和小于等于阈值的正方形的最大边长

给你一个大小为 m x n 的矩阵 mat 和一个整数阈值 threshold

请你返回元素总和小于或等于阈值的正方形区域的最大边长;如果没有这样的正方形区域,则返回

示例 1:

Y2wPne.png

输入:mat = [[1,1,3,2,4,3,2],[1,1,3,2,4,3,2],[1,1,3,2,4,3,2]], threshold = 4
输出:2
解释:总和小于 4 的正方形的最大边长为 2,如图所示。

示例 2:

输入:mat = [[2,2,2,2,2],[2,2,2,2,2],[2,2,2,2,2],[2,2,2,2,2],[2,2,2,2,2]], threshold = 1
输出:0

示例 3:

输入:mat = [[1,1,1,1],[1,0,0,0],[1,0,0,0],[1,0,0,0]], threshold = 6
输出:3

示例 4:

输入:mat = [[18,70],[61,1],[25,85],[14,40],[11,96],[97,96],[63,45]], threshold = 40184
输出:2

提示:

解法一

这里直接将之前的 题解 搬过来了,相对来说这题就没那么模板了,结合了二分,还是挺好的

首先看到这道题就意识到了这是个二分答案的题,直接二分边长就行了,左端点,右端点,某个边长满足的时候,大于的都满足,某个不满足的时候,小于的都不满足,解空间具有单调性

所以关键问题就是check怎么写,如果直接暴力枚举所有矩形然后计算时间复杂度会很恐怖,这个时候就可以引入二维前缀和,在的时间下求出子矩阵的和

class Solution {

int[][] sum;

public int maxSideLength(int[][] mat, int threshold) {
int m = mat.length;
int n = mat[0].length;
int left = 1, right = Math.min(m, n);
sum = new int[m+1][n+1];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
sum[i][j] = mat[i-1][j-1] + sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1];
}
}
int res = 0;
while(left <= right){
int mid = left + (right-left)/2;
if(check(mat, mid, threshold)){
res = mid;
left = mid+1;
}else{
right = mid-1;
}
}
return res;
}

public boolean check(int[][] mat, int side, int threshold){
//枚举所有的左端点
for (int i = 1; i+side-1 <= mat.length; i++) {
for (int j = 1; j+side-1 <= mat[0].length; j++) {
int ri = i+side-1, rj = j+side-1;
if(sum[ri][rj]-sum[i-1][rj]-sum[ri][j-1]+sum[i-1][j-1] <= threshold){
return true;
}
}
}
return false;
}
}

798. 差分矩阵(模板题)

输入一个列的整数矩阵,再输入个操作,每个操作包含五个整数 ,其中表示一个子矩阵的左上角坐标和右下角坐标。

每个操作都要将选中的子矩阵中的每个元素的值加上

请你将进行完所有操作后的矩阵输出。

输入格式

第一行包含整数

接下来行,每行包含个整数,表示整数矩阵。

接下来行,每行包含个整数,表示一个操作。

输出格式

行,每行个整数,表示所有操作进行完毕后的最终矩阵。

数据范围

输入样例:

3 4 3
1 2 2 1
3 2 2 1
1 1 1 1
1 1 2 2 1
1 3 2 3 2
3 1 3 4 1

输出样例:

2 3 4 1
4 3 4 1
2 2 2 2

解法一

二维差分模板题,一维的模板也比较简单就不多写了,二维的需要多说几句

和前缀和相反,矩阵中某个元素的值是差分数组的二维前缀和,所以当我们给某个点的差分值加的时候,会使以该点为左上角,到整个矩阵的右下角的矩阵区域元素值增加
,如下图当给的差分值增加的时候,会使得整个蓝色框区域的矩阵元素值都增加
mark
但是这里我们只希望子矩阵的值增加,所以我们需要将其它区域的值减回去。所以我们给以及的差分值减,注意这两块有一个重合区域多减了一次,我们将其加回来就行了

import java.util.*;
import java.io.*;

class Main {

static int[][] diff;
static int n, m, q;
public static void main(String... args) throws Exception {
PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("./input.txt")));
int[] in = read(br);
n = in[0]; m = in[1]; q = in[2];
diff = new int[n+2][m+2];
for (int i = 1; i <= n; i++) {
int[] t = read(br);
for (int j = 1; j <= m; j++) {
incr(i, j, i, j, t[j-1]);
}
}
for (int i = 0; i < q; i++) {
int[] q = read(br);
incr(q[0], q[1], q[2], q[3], q[4]);
}
int[][] matrix = new int[n+2][m+2];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
matrix[i][j] = diff[i][j] + matrix[i-1][j] + matrix[i][j-1] - matrix[i-1][j-1];
out.print(matrix[i][j] + " ");
}
out.println();
}
out.flush();
}

public static void incr(int x1, int y1, int x2, int y2, int c) {
diff[x1][y1] += c;
diff[x1][y2+1] -= c;
diff[x2+1][y1] -= c;
diff[x2+1][y2+1] += c;
}

public static int[] read(BufferedReader br) throws Exception {
return Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
}
}

100. 增减序列

给定一个长度为的数列,每次可以选择一个区间,使下标在这个区间内的数都加一或者都减一。

求至少需要多少次操作才能使数列中的所有数都一样,并求出在保证最少次数的前提下,最终得到的数列可能有多少种。

输入格式

第一行输入正整数

接下来行,每行输入一个整数,第行的整数代表

输出格式

第一行输出最少操作次数。

第二行输出最终能得到多少种结果。

数据范围

输入样例:

4
1
2

输出样例:

1
2

解法一

构建差分数组,根据题目要求,我们的目标就是使得的最小操作次数,一次操作可以使得中任意两个元素,一个加 1,一个减 1,并且求保证最小操作次数的同时,有几种取值情况

这里我们可以将操作按照两个元素的位置进行分类:

  1. 时,加一(减一),减一(加一)
  2. 时,加一(减一),减一(加一),这种情况就只会修改中的一个值,同时使得值不同
  3. 时,加一(减一),减一(加一)
  4. 时,整体加减一,没有意义

中正数之和为,负数绝对值之和为,那么最快使得的操作方式就是每次从中选取一个正数一个负数,使得正数减一,负数加一,操作次数为,这样正负数配对后,剩下的部分就选择操作 2 或者操作 3 进行加一或者减一使其归 0,操作次数为,所以操作总数为:

第二问求的取值情况,其实就是在执行完操作 1 后,剩下的部分执行 2 和 3 所能得到的不同的值,而这 2 种操作中能影响的值的就只有第 2 类操作,执行次第二类操作,就会使得或者减较大时,反之减),执行不同的次数,就能得到不同的值,执行完操作 1 后剩余的部分一共,所以操作 2 的执行次数就有种情况,对应

import java.util.*;
import java.io.*;

class Main {

public static void main(String... args) throws Exception {
PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("./input.txt")));
int N = read(br);
int[] diff = new int[N+2];
for (int i = 1; i <= N; i++) {
int t = read(br);
diff[i] += t; diff[i+1] -= t;
}
long p = 0, q = 0;
for (int i = 2; i <= N; i++) {
if (diff[i] > 0) {
p += diff[i];
} else {
q -= diff[i];
}
}
out.println(Math.max(p, q));
out.println(Math.abs(p-q)+1);
out.flush();
}

public static int read(BufferedReader br) throws Exception {
return Integer.valueOf(br.readLine());
}
}

1526. 形成目标数组的子数组最少增加次数

Difficulty: 困难

给你一个整数数组 target 和一个数组 initial ,initial 数组与 target  数组有同样的维度,且一开始全部为 0 。

请你返回从 initial 得到  target 的最少操作次数,每次操作需遵循以下规则:

  • initial 中选择 任意 子数组,并将子数组中每个元素增加 1 。

答案保证在 32 位有符号整数以内。

示例 1:

输入:target = [1,2,3,2,1]
输出:3
解释:我们需要至少 3 次操作从 intial 数组得到 target 数组。
[0,0,0,0,0] 将下标为 04 的元素(包含二者)加 1
[1,1,1,1,1] 将下标为 13 的元素(包含二者)加 1
[1,2,2,2,1] 将下表为 2 的元素增加 1
[1,2,3,2,1] 得到了目标数组。

示例 2:

输入:target = [3,1,1,2]
输出:4
解释:(initial)[0,0,0,0] -> [1,1,1,1] -> [1,1,1,2] -> [2,1,1,2] -> [3,1,1,2] (target) 。

示例 3:

输入:target = [3,1,5,4,2]
输出:7
解释:(initial)[0,0,0,0,0] -> [1,1,1,1,1] -> [2,1,1,1,1] -> [3,1,1,1,1]
-> [3,1,2,2,2] -> [3,1,3,3,2] -> [3,1,4,4,2] -> [3,1,5,4,2] (target)。

示例 4:

输入:target = [1,1,1,1]
输出:1

提示:

解法一

31th 双周赛 t4,首先明白一点,将数组从通过加一变为target等价于将target通过减一变为

和上面一题一样,不过这题是要连同一起变为 0,且,所以,对应上题中就是,所以最小操作次数就是

class Solution:
def minNumberOperations(self, target: List[int]) -> int:
res = target[0]
for i in range(1, len(target)):
if (d := target[i]-target[i-1]) > 0:
res += d
return res
  • 本文标题:基础:前缀和&差分
  • 本文作者:Resolmi
  • 创建时间:2021-07-04 00:00:00
  • 本文链接:https://imlgw.top/2021/07/04/ba5f35c5/
  • 版权声明:本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!
 评论