Count the Colors ZOJ - 1610

Count the Colors ZOJ - 1610

题意是求 把所有海报(实际是涂颜色 这里用海报代替)贴墙上 每种海报有不同的颜色 看最后每种颜色的海报有多少个独立区间

大致思路是把海报按正常顺序一张一张贴上去 每次普通区间更新 再对每个叶节点(每个小区间段)查询即可

注意这里的区间段的含义 如下所示

0---------------------------------------4

0-----------------2 2------------------4

0-------1 1------2 2 ------3 3---------4

这里每个叶节点不再是单独一个数 而是两个相邻数组成的一个区间

在代码中体现为

int m;

if(l+1==r) return;

m=(l+r)/2;

build(l,m);

build(m,r);

其实让每个叶节点代表一个左闭右开的区间也是可以的 回头尝试一下

这个题一开始理解错题意 以为求每种颜色露出的面积之和 还是太心急 没看清题意就乱搞

自己总是这样 比赛就憨着急 不动脑子不仔细想就xjb写 很多会做的也出不了 这是病 得治

#include struct node{ int xl; int xr; int col; int laz;};struct node poster[8001];struct node wall[32001];int ans[8001];int n,pre;void build(int l,int r,int cur);void pushdown(int cur);void update(int xl,int xr,int col,int cur);void safari(int cur);int main(){ int i,a,b,c; while(scanf("%d",&n)!=EOF) { build(0,8000,1); for(i=1;i<=n;i++) { scanf("%d%d%d",&poster[i].xl,&poster[i].xr,&poster[i].col); } for(i=0;i<=8000;i++) { ans[i]=0; } for(i=1;i<=n;i++) { update(poster[i].xl,poster[i].xr,poster[i].col,1); } pre=-1; pushdown(1); safari(1); for(i=0;i<=8000;i++) { if(ans[i]>0) { printf("%d %d\n",i,ans[i]); } } printf("\n"); } return 0;}void build(int l,int r,int cur){ int m; wall[cur].xl=l; wall[cur].xr=r; wall[cur].col=-1; wall[cur].laz=0; if(l+1==r) return; m=(l+r)/2; build(l,m,cur*2); build(m,r,cur*2+1); return;}void pushdown(int cur){ if(wall[cur].laz==1) { wall[cur*2].col=wall[cur].col; wall[cur*2].laz=1; wall[cur*2+1].col=wall[cur].col; wall[cur*2+1].laz=1; wall[cur].laz=0; } return;}void update(int xl,int xr,int col,int cur){ if(wall[cur].xl==xl&&wall[cur].xr==xr) { wall[cur].col=col; wall[cur].laz=1; return; } if(wall[cur].xl+1==wall[cur].xr) return; pushdown(cur); if(xr<=wall[cur*2].xr) { update(xl,xr,col,cur*2); } else if(xl>=wall[cur*2+1].xl) { update(xl,xr,col,cur*2+1); } else { update(xl,wall[cur*2].xr,col,cur*2); update(wall[cur*2+1].xl,xr,col,cur*2+1); } return;}void safari(int cur){ if(wall[cur].xl+1==wall[cur].xr) { /* if(wall[cur].xr<=10) { printf("%d %d %d\n",wall[cur].xl,wall[cur].xr,wall[cur].col); } */ if(pre!=wall[cur].col) { if(wall[cur].col>=0) { ans[wall[cur].col]++; pre=wall[cur].col; } else { pre=-1; } } return; } pushdown(cur); safari(cur*2); safari(cur*2+1); return;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。