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

[haoi2014]贴海报

2024-08-18 10:30:21   221人阅读

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]贴海报


联系
我们