链接:
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1610
题目大意:
在一条长度为8000的线段上染色,每次把区间[a,b]染成c颜色。显然,后面染上去的颜色会覆盖掉之前的颜色。
求染完之后,每个颜色在线段上有多少个间断的区间。
分析与总结:
这题是成段更新lazy标记的题,并不算难,但是因为一些原因一直让我过不去。。。
1. 昨天做了这题,但是一直连样例都出不来 = =~!早上起来,突然醒悟发现了问题所在,题目每次给的染色段是把[a,b]染成c,之前一直以为就是把a~b的所有点都染成c, 其实不是这样的,要染色的不是点,而是区间,例如要染[0,1],并不是把0,1两点染色,而是把[0,1]这一个单位区间进行染色。 假设有一个样例:
1 2 1
3 4 1
那么这个样例应该输出1 2. 只需要在纸上画一下就可以发现,区间【2,3】是没有被染色的,所以有两个间断的区间颜色是1。
解决这个问题的办法是,建立线段树build(1,1,8000),代表区间1~8000, 然后更新时是update(1,1,8000, a+1,b,c);
2. 由于没有仔细看题目,看错了一个地方,于是一直RE(在zoj上叫做Segmentation Fault):
The first line of each data set contains exactly one integer n, 1 <= n <= 8000, equal to the number of colored segments.
这句话的意思是只有n条线段被染色,而我一直理解成了是在一条n个单位区间长度的线段上染色 = =~ 于是就悲剧了。
正解是这句话:All the numbers are in the range [0, 8000], and they are all integers.
代码:
#include<iostream>
#include<cstdio>
#include<cstring>
#define mem(str,x) memset(str,(x),sizeof(str))
#define FOR(i,s,t) for(int i=(s); i<(t); ++i)
#define FF(i,n) for(int i=0; i<(n); ++i)
#define mid ((left+right)>>1)
#define len (right-left+1)
#define lson rt<<1, left, m
#define rson rt<<1|1, m+1, right
#define STOP puts("Stop Here~");
using namespace std;
const int MAXN = 8005;
int n,col[MAXN<<2],vis[MAXN<<2],ans[MAXN<<2];
inline void push_down(int rt){
if(col[rt] != -1){
col[rt<<1] = col[rt<<1|1] = col[rt];
col[rt] = -1;
}
}
void update(int rt,int left,int right,int l,int r,int data){
if(l<=left && right<=r){
col[rt] = data;
return;
}
if(col[rt] == data) return;
if(col[rt]!=-1)push_down(rt);
int m = mid;
if(l <= m)update(lson,l,r,data);
if(r > m)update(rson,l,r,data);
}
void query(int rt,int left,int right){
if(col[rt]>=0){
for(int i=left; i<=right; ++i)
vis[i] = col[rt];
return;
}
if(left!=right && col[rt] == -1){
int m = mid;
query(lson);
query(rson);
}
}
int main(){
int a,b,c;
while(~scanf("%d",&n)){
memset(col,-1,sizeof(col));
for(int i=0; i<n; ++i){
scanf("%d%d%d",&a,&b,&c);
if(a>=b)continue;
update(1,1,8000,a+1,b,c);
}
mem(vis,-1);
query(1,1,8000);
int i = 1;
mem(ans,0);
while(i<MAXN){
int color=vis[i], j=i+1;
if(color==-1){++i; continue;}
while(vis[j]!=-1 && vis[j]==color && j<MAXN) ++j;
++ans[color];
i=j;
}
for(int i=0; i<MAXN; ++i)if(ans[i])
printf("%d %d\n",i,ans[i]);
puts("");
}
return 0;
}
—— 生命的意义,在于赋予它意义士。
原创http://blog.csdn.net/shuangde800,By
D_Double (转载请标明)
分享到:
相关推荐
zoj 1610 Count the Colors.md
本资源是对线段树操作比较完整的操作,包括线段树的动态插入,动态删除和维护,可以查询区段的最大值,最小值,完成线段树的基本操作。
zoj 1610 线段覆盖 poj 2777 线段覆盖 poj 2528 需要离散化,建树不同,需要处理不同->注意这组数据 3 1 10 1 3 6 10 the ans is 3. hdu 1754 求区间最大值 hdu 1166 求区间和 hdu 1698 成段更新 poj 3468 成段更新 ...
hdu 1166线段树
ZOJ解题报告ZOJ解题报告ZOJ解题报告ZOJ解题报告
zoj 1255 The Path.md
zoj题目简单归类zoj题目简单归类zoj题目简单归类
acm中zoj1002的可运行C++程序
zoj 1810 The Gourmet Club.md
zoj 2499 The Happy Worm.md
zoj 2151 The Highest Profits.md
包含了zoj700多道题目的源代码,在做题时可以参考
浙江大学2451题 用线段树思想解的,c++语言版本
Problem Arrangement zoj 3777
ZOJ题目答案源码
2416和2451测试程序原代码,编译成功,好使
一个非常非常非常非常实用的zoj结题代码
count 0; cout << "[" << endl; if s1 length s2 length BackTrake s1 s2 ; cout << "]" << endl; cout << count << endl; } return 0; }">深度...
ZOJ1805代码
学习ACM程序设计的朋友一定要看,这是训练必备的POJ ZOJ题目分类及解题思路