注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

fanhq666的博客

Fan-Fun

 
 
 

日志

 
 

第5天的题目  

2010-07-24 15:05:12|  分类: 程序 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

NOI 难度练习一
@北京人大附中,2010 年7 月24 日
第一题选举计票
【题目描述】
你见过一维的世界么?其实,每一根长长的数轴就是一个世界,每一个从1 开始的整数都代
表了一个城市。和我们的世界中一样,他们的世界中也有很多国家,每个国家都是由许多连
在一起的城市组成的。由于存在领土争端,所以一个城市可以属于多个国家。但是,如果一
个国家完全被另一个国家所包含,就会被吞并掉,这个国家也就不复存在了。有趣的还在后
面:他们还会定期进行选举呢!每逢选举的时候,每个城市都会给出自己所支持的领导人的
编号,每个国家里得票最多的领导人就可以当选。当然,一个很受欢迎的领导人可以同时领
导很多国家!现在,我们已经拿到了n 个城市支持的领导人编号,同时我们也收集到了每个
国家的领土范围。现在,我们关心的是,每个国家中,当选的领导人究竟得到了多少票呢?
【输入格式】
第一行是两个整数n 和m,表示城市个数和国家个数。
第二行是n 个整数,依次表示n 个城市的选票。
从第三行开始的m 行,每行包含两个整数,依次表示m 个国家的领土作为闭区间的两个端
点;输入数据保证,没有两个国家的领土完全相同。
【输出格式】
共有m 行,每行包括一个整数,表示该国家领导人得票数量。对于在选举之前已经被他国
吞并的国家,输出0。
【样例输入】
8 5
321 231 123 231 123 123 111 123
1 3
4 7
2 4
2 3
6 8
3 6
【样例输出】
1
2
2
0
2
3
【数据范围】
对于20%的数据n<=100, m<=100;
对于40%的数据n<=1000,m<=1000;
对于60%的数据n<=100000,m<=100000;
对于80%的数据n<=1000000,m<=1000000;
对于100%的数据n<=5000000,m<=5000000;
【题目来源】
原创题目
第二题水灾
【题目描述】
Flood 城市是一个多灾多难的城市。今年夏天,由于连日降雨,城市里再次大水泛滥。目前,
城里除了几个用混凝土墙围成的孤岛外,已经成为一片汪洋泽国。Flood 城市的人们相信,
用三角形堤坝可以最有效地阻挡洪水,因此这里的每三座墙组成一个三角形的堤坝,这些堤
坝围出一个区域,洪水来临的时候待在里面就能相对安全一些。在城市规划的时候,这些堤
坝不会相交,但是可以嵌套,从而对最里层的人们提供最有效的保护。现在洪水自由前进的
速度已经测得是v,洪水冲毁一座堤坝需要的时间为t0。市长想知道,城市里最安全的地方
在哪里,但是他不想大张旗鼓地做调查,于是他就找到了你,让你为他偷偷算一下,城市里
什么地方被淹没的时间最晚。(他的目的是什么呢?市长特别嘱咐,个人私事,不要关心)
当然,由于年久失修,也可能有两个堤坝相交的情况。如果出现了相交问题,你只需要告诉
市长相交的是哪两座堤坝就可以了。
下面是从科学家那里得到的一些关于洪水前进方式的信息:
1. 城里的每个位置都会在洪水到达的时刻被淹没。最外层堤坝之外的所有位置,一开始就
已经被淹没。
2. 如果一个位置已经被淹没,在t 时间之后,所有与其直线距离小于vt,且中间没有障碍
物阻挡的位置都将被淹没。(如果没有障碍物,一个淹没点会产生大小为vt 的一个淹没
圈,如果有障碍,洪水可能需要更多的时间从旁边“绕过去”)。注意:这里的时间是连
续的,洪水淹没任何点之后都会立刻继续扩散。
3. 堤坝能够坚持的时间,从洪水开始抵达堤坝的任意一点开始计算(最外层就是从一开
始)。但是,一旦一个堤坝被冲毁,整个堤坝会瞬间全部被淹没。即,洪水从堤坝四面
八方同时涌入。
(作者的话:如果在NOI 中遇到类似题目,往往会有图形帮助理解。但是把审题的工作完
全依赖于图形是不明智的,往往会降低自己对于各种特殊情况的想象力。另外,请大家做完
之后想一想,如果堤坝坚持时间从洪水完全包围堤坝开始计算应该怎么办。这个看上去更自
然的定义会增加不少题目难度,但仍然没有超出NOI 可能的难度范围)
【输入格式】
第一行是两个实数,表示洪水自由前进的速度v,和冲毁一座堤坝需要的时间t。
第二行是一个整数,表示堤坝的个数。
从第三行开始,每行包括三对共六个实数,表示每个堤坝三角形的三顶点坐标。
为了避免可能出现的精度误差引起误判,输入数据保证所有不相交的堤坝之间有一定间距。
【输出格式】
第一行是一个判断,OK 表示没有堤坝相交,FAIL 表示存在堤坝相交。
如果没有堤坝相交,之后的一行是空格分隔的两个实数(小数点后两位即可),表示最安全
的位置。否则,之后的一行是空格分隔的两个整数,表示相交的一对堤坝在输入数据中的序
号,序号从1 开始。注意,如果存在多组相交,任意输出一组即可。
【样例输入1】
1.0 2.0
2
0.0 0.0 2.0 0.0 0.0 2.0
1.0 1.0 -1.0 1.0 1.0 -1.0
【样例输出1】
FAIL
【样例输入2】
1.0 2.0
2
0.0 0.0 2.0 0.0 0.0 2.0
0.0 1.0 1.0 0.0 1.0 1.0
【样例输出2】
FAIL
【样例输入3】
1.0 2.0
1
0.0 0.0 0.0 1.0 1.0 0.0
【样例输出3】
OK
0.29 0.29
【数据规模】
【题目来源】
与World Final 2008 中Painter 有关,但主要是原创内容
数据点1 2 3 4 5 6 7 8 9 10
堤坝个数1 2 10 200 5000 10000 20000 50000 100000 100000
第三题决斗
【题目描述】
Michel 最近迷上了买彩票。现在,某赌场就一轮决斗的结果开设了赌局。这个赌局同样被
Michel 盯上了,他决定购买这个彩票。
当然,身为有教养有文化的人, Michel 买彩票并不是胡乱买的。他在买之前进行了详尽的
市场调查,并拿到了任意两个选手对决后的胜败情况。可以假定正式比赛的时候决斗后果也
是一样的。
同时决斗的规则是这样的:
首先,选手们围成一个圈。每一回合随机抽出一个选手的号码,让他和他右边的选手决斗。
开始时,1 号右边的是2 号,2 号右边的试三号,依此类推。特别的,n 号右边的是1 号。
战败的选手则退出战场。例如2 号战败,则1 号右边的就变成了3 号。
现在,他找到了你,希望你能告诉他哪些选手可能赢。
【输入格式】
输入数据的第一行为一个整数n,表示有n 个选手。
接下来n 行,每行n 个整数,第I+1 行第J 列表示第I 个选手与第J 个选手对决后的胜败情
况,0 表示选手I 失败,1 表示选手I 获胜。
【输出格式】
输出数据的第一行为一个整数k,表示有多少选手可能赢。
接下来k 行,每行一个整数,从小到大输出这些选手的编号。
【样例输入】
2
0 0
1 0
【样例输出】
1
2
【数据范围】
对于30%的数据,n<=5
对于100%的数据,n<=500
【题目来源】
首届信息学在线测评大赛Q1,清北学堂主办,陈启峰出题

 

 

第1题:Hash,基数排序,扫描统计

第2题:扫描,平衡树维护括号序列

第3题:dp,位压缩

  评论这张
 
阅读(530)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017