地毯(暴力+差分两种方法)

news/2025/2/13 21:03:51/

题目描述

在 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<= 50,m<= 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;
}


http://www.ppmy.cn/news/1039284.html

相关文章

Kotlin Lambda和高阶函数

Lambda和高阶函数 本文链接&#xff1a; 文章目录 Lambda和高阶函数 lambda输出&#xff08;返回类型&#xff09;深入探究泛型 inline原理探究 高阶函数集合、泛型自己实现Kotlin内置函数 扩展函数原理companion object 原理 > 静态内部类函数式编程 lambda 1、lambda的由…

HJ3 明明的随机数

题目链接 难度&#xff1a;简单 题解&#xff1a; 题目思路&#xff1a;定义一个长度为510的数组来表示输入的每个数字是否出现过。 数组的下标表示输入的数字本身。 数组的值为1&#xff0c;表示已出现。 数组的值为0&#xff0c;表示未出现。 最后顺序遍历数组&#xff0c…

Esp8266学习7. 点亮JMD0.96C-1 OLED屏

Esp8266学习7. 点亮JMD0.96C-1 OLED屏 一、ESP32-C3 I2C资源简介1. 简介2. 准备工作 二、I2C协议简介1. 起始条件&#xff08;Start Condition&#xff09;&#xff1a;2. 设备地址传输&#xff08;Device Address Transmission&#xff09;&#xff1a;3. 从设备响应&#xff…

数据结构单链表

单链表 1 链表的概念及结构 概念&#xff1a;链表是一种物理存储结构上非连续、非顺序的存储结构&#xff0c;数据元素的逻辑顺序是通过链表中的指针链 接次序实现的 。 在我们开始讲链表之前&#xff0c;我们是写了顺序表&#xff0c;顺序表就是类似一个数组的东西&#xff0…

手撕单链表

目录 链表的概念和结构 单链表的实现 申请新结点 打印 尾插 头插 尾删 头删 ​编辑 查找 在pos位置前插入元素 在pos位置后插入元素 删除pos位置的元素 删除pos位置之后的位置的元素​编辑 完整代码 SListNode.h SListNode.c 链表的概念和结构 链表是一种物理存储…

C++新经典03--共用体、枚举类型与typedef

共用体 共用体&#xff0c;也叫联合&#xff0c;有时候需要把几种不同类型的变量存放到同一段内存单元&#xff0c;例如&#xff0c;把一个整型变量、一个字符型变量、一个字符数组放在同一个地址开始的内存单元中。这三个变量在内存中占的字节数不同&#xff0c;但它们都从同…

【Go 基础篇】Go语言基本数据类型转换:字符串、整数、浮点数、字符与布尔类型的转换

介绍 在计算机编程中&#xff0c;不同的数据类型用于表示不同种类的数据。在Go语言&#xff08;Golang&#xff09;中&#xff0c;基本数据类型包括字符串、整数、浮点数、字符和布尔类型。在实际开发中&#xff0c;经常需要进行不同数据类型之间的转换&#xff0c;以满足不同…

第九章 动态规划part10(代码随想录)

121. 买卖股票的最佳时机 1. 确定dp数组&#xff08;dp table&#xff09;以及下标的含义 用二维dp数组表示第i天的2种状态 dp[i][0] 表示第i天持有股票所得最多现金&#xff0c;可能i-1天就买股票了 dp[i][1] 表示第i天不持有股票所得最多现金 最后求&#xff1a;dp[len-1][0…