POJ 2777(Count Color) 经典染色问题

spoiler posted @ 2011年4月12日 03:06 in ACM经典题目之线段树 , 2165 阅读

题目大意:就是给出两种指令操作,
1. "C A B C" Color the board from segment A to segment B with color C.
2. "P A B" Output the number of different colors painted between segment A and segment B (including).

题目分析:首先建树,树节点有三个域,分别为左右端点r,l,与代表颜色的color。首先声明,当color等于0的时候表示被多种颜色覆盖了。

更新:首先如果在查找的过程中遇到当前区间的颜色大于0,也就是说这个区间已经被完全染色过,那么就把这个区间的颜色值往下传递,然后把这个区间的颜色值color赋值为0,继续往下查找,也就是常规的三种情况:左子树,右子树,或者左右子树混合的

直到当前区间的跟我的所要更新的区间吻合,停止往下更新!进行染色,也就是把color值附给他,还有一种情况就是:当前区间的color值大于0并且等于我所要染色的颜色值,这样也可以停止往下更新!

计数:在往下计数的时候,如果遇到color值大于0的直接把他在hash[]表里的映射赋值为1,这样防止重复计数!如果color==0;就继续往下计数。又是常规的三种情况!

源程序+部分注释:

#include<iostream>
#include<string.h>
#include<algorithm>
#include<stdio.h>
using namespace std;

struct node{
	int a,b,color;
}s[400000];
int h[60];
int Build(int x,int y,int num){
	s[num].a=x;	s[num].b=y;
	s[num].color=1;
	if(x==y)
		return 0;
	else{
		Build(x,(x+y)/2,num+num);
		Build((x+y)/2+1,y,num+num+1);
	}
}

int modify(int x,int y,int num,int color){
	if(x==s[num].a&&y==s[num].b){
		s[num].color=color;
		return 0;
	}
	if(s[num].color==color)
		return 0;
	if(s[num].color>0){
		s[num+num].color=s[num+num+1].color=s[num].color;
		s[num].color=0;
	}	
	if(y<=(s[num].a+s[num].b)/2)
		modify(x,y,num+num,color);
	else if(x>(s[num].a+s[num].b)/2)
		modify(x,y,num+num+1,color);
	else{
		modify(x,(s[num].a+s[num].b)/2,num+num,color);
		modify((s[num].a+s[num].b)/2+1,y,num+num+1,color);
	}
}

int getsum(int x,int y,int num){
	if(s[num].color>0){
		h[s[num].color]=1;
		return 0;
	}
	else{
		if(y<=(s[num].a+s[num].b)/2)
			getsum(x,y,num+num);
		else if(x>(s[num].a+s[num].b)/2)
			getsum(x,y,num+num+1);
		else{
			getsum(x,(s[num].a+s[num].b)/2,num+num);
			getsum((s[num].a+s[num].b)/2+1,y,num+num+1);
		}
	}
}

int main(){
	int l,t,cas,i,j,sum;
	int x,y,color;
	char c;
	scanf("%d %d %d",&l,&t,&cas);
		memset(h,0,sizeof(h));
		Build(1,l,1);
		for(j=1;j<=cas;j++){
			sum=0;
			cin>>c;
			if('P'==c){
				scanf("%d %d",&x,&y);
				getsum(x,y,1);
				for(i=1;i<=t;i++)
					cout<<h[i];
				cout<<endl;
				for(i=1;i<=t;i++)
					sum+=h[i];
				printf("%d\n",sum);
				memset(h,0,sizeof(h));
			}
			else if('C'==c){
				scanf("%d %d %d",&x,&y,&color);
				modify(x,y,1,color);
			}
		}
	return 0;
}

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter