【题目来源】
洛谷：P3397 地毯 - 洛谷
【题目描述】
在 \(n\times n\) 的格子上有 \(m\) 个地毯。
给出这些地毯的信息，问每个点被多少个地毯覆盖。
【输入】
第一行，两个正整数 \(n,m\)。意义如题所述。
接下来 \(m\) 行，每行两个坐标 \((x_1,y_1)\) 和 \((x_2,y_2)\)，代表一块地毯，左上角是 \((x_1,y_1)\)，右下角是 \((x_2,y_2)\)。
【输出】
输出 \(n\) 行，每行 \(n\) 个正整数。
第 \(i\) 行第 \(j\) 列的正整数表示 \((i,j)\) 这个格子被多少个地毯覆盖。
【输入样例】
5 3
2 2 3 3
3 3 5 5
1 2 1 4
【输出样例】
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
【算法标签】
《洛谷 P3397 地毯》 #枚举# #前缀和#
【代码详解】
#include <bits/stdc++.h>
using namespace std;int n, m; // n: 矩阵大小，m: 操作次数
int a[1005][1005]; // 二维差分数组int main()
{// 输入矩阵大小和操作次数cin >> n >> m;// 处理每个矩形区域操作while (m--){int x1, y1, x2, y2;cin >> x1 >> y1 >> x2 >> y2;// 对每行进行差分处理for (int i = x1; i <= x2; i++){a[i][y1] += 1; // 区间起始位置+1a[i][y2 + 1] -= 1; // 区间结束位置+1处-1}}// 计算前缀和并输出结果矩阵for (int i = 1; i <= n; i++){for (int j = 1; j <= n; j++){// 计算前缀和得到最终值a[i][j] = a[i][j] + a[i][j - 1];cout << a[i][j] << " ";}cout << endl;}return 0;
}
// 使用acwing模板二刷
#include <bits/stdc++.h>
using namespace std;const int N = 1005; // 定义矩阵最大尺寸
int n, m; // n: 矩阵大小，m: 操作次数
int a[N][N]; // 原始矩阵（实际未使用）
int b[N][N]; // 二维差分数组/*** 二维差分数组的插入操作* @param x1 矩形区域左上角x坐标* @param y1 矩形区域左上角y坐标* @param x2 矩形区域右下角x坐标* @param y2 矩形区域右下角y坐标* @param c 要增加的数值*/
void insert(int x1, int y1, int x2, int y2, int c)
{b[x1][y1] += c; // 左上角+1b[x2 + 1][y1] -= c; // 左下角外侧-1b[x1][y2 + 1] -= c; // 右上角外侧-1b[x2 + 1][y2 + 1] += c; // 右下角外侧外侧+1（补偿）
}int main()
{// 输入矩阵大小和操作次数cin >> n >> m;// 处理每个矩形区域操作while (m--){int x1, y1, x2, y2;cin >> x1 >> y1 >> x2 >> y2;insert(x1, y1, x2, y2, 1); // 对指定区域+1}// 计算二维前缀和，还原最终矩阵for (int i = 1; i <= n; i++){for (int j = 1; j <= n; 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 <= n; j++){cout << b[i][j] << " ";}cout << endl;}return 0;
}
【运行结果】
5 3
2 2 3 3
3 3 5 5
1 2 1 4
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