AcWing 798. 差分矩阵
原题链接
简单
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int n, m, q;
int a[N][N], s[N][N];
int main()
{
cin >> n >> m >> q;
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
scanf("%d", &s[i][j]);
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
a[i][j] = s[i][j] - s[i - 1][j] - s[i][j - 1] + s[i - 1][j - 1];
while (q -- )
{
int x1, y1, x2, y2, c;
scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &c);
a[x1][y1] += c;
a[x1][y2 + 1] -= c;
a[x2 + 1][y1] -= c;
a[x2 + 1][y2 + 1] += c;
}
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
s[i][j] = a[i][j] + s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
for (int i = 1; i <= n; i ++ )
{
for (int j = 1; j <= m; j ++ ) printf("%d ", s[i][j]);
cout << endl;
}
return 0;
}
找了这么多,终于有和我一样想法的人了,
顶一下
确石,明显这个更适合我们这种入门的
他们那种思想学了很久都没学会,瞎耽误时间了QAQ
加个注释方便理解
这个puts函数不是很理解,为啥去掉就报错啊
puts自带换行,所以puts一个空串就相当于输出一个换行
了解了,谢谢
感谢分享
可以解释一下吗?我有点看不懂a[i][j] = s[i][j] - s[i - 1][j] - s[i][j - 1] + s[i - 1][j - 1];
就是求差分数组里面的每个元素的值呀,和我们之前二维矩阵的前缀和那个公式是一样的,把前缀和的公式里面的a[i][j]移到左边,就得到了这个式子,然后理解一下,前缀和里面每个元素(格子)就是这个aij不就是差分元素嘛,这样就构造好了差分数组
前缀和反过来。
请问这里的s[][]不是原数组的每个元素嘛,
感谢!
顶一个,想法一样,但是我写错了
跟一维差分是一样的思路嘿嘿 我也是这种方法 标标准准的按照差分公示来构建差分数组,,然后根据推理将[x1,y1] 到[x2,y2]这个矩阵的元素全部加上C,,,最后按照差分求前缀和的公示往里套就可以了
很棒很棒,谢谢作者啦!
感谢
感谢题解
感谢题解
写的很棒
谢谢作者了
更易懂 谢谢啦