模拟-hdoj-4831-百度之星2014初赛第二场

Scenic Popularity

Problem Description

  临近节日,度度熊们最近计划到室外游玩公园,公园内部包括了很多的旅游景点区和休息区,由于旅游景点很热门,导致景点区和休息区都聚集了很多人。所以度度熊在旅游之前想通过百度地图查看一下公园内各个地方的热门程度。

  假设所有景点区和休息区都是X轴直线上的一系列顶点,所对应的坐标Xi 保证唯一。每个景点区有个初始的热度值,而一个休息区(坐标为Xi)的热度值等于离它距离最近的景点区Xj的热度值(距离定义为|Xi-Xj|),如果此休息区与两个景点区的距离一样,则休息区的热度值选择两个景点区中的热度值最大值,如果两个热度值都一样,则随意选择其中一个。

  度度熊在出门之前会经常去查看百度地图,每次查看前会有某些景点区的热度值已发生改变,从而也会导致周围的休息区的热度值发生改变,然后度度熊想知道当前热度值<=Rk的顶点(包括景点区和休息区)有多少个

Input

  输入数据的第一行是测试Case的个数(T<=100)。

  每个Case的第一行是N(0<N<=10000),表示景点区和休息区的总数。

  接着会有N行数据,每一列首先是顶点的X坐标Xi (0< Xi <=1e8),第二列是一个整数Hi(0=<Hi <=100000),如果Hi 不为0,则表示当前顶点为风景区且初始的热度值为Hi,否则表示当前顶点为休息区。这N行数据会按照坐标Xi递增的方式依次给出。

  接着的一行数据是操作的次数K(K<=100),最后会有K行数据,每一行的第一列要么是’U’或者’Q’,’U’表示当前操作为更改热度操作,’Q’表示当前操作为查询操作。如果是更改操作,接着会有两列数据,分别是热度值要改变的风景区的下标Lk(0<=Lk<N)以及改变后的热度值Vk(0< Vk<=100000);如果是查询操作,第二列是要查询的热度范围Rk(0< Rk<=100000)

Output

  对于第k组测试数据,第一行输出Case #k:,接下来对每次查询操作(即Q操作)会输出一个整数,表示满足条件的顶点数有多少个

Sample Input

1                                 

4                                 

10 0

20 3

30 0 

40 2

3

Q 3 

U 3 4 

Q 3

Sample Output

Case #1:

4

2

Source

2014年百度之星程序设计大赛 - 初赛(第二轮) 

树状数组貌似是考察点。我目前只会模拟,闲了再说。

 

时间: 2024-11-17 02:33:39

模拟-hdoj-4831-百度之星2014初赛第二场的相关文章

动态规划-hdoj-4832-百度之星2014初赛第二场

Chess Problem Description 小度和小良最近又迷上了下棋.棋盘一共有N行M列,我们可以把左上角的格子定为(1,1),右下角的格子定为(N,M).在他们的规则中,"王"在棋盘上的走法遵循十字路线.也就是说,如果"王"当前在(x,y)点,小度在下一步可以移动到(x+1, y), (x-1, y), (x, y+1), (x, y-1), (x+2, y), (x-2, y), (x, y+2), (x, y-2) 这八个点中的任意一个. 小度觉得每

2016&quot;百度之星&quot; - 初赛(Astar Round2B)解题报告

此文章可以使用目录功能哟↑(点击上方[+]) 被自己蠢哭,去年还能进一下复赛,今年复赛都没戏了... 链接→2016"百度之星" - 初赛(Astar Round2B)  Problem 1001 区间的价值 Accept: 0    Submit: 0 Time Limit: 10000/5000 mSec(Java/Others)    Memory Limit : 65536 KB  Problem Description  Input  Output  Sample Input

百度之星编程大赛落幕六年发掘十万计算机精英

挖贝网7月28日消息 经过两个多月的激烈角逐,2010年7月28日,由百度主办的"2010 Astar百度之星程序设计大赛"正式在京落下帷幕,来自浙江大学的杭航表现出色,从三万多名参赛的程序设计高手中脱颖而出,最终捧得"2010年百度之星"桂冠.而在其余8名二.三等奖获得者中,山东师大附中魏铭等几位高中生的身影,也成为当天比赛的一大亮点. 作为中国互联网中规模最大.最具影响力的程序开发设计赛事,"Astar百度之星程序设计大赛"自2005年创办来

