首页 > 代码库 > cogs1682. [HAOI2014]贴海报 x

cogs1682. [HAOI2014]贴海报 x

1682. [HAOI2014]贴海报

★★☆   输入文件:ha14d.in   输出文件:ha14d.out   简单对比
时间限制:1 s   内存限制:256 MB

【题目描述】

Bytetown城市要进行市长竞选,所有的选民可以畅所欲言地对竞选市长的候选人发表言论。为了统一管理,城市委员会为选民准备了一个张贴海报的electoral墙。

张贴规则如下:

1.electoral墙是一个长度为N个单位的长方形,每个单位记为一个格子;

2.所有张贴的海报的高度必须与electoral墙的高度一致的;

3.每张海报以“A B”表示,即从第A个格子到第B个格子张贴海报;

4.后贴的海报可以覆盖前面已贴的海报或部分海报。

现在请你判断,张贴完所有海报后,在electoral墙上还可以看见多少张海报。

【输入格式】

第一行:     N   M            分别表示electoral墙的长度和海报个数

接下来M行:   Ai   Bi          表示每张海报张贴的位置

 

【输出格式】

输出贴完所有海报后,在electoral墙上还可以看见的海报数。

【样例输入】

 

100 5

1 4

2 6

8 10

3 4

7 10

 

【样例输出】

4

【提示】

 

技术分享

【约束条件】

1 0<= N <= 10000000     1<=M<=1000   1<= Ai <= Bi <=10000000

所有的数据都是整数。数据之间有一个空格

 思路:

  1)首先这道题暴力可以拿80分!(在luogu上可以AC!!!!)

  2)然后考场上作死写了个并查集。。。61分

  3)正解:

      ①线段树(然而我没写~)

      ②浮水法

坑点:

  因为给出的是所位于的块,不是左右端点,所以在处理浮水法的时候记得要右端点+1,或者左端点-1

上代码:

1)暴力

#include <algorithm>#include <iostream>#include <cstring>#include <string>#include <cstdio>using namespace std; const int M = 1e7 + 1;int n,m,l,r,ans;int a[M],v[M];inline int reads(){    int x=0,f=1;char ch=getchar();    while(ch<0 || ch>9)    {if(ch==-) f=-1;ch=getchar();}    while(ch>=0 && ch<=9)    {x=10*x+ch-0;ch=getchar();}    return x*f;}int main(){    freopen("ha14d.in","r",stdin);    freopen("ha14d.out","w",stdout);    n=reads(),m=reads();    for(int i=1;i<=m;i++)    {        l=reads(),r=reads();        if(r<l) swap(l,r);        for(int j=l;j<=r;j++)            a[j]=i;    }    for(int i=1;i<=n;i++)    {        if(!v[a[i]] && a[i])        {            ans++;            v[a[i]]=1;        }    }    printf("%d",ans);    return 0;}

2)作死并查集

#include <algorithm>#include <iostream>#include <cstring>#include <string>#include <cstdio> using namespace std; inline int reads(){    int x=0,f=1;char ch=getchar();    while(ch<0 || ch>9)    {if(ch==-) f=-1;ch=getchar();}    while(ch>=0 && ch<=9)    {x=10*x+ch-0;ch=getchar();}    return x*f;} const int M = 1e7 + 2333333;                ///多开几个 const int N = 1111;int n,m;int f[M];int ans[M],anse;int Ls[N],Rs[N]; int getf(int x){return f[x] == x ? x : f[x] = getf(f[x]);} int main(){    freopen("ha14d.in","r",stdin);    freopen("ha14d.out","w",stdout);    n=reads();m=reads();                    ///n是n块,不是左右端点!!!     for(int i=1;i<=n+2;i++)        f[i]=i;    for(int i=1;i<=m;i++)                   ///m组数据     {                                       ///手动从1开始,从0不会...         Ls[i]=reads();        Rs[i]=reads()+1;                    ///因为给出不是点的坐标,是块的坐标     }    int l,r;     for(int i=m;i>=1;i--)                   ///逆序张贴,因为只需要的是最后的能看到的海报     {        l=Ls[i],r=Rs[i];                    ///左右端点         if(l>r) swap(l,r);                  ///maybe?会出现"left">"right"的情况(考虑最坏情况,以防万一,以前做过一个题就是恶心的数据!)         for(int j=getf(l);j<=r;j=getf(j+1))        {            f[getf(j)]=getf(j+1);           ///将当前被张贴报纸的父结点手动设置到最后一个的父结点 ///            ans[j]=i;            ans[i]++;             if(getf(1)==n+2) break;         ///表示已经贴完         }    }     for(int i=1;i<=n+1;i++)    {///        printf("%d=%d\n",i,ans[i]);      ///输出调试???         if(ans[i]) anse++;    }    printf("%d\n",anse);     return 0;}

3)正解(浮水法)

#include <algorithm>#include <iostream>#include <cstring>#include <cstdio>#include <cmath>using namespace std; const int M = 1001;int n,m,ans=1;bool v[M]; struct U {    int l,r,id;    //id 为第几张海报 }t[M]; inline int reads(){    int x=0,f=1;char ch=getchar();    while(ch<0 || ch>9)    {if(ch==-) f=-1;ch=getchar();}    while(ch>=0 && ch<=9)    {x=10*x+ch-0;ch=getchar();}    return x*f;} void swim(int ql,int qr,int nowid,int preid){    if(v[preid])        return;    while(nowid<=m && (qr<=t[nowid].l || ql>=t[nowid].r))        nowid++;    if(nowid>m)    {        v[preid]=true;        ans++;        return;    }    if(ql<t[nowid].l && qr>t[nowid].l)        swim(ql,t[nowid].l,nowid+1,preid);    if(ql<t[nowid].r && qr>t[nowid].r)        swim(t[nowid].r,qr,nowid+1,preid);} int main(){    freopen("ha14d.in","r",stdin);    freopen("ha14d.out","w",stdout);    n=reads();m=reads();    for(int i=1;i<=m;i++)    {        t[i].l=reads(),t[i].r=reads()+1;        t[i].id=i;    }    for(int i=m-1;i>=1;i--)        swim(t[i].l,t[i].r,i+1,i);    printf("%d",ans);    return 0;}

 

cogs1682. [HAOI2014]贴海报 x