做网站和网页区别,山东青岛网站制作公司,大型网站建设公司制作网站,陈幼坚设计公司官网题目
差分矩阵 题解 只有一个操作#xff1a; void insert(int x1, int y1, int x2, int y2, int c){b[x1][y1] c;b[x2 1][y1] - c;b[x1][y2 1] - c;b[x2 1][y2 1] c;
}利用差分的思想#xff0c;扩展到二维上。 insert函数作用是将矩阵之内的数全部加上c#xff0c;…题目
差分矩阵 题解 只有一个操作 void insert(int x1, int y1, int x2, int y2, int c){b[x1][y1] c;b[x2 1][y1] - c;b[x1][y2 1] - c;b[x2 1][y2 1] c;
}利用差分的思想扩展到二维上。 insert函数作用是将矩阵之内的数全部加上c 其余部分不会变。 而最后的实现其实就是前面子矩阵的和这道题的方法也就是将最后得到的b数组进行二维前缀和的操作, 得到的b数组就是答案 举例理解 首先 假设 有一个4X4 的小方块要加上 2 那么我们先将方块的左上角(1, 1)加上2。然后你想我们最后是要进行二维前缀和的运算的那么为了不让其它部分受到影响我们要将1, 55, 1上的数减去2抵消从1 1传递过来的2的影响这样后面的数也不会受到影响了。注意有一个位置就是b5, 5它减去了两次2因为它同时受b5 1b1 5的影响所以我们还要在b5 5再加上2.代码
答案
#include bits/stdc.h
using namespace std;
const int N 1010;int n, m, q;
int a[N][N], b[N][N];void insert(int x1, int y1, int x2, int y2, int c){b[x1][y1] c;b[x2 1][y1] - c;b[x1][y2 1] - c;b[x2 1][y2 1] c;
}int main(){scanf(%d%d%d, n, m, q);for(int i 1; i n; i )for(int j 1;j m; j ){scanf(%d, a[i][j]);insert(i, j, i, j, a[i][j]);}for(int i 1; i q; i ){int x1, x2, y1, y2, c;scanf(%d%d%d%d%d, 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 )b[i][j] b[i - 1][j] b[i][j - 1] - b[i - 1][j - 1];for(int i 1; i n; i ){for(int j 1; j m; j )printf(%d , b[i][j]);puts();} return 0;
}
