本文主要是介绍HDU--1556 -- Color the ball [树状数组] [线段树]，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Color the ball
Time Limit: 9000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 5864 Accepted Submission(s): 3122
当N = 0，输入结束。
3 1 1 2 2 3 3 3 1 1 1 2 1 3 0
1 1 1 3 2 1
Code:
这一题真难为本姐姐啊
早上徒弟问我的时候顺便给了别人正确的代码,如下
按照树状数组去理解, 总觉得和树状数组有些不一样,原来是变形了==,晕
/*
这题是插段求点。有点变化但是是一样的。
插线段的话就在线段左端点加1，在右端点后面减一。
这样求和得到的就是这个点的染色次数了。
*/
#include<stdio.h>
#include<iostream>
#include<string.h>
using namespace std;
const int MAXN=100010;
int c[MAXN];
int n;
int lowbit(int x)//求最小幂,即x的最大的能用2的n次方表示的因子
{
return x&(-x);
}
void add(int i,int val)//更新数据,将含有该元素的后面的每一位都更新
{
while(i<=n)
{
c[i]+=val;
i+=lowbit(i);
}
}
int sum(int i)
{
int s=0;
while(i>0) //该位运算后,跳到前面-lowbit的地方,因为从这以后的元素和存在该位上
{
s+=c[i];
i-=lowbit(i);
}
return s;
}
int main()
{
int a,b;
while(scanf("%d",&n),n)
{
memset(c,0,sizeof(c));
for(int i=0;i<n;i++)
{
scanf("%d%d",&a,&b);
add(a,1); //插线段法
add(b+1,-1);
}
for(int i=1;i<n;i++)//按格式输出
printf("%d ",sum(i));
printf("%d\n",sum(n));
}
return 0;
}
后来用了线段树解题
虽说代码比较长吧,思想还是有利于进步的
在这个这个线段树中,如果找到一个和输入范围相同的区间,次数value就++, 即使下面有子树也不用赋值
最后只要将各个子树和各个层的双亲相加,就得到了总染色次数
前几次数组分配太小了,,郁闷!
后来输出次数的时候用的是找到最后一个叶子节点的数组下标, 一直-- ,直到减到最开始一个叶子节点为止
但是! 有一种情况是叶子结点可能在一个双亲结点和一个叶子结点之间,比如说n=6时, 姐姐我加上各种条件判断, 均不对啊
无奈只好采用类似于中序遍历的方法替代之, 从根节点开始把每层父亲结点的值都累加在一起,加到最后就是叶子结点的值, 一点不同就是父亲节点不用输出
OK, 今天一天全都荒废
#include"stdio.h"
#include"string.h"
int n;
typedef struct interval_tree_node
{
int value;
int lside,rside;
}interval_tree_node;
interval_tree_node tree[400010];
void tree_build(int n,int left,int right)//建立一个叶子节点为n的线段树
{
tree[n].lside = left;
tree[n].rside = right;
tree[n].value = 0;
if(left == right) return;
int mid = (left+right)>>1;
tree_build(n<<1,left,mid);
tree_build(n<<1|1,mid+1,right);
}
void colour(int start,int a,int b)//根据输入范围染色并计数
{
// printf("start:%d a:%d b:%d ",start,a,b);
if(tree[start].lside>=a && tree[start].rside<=b)
{
tree[start].value += 1;
// printf("final: start=%d value=%d\n",start,tree[start].value);
return;
}
int mid = (tree[start].lside+tree[start].rside)>>1;
if(b<=mid)
colour(start<<1,a,b);
else if(a>mid)
colour(start<<1|1,a,b);
else //染色范围左右子树都有
{
colour(start<<1,a,mid);
colour(start<<1|1,mid+1,b);
}
}
void forprint(int start)
{
tree[start].value += tree[start/2].value;
if(tree[start].lside==tree[start].rside)
{
printf("%d",tree[start].value);
// count--;
if(tree[start].lside!=n) printf(" ");
return;
}
// int mid = (tree[start].lside+tree[start].rside)>>1;
forprint(start<<1);
// start = start/2;
// count -= tree[start].value;
forprint(start<<1|1);
}
int main()
{
int i,a,b;
while(scanf("%d",&n),n)
{
tree_build(1,1,n);
for(i=0;i<n;i++)
{
scanf("%d%d",&a,&b);
colour(1,a,b);
}
forprint(1);
printf("\n");
}
return 0;
}这篇关于HDU--1556 -- Color the ball [树状数组] [线段树]的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
