首页 > 代码库 > [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]贴海报
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。