首页 > 代码库 > poj 2528 Mayor's posters
poj 2528 Mayor's posters
这个题意是市长竞选,然后每个人都可以贴广告牌。可以覆盖别人的看最后剩几个广告牌
这题目想了两个多小时,最后忍不住看了一下题解。发现只是简单地hash 和线段树成段更新
因为有10000个人竞选,所以最多是10000个区间。20000个点,线段树就不会爆内存了;
具体操作有两个:
(1)哈希之后把每个区间端点当做底层节点,并且只要是把这个节点染色之后就是把这两个节点之中的全染色了
(2)简单地线段树更新
详情请见代码:
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; #define maxx 20010 #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 int sum[maxx<<2];//建树 int num[maxx<<1]; int cnt; int hash[maxx<<1]; int a[maxx],b[maxx]; void pushup(int rt)//更新节点,把此节点的颜色传递下去,然后此节点就可以初始化掉,表示此节点中不止有一张海报
{ if(sum[rt]!=-1){ sum[rt<<1]=sum[rt<<1|1]=sum[rt]; sum[rt]=-1; } } void update(int L,int R ,int c,int l,int r,int rt){ if(L<=l&&R>=r){ sum[rt]=c; return ; } pushup(rt); int m=(l+r)>>1; if(L<=m) update(L,R,c,lson); if(R>m) update(L,R,c,rson); } void query(int l,int r,int rt){ if(sum[rt]!=-1)//表示不只有一张海报
{ if(!hash[sum[rt]]) cnt++; hash[sum[rt]]=1; return ; } if(l==r) return ; int m=(l+r)>>1; query(lson); query(rson); } int cheak(int aa,int nn,int num[])//判断这个点在那边
{ int l=0,r=nn-1; while(l<=r){ int m=(l+r)>>1; if(num[m]==aa) return m; if(num[m]<aa) l=m+1; else r=m; } return -1; } int main(){ int T,n; scanf("%d",&T); while(T--){ scanf("%d",&n); int m=0; for(int i=0;i<n;i++){ scanf("%d%d",&a[i],&b[i]); num[m++]=a[i]; num[m++]=b[i]; } sort(num,num+m); // for(int i=0;i<m;i++) // printf("%d %d\n",i,num[i]); int h=1; for(int i=1;i<m;i++){ if(num[i]!=num[i-1]) num[h++]=num[i]; } //puts("--------------"); // for(int i=0;i<h;i++) // printf("%d %d\n",i,num[i]); memset(sum,-1,sizeof(sum)); memset(hash,0,sizeof(hash)); for(int i=0;i<n;i++){ int l=cheak(a[i],h,num); int r=cheak(b[i],h,num); update(l,r,i,0,h,1); } cnt=0; query(0,h,1); printf("%d\n",cnt); } }
poj 2528 Mayor's posters
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。