首页 > 代码库 > [haoi2014]贴海报

[haoi2014]贴海报

Bytetown城市要进行市长竞选,所有的选民可以畅所欲言地对竞选市长的候选人发表言论。为了统一管理,城市委员会为选民准备了一个张贴海报的electoral墙。
张贴规则如下:
1.electoral墙是一个长度为N个单位的长方形,每个单位记为一个格子;
2.所有张贴的海报的高度必须与electoral墙的高度一致的;
3.每张海报以“A B”表示,即从第A个格子到第B个格子张贴海报;
4.后贴的海报可以覆盖前面已贴的海报或部分海报。
现在请你判断,张贴完所有海报后,在electoral墙上还可以看见多少张海报。

1 0<= N <= 10000000   1<=M<=1000   1<= Ai <= Bi <=10000000
所有的数据都是整数。数据之间有一个空格

 

题解:离散;

可能会出现这样的情况,两个相邻的线段正好覆盖住了一条线段的两端,且这条线段的两端离散后处于相邻的位置,就会出现中间的地方还有没被覆盖的点,但计算的时候无法算进去了;

对于这种情况,我采用的方法是用一个t数组,t[i]表示离散后的数组c[i]和c[i+1]之间的空隙的颜色;

如果仅仅上面这样处理还是会挂,我们最后统计答案的时候还需要判断一下c[i]和c[i+1]之间有没有空隙(if(c[i+1]-c[i]==1)continue;)

离散化的题目没怎么做,稍稍一道水题竟然有这么多坑,还不如交个二重循环;

蛤省众人疯狂吐槽:这题nm就能过!数据水的一B!)

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<ctime>
using namespace std;
#define up(i,j,n) for(int i=j;i<=n;i++)
#define LL long long
#define pii pair<int,int> 
#define FILE "dealing"
inline bool chkmin(int &x,int y){return x>y?(x=y,true):false;}
inline bool chkmax(int &x,int y){return x<y?(x=y,true):false;}
namespace IO{
    char buf[1<<15],*fs,*ft;
    int gc(){return (fs==ft&&((ft=(fs=buf)+fread(buf,1,1<<15,stdin)),fs==ft))?0:*fs++;}
    int read(){
        int x=0,ch=gc(),d=0;
        while(ch<0||ch>9){if(ch==-)d=1;ch=gc();}
        while(ch>=0&&ch<=9){x=(x<<1)+(x<<3)+ch-0;ch=gc();}
        return d?-x:x;
    }
}using namespace IO;
namespace OI{
    const int maxn(4010);
    int x[maxn],y[maxn],n,m,q[maxn<<2],tail=0;
    int b[20000010],f[maxn];
    bool B[20000010];
    int c[maxn],t[maxn];
    int ans=0;
    void slove(){
        m=read(),n=read();
        up(i,1,n){
            x[i]=read(),y[i]=read();
            if(!B[x[i]])q[++tail]=x[i],B[x[i]]=1;
            if(!B[y[i]])q[++tail]=y[i],B[y[i]]=1;
        }
        sort(q+1,q+tail+1);
        for(int i=1;i<=tail;i++)b[q[i]]=i;
        up(i,1,n){
            up(j,b[x[i]],b[y[i]])c[j]=i;
            up(j,b[x[i]],(b[y[i]]-1))t[j]=i;
        }
        for(int i=1;i<=tail;i++)if(!f[c[i]]&&c[i])ans++,f[c[i]]=1;
        for(int i=1;i<tail;i++)if(!f[t[i]]&&t[i]&&q[i+1]-q[i]>1)ans++,f[t[i]]=1;
        printf("%d\n",ans);
    }
}
int main(){
    //freopen(FILE".in","r",stdin);
    //freopen(FILE".out","w",stdout);
    using namespace OI;
    slove();
    return 0;
}

 

[haoi2014]贴海报