上链接:P3397 地毯 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)https://www.luogu.com.cn/problem/P3397
上题干:
题目描述
在 n×n 的格子上有 m 个地毯。
给出这些地毯的信息,问每个点被多少个地毯覆盖。
输入格式
第一行,两个正整数 n,m。意义如题所述。
接下来 m 行,每行两个坐标 (x1,y1) 和 (x2,y2),代表一块地毯,左上角是 (x1,y1),右下角是(x2,y2)。
输出格式
输出 n 行,每行 n 个正整数。
第 i 行第 j 列的正整数表示 (i,j) 这个格子被多少个地毯覆盖。
输入输出样例
输入 #1复制
5 3 2 2 3 3 3 3 5 5 1 2 1 4输出 #1复制
0 1 1 1 0 0 1 1 0 0 0 1 2 1 1 0 0 1 1 1 0 0 1 1 1说明/提示
样例解释
覆盖第一个地毯后:
0 0 0 0 0 0 1 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 覆盖第一、二个地毯后:
0 0 0 0 0 0 1 1 0 0 0 1 2 1 1 0 0 1 1 1 0 0 1 1 1 覆盖所有地毯后:
0 1 1 1 0 0 1 1 0 0 0 1 2 1 1 0 0 1 1 1 0 0 1 1 1
数据范围
对于 20% 的数据,有 n≤50,m≤100。
对于 100% 的数据,有 n,m≤1000。
在上一篇已经讲过了差分是什么,和一维差分:
《洛谷深入浅出进阶篇》 P2367语文成绩——差分-CSDN博客https://blog.csdn.net/louisdlee/article/details/134400596 这章的内容来介绍一下,二维差分。
假设b[i,j]为差分数组,a[i,j]为原数组
b[i,j]和a[i,j]满足下面这个性质:
(只要是差分就应该满足这个性质)
但是根据题目的不同,差分数组的求法也有所不同
但是我们求答案的时候一定要记住四个字:前加后减
给大家举几个例子理解:
假设这是第一块地毯(原数组),
1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|
2 | 1 | 1 | 0 | 0 |
3 | 1 | 1 | 0 | 0 |
4 | 0 | 0 | 0 | 0 |
5 | 0 | 0 | 0 | 0 |
那么它的差分数组可以是这样的。
1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|
2 | 1 | 0 | -1 | 0 |
3 | 1 | 0 | -1 | 0 |
4 | 0 | 0 | 0 | 0 |
5 | 0 | 0 | 0 | 0 |
假设这是第二块地毯:
0 | 0 | 0 | 0 | 0 |
---|---|---|---|---|
0 | 0 | 0 | 0 | 0 |
0 | 0 | 1 | 1 | 1 |
0 | 0 | 1 | 1 | 1 |
0 | 0 | 1 | 1 | 1 |
那么它的差分数组我想你们应该可以想到了吧:(加了一列虚拟边界来表示,其实我们真实遍历的时候不会扫描到n*m之外的格子)
1 | 2 | 3 | 4 | 5 | 6 |
---|---|---|---|---|---|
2 | 0 | 0 | 0 | 0 | 0 |
3 | 0 | 1 | 0 | 0 | -1 |
4 | 0 | 1 | 0 | 0 | -1 |
5 | 0 | 1 | 0 | 0 | -1 |
我们发现:
-1的位置都是在原来矩阵的后面一列,
假设左上角为(x1,y1) 右下角为(x2,y2)
那么第一列的-1应该在 (x1,y2+1)处
第二列的-1应该在(x1+1,y2+1)处
因为我们加了虚拟边界,当-1出现在原来的边界外的时候,也不用担心。
上代码:
const int N = 1e3 + 10;
int a[N][N];
int b[N][N];
int main()
{int n, m;cin >> n >> m;while (m--) {int x1, y1, x2, y2;cin >> x1 >> y1 >> x2 >> y2;for (int i = x1; i <= x2; i++){b[i][y1]++;b[i][y2 + 1]--;}}for (int i = 1; i <= n; i++){for (int j = 1; j <= n; j++){b[i][j] += b[i][j - 1];cout << b[i][j] << ' ';}cout << endl;}
}