hdu1556--Color the ball

2024-08-25 01:32
文章标签 color ball hdu1556

本文主要是介绍hdu1556--Color the ball,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Color the ball

Time Limit: 9000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 8883 Accepted Submission(s): 4542


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

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

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

Sample Input
  
3 1 1 2 2 3 3 3 1 1 1 2 1 3 0

Sample Output
  
1 1 1 3 2 1

Author
8600

Source
HDU 2006-12 Programming Contest

Recommend
LL | We have carefully selected several similar problems for you: 1166 1542 1394 1698 1255
用数组k,k[i]表示对i到n的染色次数,求x点染色次数,将k[1]累加到k[x]
对于k数组的处理,如果输入(a,b)代表着k[a]+1 , k[b+1]-1;这样计算b以后的气球时这次的染色会被平衡掉
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;int c[100010] ;
int lowbit(int x)
{return x & -x ;
}
void add(int i,int n,int d)
{while(i <= n ){c[i] += d ;i += lowbit(i) ;}
}
int sum(int i)
{int a = 0 ;while( i ){a += c[i] ;i -= lowbit(i) ;}return a ;
}
int main()
{int i , n , a , b ;while(scanf("%d", &n) && n ){memset(c,0,sizeof(c));for(i = 0 ; i < n ; i++){scanf("%d %d", &a, &b);add(a,n,1);add(b+1,n,-1);}for(i = 1 ; i <= n ; i++){a = sum(i);if(i == n)printf("%d\n", a);elseprintf("%d ", a);}}return 0;
}


这篇关于hdu1556--Color the ball的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1104171

相关文章

三色标记(Tri-color marking)

维基百科部分 原文 https://en.wikipedia.org/wiki/Tracing_garbage_collection#TRI-COLOR Because of these performance problems, most modern tracing garbage collectors implement some variant of the tri-color ma

HDU 1556 Color the ball (树状数组-- 区间更新,单点求值)

OJ题目 :点这里~~ 与 单点更新,区间求值 稍有不同,需要理解注意。 AC_CODE int n;int num[100002];int lowbit(int x){return x&(-x);}int sum(int x){int ret = 0;while(x > 0){ret += num[x];x -= lowbit(x);}return ret;}void ad

[C++] 将LONG类型的color值转换为RGB值

转换原理: The calculation is: (65536 * Blue) + (256 * Green) + (Red) 'Convert RGB to LONG: LONG = B * 65536 + G * 256 + R       'Convert LONG to RGB:  B = LONG \ 65536  G = (LONG - B * 65536) \ 256  R =

记一次解析Pantone Color TCX 色彩码

第一次尝试解析TCX 第二次尝试解析TPG 第三次一次到位TCX&TPG ①打开潘通·中国官网 ②在找寻潘通色彩一栏输入TCX,提交 ③浏览器F12,找到搜索结果所在的div,右键copy element ④文本文档修改文件类型为js,并粘贴上一部的结果,将其赋值给str str='<div class="colorInfo" id="fashionColorDiv"><a class

ABAP OOALV 颜色COLOR设置

文章目录 行颜色、列颜色、单元格颜色设置COLOR行颜色设定实现过程运行结果 列颜色的设置实现过程运行结果 设置单元格颜色完成过程运行结果1运行结果2 行颜色、列颜色、单元格颜色设置COLOR 行颜色设定 参考文章:https://blog.csdn.net/Leo520liang/article/details/138697189 实现过程 TYPES: BEG

poj 2154 Color(polya计数 + 欧拉函数优化)

http://poj.org/problem?id=2154 大致题意:由n个珠子,n种颜色,组成一个项链。要求不同的项链数目,旋转后一样的属于同一种,结果模p。 n个珠子应该有n种旋转置换,每种置换的循环个数为gcd(i,n)。如果直接枚举i,显然不行。但是我们可以缩小枚举的数目。改为枚举每个循环节的长度L,那么相应的循环节数是n/L。所以我们只需求出每个L有多少个i满足gcd(

A. Find Color

A. Find Color time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output Not so long ago as a result of combat operations the main Berl

MSRCR(Multi-Scale Retinex with Color Restore)

引言 始于Edwin Herbert Land(埃德温·赫伯特·兰德)于1971年提出的一种被称为色彩恒常的理论,并基于此理论的图像增强方法。Retinex这个词由视网膜(Retina)和大脑皮层(Cortex)合成而来.之所以这样设计,表明Land他也不清楚视觉系统的特性究竟取决于此两个生理结构中的哪一个,抑或两者都有关系。不同于传统的图像增强算法,如线性、非线性变换、图像锐化等只能增强图像

OpenCV, color reduction method

转载请注明出处!!!http://blog.csdn.net/zhonghuan1992 OpenCV, colorreduction method 目标:          这次学习的目标是回答下面的几个问题:                   1 图片像素是如何被扫描的?                    2OpenCV 矩阵值如何被存储?

python动画:颜色(color)能接受的[manim_colors]

Manim_colors指的是Manim动画引擎中全局命名空间中包含的一组颜色。这些颜色构成了Manim默认的颜色空间。通过使用manim_colors,动画师和创作者可以轻松地访问和应用各种颜色到他们的动画中,而无需单独定义它们。这个特性简化了动画制作的过程,并确保整个项目中颜色的一致性使用。manim_colors的可用性增强了使用Manim创建的动画的视觉吸引力和清晰度,使其成为动画师、教育