线段树是一种二叉树的拓展,在线段树每个节点中,存储的是一个区间范围。对于每个节点,它的数据结构一般有,left,right,*lch,*rch,分别描述的是区间的左端点,区间的右端点,指向左子树的指针,指向右子树的指针。对于一个节点的左子树,它的区间范围是[left,(left+right)/2],对于一个节点的右子树,它的区间范围是[(left+right)/2,right]。
利用线段树可以解决很多问题,染色问题就是其中一类,zoj_1610
#include<iostream> #include<cstdio> #include<string.h> using namespace std; int res[8010]; int nc; int n,s,e,c; class node { public: int left,right; node* lch; node* rch; int color;//>=0 singal -1:uncolored -2:muti-colored node(int start,int end) { this->left=start; this->right=end; this->lch=NULL; this->rch=NULL; this->color=-1; } void creatTree(node*root) { int end=root->right; int start=root->left; if(end-start>1) { node* lt=new node(start,(start+end)/2); node* rt=new node((start+end)/2,end); root->lch=lt; root->rch=rt; creatTree(lt); creatTree(rt); } } void insert(node*root,int start,int end,int color) { if((start==root->left&&end==root->right)||color==root->color) { root->color=color; return; } if(root->color>=0) { root->lch->color=root->color; root->rch->color=root->color; } root->color=-2; int mid=(root->left+root->right)/2; if(end<=mid) { insert(root->lch,start,end,color); } else if(start>=mid) { insert(root->rch,start,end,color); } else { insert(root->lch,start,mid,color); insert(root->rch,mid,end,color); } } void count(node*root) { if(root->color>=0&&nc!=root->color) { nc=root->color; ++res[nc]; } else if(root->color==-2) { count(root->lch); count(root->rch); } else { nc=root->color; } } }; node* createTree(int start,int end) { node* tmp=new node(start,end); if(end-start>1) { tmp->lch=createTree(start,(start+end)/2); tmp->rch=createTree((start+end)/2,end); } return tmp; } /*int average(int a,int b) { int r=(a&b)+((a^b)>>1); cout<<r<<endl; }*/ int main() { freopen("e:\\zoj\\zoj_1610.txt","r",stdin); while(cin>>n) { //node* tree=createTree(0,8010); node*tree=new node(0,8010); tree->creatTree(tree); memset(res,0,sizeof(res)); nc=-1; while(n--) { scanf("%d%d%d",&s,&e,&c); tree->insert(tree,s,e,c); } tree->count(tree); for(int i=0;i<8010;i++) if(res[i]) printf("%d %d\n",i,res[i]); printf("\n"); } return 0; }
发表评论
-
图的割点tarjan---zoj_1119
2011-10-24 23:00 1232http://acm.zju.edu.cn/on ... -
BFS与双向BFS---zoj_1505
2011-10-09 17:14 1642http://acm.zju.edu.c ... -
静态treap+线段树---zoj_2112
2011-09-29 23:06 1708http://acm.zju.edu ... -
NIM博弈游戏,SG函数---zoj_3084,zoj_2083
2011-09-23 23:00 1316Nim游戏是两个人进行的游戏有如下规则: ... -
多重背包--zoj_2156
2011-09-14 11:10 864首先介绍经典的三种背包问题,0-1背包,完全 ... -
模式串匹配---KMP
2011-08-31 20:49 1277朴素的的模式串匹配算法通常要在向前移动文本指针 ... -
八数码问题(A*&&双向BFS)---zoj_1217
2011-08-30 22:13 1665题目地址:http://acm.zju.edu.cn/onli ... -
ac自动机以及它上面的DFA
2011-08-08 23:04 2479AC自动机(Aho-Corasick)主要用 ... -
二分图最大匹配(匈牙利算法)--zoj1516,1525,2223
2011-07-20 22:36 1186二分图G(E,V)将点集合V分成两个部分L,R ... -
网络最大流(EK)---zoj_1734
2011-07-19 16:34 2130网络最大流是图论中的一个典型问题,为了精确的定 ... -
trie和前缀检查---zoj_2876
2011-07-13 23:03 866trie树是一种多叉树,广泛用于字典检索。如 ... -
位图bitmap
2011-07-13 21:08 914bitmap是一种广泛使用的数据结构,主要用在 ... -
LAC和RMQ的转化---zoj_3195
2011-07-12 22:35 1072我擦。。纠结了好久啊,从SF到TLE,先总结2 ... -
LAC的tarjan(离线)算法---zoj_1141
2011-07-08 17:52 1658LCA就不解释了,这里主要再次复习一下LC ... -
笛卡尔树以及treap---zoj_2243
2011-07-07 15:52 2839zoj_2243笛卡 ... -
线段染色,矩形切割,离散化---zoj_2301,zoj_1128
2011-06-24 22:32 1364染色问题:在一维坐标轴上(最右端为M),有N ... -
快速排序(qsort)
2011-06-16 17:03 776快速排序是一种高效的非稳定排序,它的基本思路 ... -
斐波那契散列
2011-06-16 16:38 3073斐波那契散列法其实是一种特殊的乘法散列,先来看乘法 ... -
强连通分支(scc)---tarjan
2011-06-15 16:17 1283本文大量 ... -
单源最短路径SPFA---zoj3146
2011-06-09 15:25 940针对Bellman-Ford算法效率比较低 ...
相关推荐
最近在acm.zju.edu.cn上通过的题目的代码,都是比较有价值的题目
zoj吐血制作,希望大家喜欢
zoj网站中多个练习的c++解答,文件名即为题目序号。经本人测试可以使用,主要为动态规划方面的问题,希望给初学者提供帮助。
这是一份ZOJ的ACM题解,包含大多数题目的AC程序,是学习算法的好东西~
zoj在线评测系统前台和后台源代码,包括比赛用的客户端源代码
本资源是对线段树操作比较完整的操作,包括线段树的动态插入,动态删除和维护,可以查询区段的最大值,最小值,完成线段树的基本操作。
ZOJ 1055 Oh, Those Achin Feet.bfs求最短路径.
zoj4041正确题解源代码,以及运行程序
浙江大学ZOJ源码题解,按照题目类型和难易分类。
acm中zoj1002的可运行C++程序
问题:枫教授在一所大学教数学,他发现了一个函数,用于获得一个表达式的操作数的目的,函数命名op(i,e)可以描述如下:
一个非常非常非常非常实用的zoj结题代码
zoj的代码实现,很好,而且很全面,全部实现。
hdu 1166线段树
zoj_1004.cpp 求单词字母进出栈后能形成目标串的进出方案 广度优先搜索求解
ZOJ上的一些水题,4.16浙江省程序设计竞赛的题目
zoj 2536 这个不是用贪心做的
zoj上的3607Lazier Salesgirl AC代码及一些注释。贪心算法
浙大acm OJ1204,自己做的,已经AC 分享一下,若有更好的算法可以教教我
能AC 通过的c++代码,包括zoj1002,1091,1789