首页 > 代码库 > 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