地毯（暴力+差分两种方法）-Toy模板网

这篇具有很好参考价值的文章主要介绍了地毯（暴力+差分两种方法）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题目描述

在 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

提示

样例解释

覆盖第一个地毯后：

地毯（暴力+差分两种方法）,c++,c语言

覆盖第一、二个地毯后：

地毯（暴力+差分两种方法）,c++,c语言

覆盖所有地毯后：

地毯（暴力+差分两种方法）,c++,c语言

数据范围

对于 20% 的数据，有 n<= 50，m<= 100。

对于 100% 的数据，有 n,m<= 1000。

第一种方法：暴力做法。这道题的数据范围很小，所以暴力也可以过所有样例。

代码比较简单就不多讲了。文章来源地址https://www.toymoban.com/news/detail-653408.html

#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]++;       // 在该列上加1
            q[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;
}

到了这里，关于地毯（暴力+差分两种方法）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！