新网站建设服务,建筑行业网站模板,国外 设计师 网站,wordpress joomla题目描述
在 nx n 的格子上有 m 个地毯。
给出这些地毯的信息#xff0c;问每个点被多少个地毯覆盖。
输入格式
第一行#xff0c;两个正整数 n,m。意义如题所述。
接下来 m 行#xff0c;每行两个坐标 (x_1,y_1) 和 (x_2,y_2)#xff0c;代表一块地毯#xff0c;左上…题目描述
在 nx 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) 这个格子被多少个地毯覆盖。
样例 #1
样例输入 #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
提示
样例解释
覆盖第一个地毯后 覆盖第一、二个地毯后 覆盖所有地毯后 数据范围
对于 20% 的数据有 n 50m 100。
对于 100% 的数据有 n,m 1000。 第一种方法暴力做法。这道题的数据范围很小所以暴力也可以过所有样例。
代码比较简单就不多讲了。
#include iostream
#include algorithm
using namespace std;const int N 100010;
int q[N][N]; // 定义一个二维数组来记录操作结果int main()
{int n, m;cin n m; // 输入n和m分别表示矩阵的大小和操作的次数// 进行m次操作for (int i 0; i m; i){int x1, y1, x2, y2;cin x1 y1 x2 y2; // 输入操作的左上角和右下角坐标// 针对操作的区域进行累加操作for (int j x1; j x2; j){for (int k y1; k y2; k){q[j][k]; // 将区域内的每个元素增加1}}}// 输出操作后的结果for (int i 1; i n; i){for (int j 1; j n; j){cout q[i][j] ; // 输出每个位置的操作结果}cout endl;}return 0;
}第二种方法差分。
#include iostream
#include algorithm
using namespace std;const int N 1010;
int q[N][N]; // 定义一个二维数组来记录操作结果int main()
{int n, m;cin n m; // 输入n和m分别表示矩阵的大小和操作的次数// 进行m次操作for (int i 0; i m; i){int x1, y1, x2, y2;cin x1 y1 x2 y2; // 输入操作的左上角和右下角坐标// 更新操作for (int j x1; j x2; j){q[j][y1]; // 在该列上加1q[j][y2 1]--; // 在该列的下一行减1用于区分操作的范围}}// 根据更新操作计算每个位置的最终值for (int i 1; i n; i){for (int j 1; j n; j){q[i][j] q[i][j - 1]; // 当前位置的值等于前一列的值加上当前位置的值cout q[i][j] ; // 输出每个位置的最终结果}cout endl;}return 0;
}