2009百度之星程序设计大赛启动

中介交易 http://www.aliyun.com/zixun/aggregation/6858.html">SEO诊断 淘宝客 云主机 技术大厅 5月5日,a*star2009百度之星程序设计大赛,以"Code人心弦"为宣传口号全面启动. 据悉,从5月5日到5月29日,均可在大赛官网注册.大赛官网包含赛事规则.赛题集锦.答题指南等详细信息,选手可在此处了解最新消息,为比赛做充分准备. 整个赛事一直延续到2009年7月中旬,包括5月底的网络资格赛(初赛).6月中旬的网

2013百度之星冠军乔明达专访:我的冠军之路

硅谷网8月19日讯 从2013百度之星5月东部区域赛冠军,到2013国际信息学奥林匹克(IOI)竞赛第二名,再到2013百度之星总决赛冠军,乔明达2013年的编程之路可谓是一路畅通无阻的冠军之路.在赛后冠军采访的过程中,经常面带微笑的乔明达在镜头前稍显有一点局促,然而就是这样一位腼腆的南京外国语学校的高三学生在比赛现场赢得了最多的掌声和尊重. 在三个月前的区域赛冠军采访中,乔明达告诉我们他学编程的时间比一般人要稍早一些.小学五年级第一次接触编程时他对此一无所知,但当他发现编程是一个可以促进从无到

2012“Astar百度之星”大赛启动

近日,"Astar百度之星"编程大赛在清华大学拉开帷幕,旨在让编程爱好者们通过自己擅长的程序代码,获得"改变世界的荣耀感".据悉,本次资格赛的参赛人数将挑战全球"同时参与人数最多的在线编程"纪录,在大赛中脱颖而出的选手还将进入百度公司校园招聘"绿色通道",直接获得加盟百度的优先通行证,与世界顶级工程师共事.同时,本届Astar百度之星还将"公益编程大赛"作为辅线赛事,号召参赛者共同关注社会问题.另外,&qu

一道百度之星编程大赛题的随笔联想·(2)

百度之星,是全球最大的中文搜索引擎,百度公司面向中国高校学生和编程爱好者所举办的高水平的程序设计大赛.他所考试的题目,全部都是算法的题目. 鄙人虽然是一个.net程序员,在工作之余,喜爱算法. 我觉得这个题目有点意思,故而分享给大家,我想到两种方法,提供大家,希望对大家起了一个开阔思路的作用. 下面介绍解法二了.  解法二,是抓小放大.  由小及大.首先,说一说我分析的思路吧.  第一步,还是判断i是不小于i/2,以此循环了.  第二步,是不是判断此范围的值的累加是不是等于相应某个值. 第三步,

百度之星试题每周一练

百度之星,是全球最大的中文搜索引擎,百度公司面向中国高校学生和编程爱好者所举办的高水平的程序设计大赛.他所考试的题目,全部都是算法的题目. 鄙人虽然是一个.net程序员,在工作之余,喜爱算法. 这个问题非常的巧,故而分享给大家,我想到一种超简单方法,提供大家,希望对大家起了一个开阔思路的作用. 首先,题意是这样的: 八方块移动游戏要求从一个含 8 个数字 (用 1-8 表示) 的方块以及一个空格方块 (用 0 表示) 的 3x3 矩阵的起始状态开始,不断移动该空格方块以使其和相邻的方块互换,直至

一道百度之星编程大赛题的随笔联想·(1)

百度之星,是全球最大的中文搜索引擎,百度公司面向中国高校学生和编程爱好者所举办的高水平的程序设计大赛.他所考试的题目,全部都是算法的题目. 鄙人虽然是一个.net程序员,在工作之余,喜爱算法. 我觉得这个题目有点意思,故而分享给大家,我想到两种方法,提供大家,希望对大家起了一个开阔思路的作用. 首先,看题目是那样的: 请编写程序,根据输入的任何一个正整数,找出符合这种要求的所有连续正整数序列. 输入数据:一个正整数,以命令行参数的形式提供给程序. 输出数据:在标准输出上打印出符合题目描述的全部正