题解 P2692 【覆盖】

· · 题解

我又来水题解啦！

不会的道友们跟我来！

STEP 1 审题

  1. 有一张图，知道长宽

  2. 竖着填充b列，横着填充g列

  3. 问有多少格未填充

是不是看着很简单，想直接动手暴力了呢？但是理智告诉我们，不优化就意味着——TLE

STEP 2 优化方法

那么问题来了，怎么优化呢？

dalao们不要回答什么若干高级算法，对于一道橙题和想做这道橙题的包括我在内的蒟蒻来说，有些复杂了。

所以我们考虑能否在处理方面做一些小优化：

我们可以设立一个数组，专门记录每一行的占用情况，好处有：

  1. 我们在最后处理每一格是否被占用的时候可以只处理单从行来看没有被占用的格子；

  2. 再处理女生覆盖列的时候，只需要覆盖行没有被占用的各自即可

当然，说了这么多，不会实现也是没有用的，下面将为大家展示代码实现以及完整注释

STEP 3 AC代码及完整注释QAQ

#include<bits/stdc++.h>//万能头小宝贝
using namespace std;
int n,m,b,g,ma[5001][5001],x,y,ans;
//分别储存行列数，覆盖行列数，整张地图，暂时用来储存的两个变量，以及答案
bool h[5001]; //储存每一行的占用情况
int main(){
    scanf("%d %d %d %d",&n,&m,&b,&g);//正常输入
    for (int i=1;i<=b;i++){
        scanf("%d %d",&x,&y);
        for (int j=x;j<=y;j++) h[j]=1;//每次输入男生覆盖的行的时候标记
    }
    for (int i=1;i<=g;i++){
        scanf("%d %d",&x,&y);
        for (int j=1;j<=n;j++)
            if (!h[j])
                for (int w=x;w<=y;w++)
                    ma[j][w]=1;//女生的标记每一格
    }
    for (int i=1;i<=n;i++)//循环每一行
        if (!h[i])//优化：特判
            for (int j=1;j<=m;j++)
                if (!ma[i][j])
                    ans++;//只要没被覆盖就++
    printf("%d\n",n*m-ans);//要求的是覆盖的数量，所以要拿总格子数减去覆盖的格子数
    return 0;//好习惯++
}

你，看懂了吗？

STEP 4 完结撒花！

恭喜你成功看完了本篇题解！[手动鼓掌]如果还有不懂的地方，欢迎在评论区评论哦，我会第一时间回复哒！

如果都看懂了，就点个赞纪念一下你的成长吧！