公共法律知识培训网站,长春seo网站排名优化,公众平台是什么,微网站建设包括哪些前言 上一期我们分享了一维差分的使用方法#xff0c;这一期我们将接着上期的内容带大家了解二位差分的使用方法#xff0c;话不多说#xff0c;LET’S GO!#xff08;上一期链接#xff09;
二维差分 二维差分我们可以用于对矩阵区间进行多次操作的题。 二维差分我们还…前言 上一期我们分享了一维差分的使用方法这一期我们将接着上期的内容带大家了解二位差分的使用方法话不多说LET’S GO!上一期链接
二维差分 二维差分我们可以用于对矩阵区间进行多次操作的题。 二维差分我们还可以采用一维差分的思想如图假如我们要对区间[x1,x2],[y1,y2]的元素都1 即 arrsum[x1][y1] 1;arrsum[x1][y21] - 1;arrsum[x21 ][y1] - 1;arrsum[x21][y21] 1;思路就是这样操作完之后直接求数组全缀合就是目标矩阵数组下面我们上实战。 给出矩阵数组arr共有n行m列对其进行t次操作每次操作会对[ x1 , x2 ],[ y1,y2 ]区间内的元素1请输出进行操作后的arr数组。 输入样例 第一行为n,m和q 往后n行为矩阵数组的元素 往后q行为x1,y1,x2,y2 测试样例 3 3 2 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 3 3 输出样例 2 2 1 2 3 2 1 2 2 题解
#includestdio.h
int arr[100][100];
int arrsum[100][100];//前缀和数组
int main()
{int n, m, t;scanf(%d %d %d, n, m, t);for (int i 1; i n; i)//输入数组{for (int j 1; j m; j){scanf(%d, arr[i][j]);}}for (int i 1; i n; i)//操作arrsum数组使其前缀和为目标数组{for (int j 1; j m; j){arrsum[i][j] arr[i][j];arrsum[i1][j] - arr[i][j];arrsum[i][j1] - arr[i][j];arrsum[i1][j1] arr[i][j];}}while (t--)//t次操作{int x1, y1, x2, y2;scanf(%d %d %d %d, x1, y1, x2, y2);arrsum[x1][y1] 1;arrsum[x1][y21] - 1;arrsum[x21 ][y1] - 1;arrsum[x21][y21] 1;}for (int i 1; i n; i)//求前缀和{for (int j 1; j m; j){arrsum[i][j] arrsum[i-1][j]arrsum[i][j-1]-arrsum[i-1][j-1]; }}for (int i 1; i n; i)//打印目标数组{for (int j 1; j m; j){printf(%d , arrsum[i][j]);}printf(\n);}return 0;
}尾声 本期分享就到这里如果觉得博主讲的不错的话请给博主一个关注点赞收藏支持一下吧~博主还将持续分享更多知识我们下期再见
