MJUPC-006_编程挑战系列赛第六场(以代码为文,贺国庆华诞) _D.铺水泥

原题链接: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。

【出题人】

Grape_L

题目解析:

题意即给你一个矩阵,求出矩阵每个格子被铺水泥的次数。本题有两种解法。

第一种:暴力

本题降低了难度,判定的数据比较小,可以用暴力的做法求解。即先建立一个二维数组 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;
}
上一篇:Linux用户管理


下一篇:Linux用户管理2