Java模板
1:构造差分数组b[i][j] = S[i][j] - S[i-1][j] - S[i][j-1] + S[i-1][j-1];
2:给以(x1, y1)为左上角,(x2, y2)为右下角的子矩阵中的所有元素加上c:
b[x1][y1] += c;
b[x2 + 1][y1] -= c;
b[x1][y2 + 1] -= c;
b[x2 + 1][y2 + 1] += c;
写代码的话记住这两个公式就可以了;第一个公式是由二维前缀和公式推导出来的,记住二维前缀和公式就可以了;
二维前缀和公式:
S[i][j] = S[i-1][j] + S[i][j-1] - S[i-1][j-1] + a[i][j];
换下位置就可以得出 b[i][j] = S[i][j] - S[i-1][j] - S[i][j-1] + S[i-1][j-1];
我们用这个公式来构造差分数组b[n][n],没有用y总的插入函数,我觉着这样会更好理解一些
第二个公式的话就不推导了,y总讲的挺清晰的,大概意思就是,为了让某个固定矩阵的元素都加上c,我们先一个大范围都加上c,然后在去除固定矩阵边界以外的c,因为会有叠加-c,需要所以再加上叠加的部分;这么一看和一维差分的思想是一样的;
思路
1:初始化前缀和数组S[n][n]
2:初始化差分数组b[n][n]
3:利用公式对差分数组进行操作
4:求差分数组b[n][n]的前缀和
5:输出结果
只要把思路实现就是下面的代码
先放出超时的代码,看起来会简洁很多(Scanner + Sout)
import java.util.Scanner;
public class Main{
private static int N = 1010;
public static void main(String[] args){
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int m = in.nextInt();
int q = in.nextInt();
int[][] S = new int[N][N]; //初始化前缀和数组S[n][n]
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
S[i][j] = in.nextInt();
}
}
int[][] b = new int[N][N]; //初始化差分数组b[n][n]
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
b[i][j] = S[i][j] - S[i-1][j] - S[i][j-1] + S[i-1][j-1];
}
}
while(q-- > 0){ //对差分数组进行操作
int x1 = in.nextInt();
int y1 = in.nextInt();
int x2 = in.nextInt();
int y2 = in.nextInt();
int c = in.nextInt();
b[x1][y1] += c;
b[x2+1][y1] -= c;
b[x1][y2+1] -= c;
b[x2+1][y2+1] += c;
}
for(int i = 1; i <= n; i++){ //把差分数组合并为前缀和数组
for(int j = 1; j <= m; j++){
b[i][j] = b[i-1][j] + b[i][j-1] - b[i-1][j-1] + b[i][j];
}
}
for(int i = 1; i <= n; i++){ //输出结果
for(int j = 1; j <= m; j++){
System.out.print(b[i][j] + " ");
}
System.out.println();
}
}
}
可以AC的代码(BufferedReader + BufferWriter)
我记得y总是在第一题的时候说过BufferedReader会比Scanner快几十倍,但是我一直偷懒,一直用的Scanner;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.IOException;
public class Main{
private static int N = 1010;
public static void main(String[] args) throws IOException{
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
String[] str1 = reader.readLine().split(" "); //读取第一行数据并以空格进行分割;
int n = Integer.parseInt(str1[0]);
int m = Integer.parseInt(str1[1]);
int q = Integer.parseInt(str1[2]);
int[][] S = new int[N][N]; //初始化前缀和数组S[n][n]
for(int i = 1; i <= n; i++){
String[] str2 = reader.readLine().split(" "); //读取n行数据
for(int j = 1; j <= m; j++){
S[i][j] = Integer.parseInt(str2[j-1]); //因为数组中是从0开始存储,也就要从0开始读取
}
}
int[][] b = new int[N][N];
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
b[i][j] = S[i][j] - S[i-1][j] - S[i][j-1] + S[i-1][j-1]; //初始化差分数组b[i][j]
}
}
while(q-- > 0){ //对差分数组进行操作
String[] str3 = reader.readLine().split(" ");
int x1 = Integer.parseInt(str3[0]);
int y1 = Integer.parseInt(str3[1]);
int x2 = Integer.parseInt(str3[2]);
int y2 = Integer.parseInt(str3[3]);
int k = Integer.parseInt(str3[4]);
b[x1][y1] += k;
b[x2 + 1][y1] -= k;
b[x1][y2 + 1] -= k;
b[x2 + 1][y2 + 1] += k;
}
for(int i = 1; i <= n; i++){ //求差分数组b[n]的前缀和
for(int j = 1; j <= m; j++){
b[i][j] = b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1] + b[i][j];
writer.write(b[i][j] + " ");
}
writer.write("\n");
}
writer.flush();
reader.close();
writer.close();
}
}