题解 P3740 【[HAOI2014]贴海报】

nju_zdd · 2019-09-21 21:15:28 · 题解

不太敢相信这是一道绿题。。。

各位大佬的题解都太正确了，我就给一篇最暴力的吧！

1. 海报用k表示，每次新的一张则通过k++来区别。

2. 在[a,b]的区间内，给每一个t[i]都赋值为新的k（原有值的覆盖掉）。

3. 判断[1,n]是否全被覆盖。是则令w=0，否则w=1。（最后要减掉w）。

4. 如果有不同的海报露出来（即g[i]有不同的值出现），sum++（计数）。

5. sum-w即为答案。

本以为是一道线段树，结果被骗了。

#include<bits/stdc++.h>
#define maxn 10000009
using namespace std;
long long int n,m,sum,w,k;
int t[maxn],g[maxn];

template<typename T>
void read(T &x){
    x=0;int f=1;char ch=getchar();
    while(ch>'9'||ch<'0'){
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=x*10+ch-'0';
        ch=getchar();
    }
    x*=f;
}
int main(){
    read(n),read(m);
    for (int i=1;i<=m;i++){
        int a,b;
        read(a),read(b);
        k++;//更新k。
        for (int j=a;j<=b;j++)
            t[j]=k;//在[a,b]的区间内，给每一个t[i]都赋值为新的k（原有值的覆盖掉）。

    }
    for (int i=1;i<=n;i++){
        if(t[i]==0){
            w=1;break;//判断[1,n]是否全被覆盖。是则令w=0，否则w=1。（最后要减掉w）。
        }
    }
    for (int i=1;i<=n;i++){
        if(g[t[i]]==0){
            sum++;g[t[i]]=1;//如果有不同的海报露出来（即g[i]有不同的值出现），sum++（计数）。
        }
    }
    cout<<sum-w;//sum-w即为答案。
    return 0;
}