首页 > ACM题库 > HDU-杭电 > HDU 1556 Color the ball-线段树-[解题报告] C++
2013
12-12

HDU 1556 Color the ball-线段树-[解题报告] C++

Color the ball

问题描述 :

N个气球排成一排,从左到右依次编号为1,2,3….N.每次给定2个整数a b(a <= b),lele便为骑上他的“小飞鸽"牌电动车从气球a开始到气球b依次给每个气球涂一次颜色。但是N次以后lele已经忘记了第I个气球已经涂过几次颜色了,你能帮他算出每个气球被涂过几次颜色吗?

输入:

每个测试实例第一行为一个整数N,(N <= 100000).接下来的N行,每行包括2个整数a b(1 <= a <= b <= N)。
当N = 0,输入结束。

输出:

每个测试实例输出一行,包括N个整数,第I个数代表第I个气球总共被涂色的次数。

样例输入:

3
1 1
2 2
3 3
3
1 1
1 2
1 3
0

样例输出:

1 1 1
3 2 1

本题也可用线段树过,但代码麻烦得多。题意就不用说了,直接上代码吧。

#include <stdio.h>
 #include <string.h>
 #define lowbit(x) ((x)&(-x))
 int a[100005],n;
 void update(int x,int y)
 {
     while(x <= n)
     {
         a[x] += y;
         x += lowbit(x);
     }
 }
 int getsum(int x)
 {
     int ans = 0;
     while(x > 0)
     {
         ans += a[x];
         x -= lowbit(x);
     }
     return ans;
 }
 int main()
 {
     int i,j;
     while(scanf("%d",&n) == 1 && n)
     {
         memset(a,0,sizeof(a));
         for(j = 1;j <= n;j ++)
         {
             int a,b;
             scanf("%d %d",&a,&b);
             update(a,1);
             update(b+1,-1);
         }
         printf("%d",getsum(1));
         for(i = 2;i <= n;i ++)
             printf(" %d",getsum(i));
         puts("");
     }
     return 0;
 }

这道题也可直接用数组过,新学到一种方法。

更新点的时候起点坐标开始是1,结束坐标后一位是-1,然后叠加的每个点的次数。

#include <stdio.h>
 int a[100005];
 int main()
 {
     int i,n,p,q,s;
     while(scanf("%d",&n)==1 && n)
     {
         for(i = 1;i <= n;i ++)
             a[i] = 0;
         for(i = 1;i <= n;i ++)
         {
             scanf("%d %d",&p,&q);
             a[p] ++;
             a[q+1] --;
         }
         printf("%d",a[1]);
         s = a[1];
         for(i = 2;i <= n;i ++)
         {
             s += a[i];
             printf(" %d",s);
         }
         puts("");
     }
     return 0;
 }

解题报告转自:http://www.cnblogs.com/zhangteng512/archive/2011/09/27/2193313.html


  1. 第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。

  2. 可以根据二叉排序树的定义进行严格的排序树创建和后序遍历操作。如果形成的排序树相同,其树的前、中、后序遍历是相同的,但在此处不能使用中序遍历,因为,中序遍历的结果就是排序的结果。经在九度测试,运行时间90ms,比楼主的要快。

  3. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮

  4. 很高兴你会喜欢这个网站。目前还没有一个开发团队,网站是我一个人在维护,都是用的开源系统,也没有太多需要开发的部分,主要是内容整理。非常感谢你的关注。

  5. 算法是程序的灵魂,算法分简单和复杂,如果不搞大数据类,程序员了解一下简单点的算法也是可以的,但是会算法的一定要会编程才行,程序员不一定要会算法,利于自己项目需要的可以简单了解。

  6. 学算法中的数据结构学到一定程度会乐此不疲的,比如其中的2-3树,类似的红黑树,我甚至可以自己写个逻辑文件系统结构来。

  7. Gucci New Fall Arrivals

    This is really nice to know. I hope it will be successful in the future. Good job on this and keep up the good work.

  8. 5.1处,反了;“上一个操作符的优先级比操作符ch的优先级大,或栈是空的就入栈。”如代码所述,应为“上一个操作符的优先级比操作符ch的优先级小,或栈是空的就入栈。”