工作后好久没发新文章了,有些文章其实是很久之前就写完了,但是一直没发。最近搬家了,开始了新的生活,先慢慢找回之前的节奏,把坑都填完
输入一个 行 列的整数矩阵,再输入 个询问,每个询问包含四个整数 ,表示一个子矩阵的左上角坐标和右下角坐标。
对于每个询问输出子矩阵中所有数的和。
输入格式
第一行包含三个整数 , , 。
接下来 行,每行包含 个整数,表示整数矩阵。
接下来 行,每行包含四个整数 ,表示一组询问。
输出格式
共 行,每行输出一个询问的结果。
数据范围
输入样例:
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
输出样例:
解法一 二维前缀和模板,一维的模板比较简单就不多写了
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)); 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(); } }
地图上有 个目标,用整数 表示目标在地图上的位置,每个目标都有一个价值 。
注意 :不同目标可能在同一位置。
现在有一种新型的激光炸弹,可以摧毁一个包含 个位置的正方形内的所有目标。
激光炸弹的投放是通过卫星定位的,但其有一个缺点,就是其爆炸范围,即那个正方形的边必须和 , 轴平行。
求一颗炸弹最多能炸掉地图上总价值为多少的目标。
输入格式
第一行输入正整数 和 ,分别代表地图上的目标数目和正方形的边长,数据用空格隔开。
接下来 行,每行输入一组数据,每组数据包括三个整数 ,分别代表目标的 坐标, 坐标和价值,数据用空格隔开。
输出格式
输出一个正整数,代表一颗炸弹最多能炸掉地图上目标的总价值数目。
数据范围
输入样例:
输出样例:
解法一 其实也是个模板题。.. 注意多个目标会在同一个点
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)); 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(); } }
给你一个大小为 m x n
的矩阵 mat
和一个整数阈值 threshold
。
请你返回元素总和小于或等于阈值的正方形区域的最大边长;如果没有这样的正方形区域,则返回 。
示例 1:
输入: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 ; } }
输入一个 行 列的整数矩阵,再输入 个操作,每个操作包含五个整数 ,其中 和 表示一个子矩阵的左上角坐标和右下角坐标。
每个操作都要将选中的子矩阵中的每个元素的值加上 。
请你将进行完所有操作后的矩阵输出。
输入格式
第一行包含整数 。
接下来 行,每行包含 个整数,表示整数矩阵。
接下来 行,每行包含 个整数 ,表示一个操作。
输出格式
共 行,每行 个整数,表示所有操作进行完毕后的最终矩阵。
数据范围
输入样例:
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
输出样例:
解法一 二维差分模板题,一维的模板也比较简单就不多写了,二维的需要多说几句
和前缀和相反,矩阵中某个元素 的值是差分数组 到 的二维前缀和,所以当我们给某个点 的差分值加 的时候,会使以该点为左上角,到整个矩阵的右下角 的矩阵区域元素值 增加 ,如下图当给 的差分值增加 的时候,会使得整个蓝色框区域的矩阵元素值都增加 但是这里我们只希望子矩阵 的值增加,所以我们需要将其它区域的值减回去。所以我们给 以及 的差分值减 ,注意这两块有一个重合区域 多减了一次,我们将其加回来就行了
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)); 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(); } }
给定一个长度为 的数列 ,每次可以选择一个区间 ,使下标在这个区间内的数都加一或者都减一。
求至少需要多少次操作才能使数列中的所有数都一样,并求出在保证最少次数的前提下,最终得到的数列可能有多少种。
输入格式
第一行输入正整数 。
接下来 行,每行输入一个整数,第 行的整数代表 。
输出格式
第一行输出最少操作次数。
第二行输出最终能得到多少种结果。
数据范围
输入样例:
输出样例:
解法一 构建差分数组 ,根据题目要求,我们的目标就是使得 的最小操作次数,一次操作可以使得 中任意两个元素,一个加 1,一个减 1,并且求保证最小操作次数的同时, 有几种取值情况
这里我们可以将操作按照两个元素的位置进行分类:
当 时, 加一(减一), 减一(加一)
当 时, 加一(减一), 减一(加一),这种情况就只会修改 中的一个值,同时使得 值不同
当 时, 加一(减一), 减一(加一)
当 时,整体加减一,没有意义
设 中正数之和为 ,负数绝对值之和为 ,那么最快使得 的操作方式就是每次从中选取一个正数一个负数,使得正数减一,负数加一,操作次数为 ,这样正负数配对后,剩下的部分就选择操作 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)); 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()); } }
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 ] 将下标为 0 到 4 的元素(包含二者)加 1 。 [1 ,1 ,1 ,1 ,1 ] 将下标为 1 到 3 的元素(包含二者)加 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