原题链接:MJUPC-006_D.铺水泥
D.铺水泥
题目背景
某一天,小郭成为了人上人——包工头。这天,小郭给了打工人小马一张图纸,要求小马在给定的区域中铺水泥。不仅如此,还要求小马算出每个位置铺了多少次水泥。
题目描述
小郭的图纸中有 n × n n\times n n×n 个方格 , 又给了 m m m 块矩形区域。
问每个方格被铺了多少次水泥。
输入格式
第一行,两个正整数 n , m n,m n,m。
之后的 m m m 行,分别输入两个坐标 ( x 1 , y 1 ) (x_1,y_1) (x1,y1) 和 ( x 2 , y 2 ) (x_2,y_2) (x2,y2),代表这片区域被铺了一次的水泥地。其中,左上角是 ( x 1 , y 1 ) (x_1,y_1) (x1,y1),右下角是 ( x 2 , y 2 ) (x_2,y_2) (x2,y2)。
输出格式
输出 n n n 行,每行 n n n 个正整数。
第 i i i 行第 j j j 列的正整数表示 ( i , j ) (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 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 第一、二次铺水泥后:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 1 1 1 2 2 2 1 1 1 1 1 1 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 覆盖所有水泥后:
0 0 0 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 1 1 1 2 2 2 1 1 1 1 1 1 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1
数据范围
对于 20 % 20\% 20% 的数据,有 n ≤ 50 n\le 50 n≤50, m ≤ 100 m\le 100 m≤100。
对于 100 % 100\% 100% 的数据,有 n , m ≤ 1000 n,m\le 1000 n,m≤1000。
【出题人】
题目解析:
题意即给你一个矩阵,求出矩阵每个格子被铺水泥的次数。本题有两种解法。
第一种:暴力
本题降低了难度,判定的数据比较小,可以用暴力的做法求解。即先建立一个二维数组 t t t ,来记录被铺的次数,再遍历一遍给的 n n n 行,每次将每个格子加 1 1 1 即可,最后输出二维数组 t t t 。
AC代码(C++):
#include<iostream>
using namespace std;
int t[1005][1005];
int main()
{
int n, m, x1, x2, y1, y2;
cin >> n >> m;
for (int k = 1; k <= m; ++k)
{
cin >> x1 >> y1 >> x2 >> y2;
for (int i = x1; i <= x2; ++i)
for (int j = y1; j <= y2; ++j)
++t[i][j];
}//暴力模拟
for (int i = 1; i <= n; ++i)
{
for (int j = 1; j <= n; ++j)
cout << t[i][j] << ' ';
cout << endl;
}
}
第二种(推荐做法):差分&前缀和
假设 n n n 达到 105 甚至更大,暴力最坏的情况就是103 *103 * 105 ,达到惊人的 1011 ,复杂度为 O(m2n) ,必然超时。因此,我们需要更简便的方法解决它,这就是差分&前缀和。
前缀和,用于解决区间累加及查询问题。差分,是前缀和的逆运算,用于对数组进行快速多次的批量运算。本题可以搭配这两种算法解决问题。
差分&前缀和是重要的基础算法,它的复杂度只有 O(m*n),较为高效地解决了这类问题,详细请看:前缀和&差分 详解、总结及例题。
除此之外,你问我还有没有更高效的?当然有!如果你数据结构和算法基础好的话,可以去了解一下二维树状数组和二维线段树,复杂度更低!
AC代码(C++):
#include<iostream>
using namespace std;
int a[1005][1005] = { 0 }, d[1005][1005] = { 0 };
int main() {
int n, m, x1, x2, y1, y2;
cin >> n >> m;
for (int i = 1; i <= m; i++) {
cin >> x1 >> y1 >> x2 >> y2;
d[x1][y1] += 1, d[x2 + 1][y1] -= 1, d[x1][y2 + 1] -= 1, d[x2 + 1][y2 + 1] += 1;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
a[i][j] += d[i][j] + a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1];
cout << a[i][j] << " ";
}
cout << endl;
}
return 0;
}