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

fanhq666的博客

Fan-Fun

 
 
 

日志

 
 

IOI2011题目、算法  

2011-07-26 17:49:48|  分类: 程序 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
中国队成绩不错。
说说题目及算法吧:
完整版的题目参见官网:http://www.ioi2011.or.th/tasks
想先睹为快的看下面

Day1:

热带花园(Tropical Garden)
植物学家 Somhed  带着几组学生去泰国最大的热带花园游玩。这个花园中有 N 个喷泉
(编号为 0, 1, …, N-1)和 M 条小路。每条小路连接一对不同的喷泉,两个喷泉间最多只有
一条小路,小路是可以双向行走的。从任意一个喷泉出发至少有一条小路。每条小路的美丽
程度决定了 Somhed  选择走该条小路的优先程度。每组学生可以从任何一个喷泉出发。 
在任何一个喷泉,Somhed 和他的学生们会选择最美丽的一条小路离开该喷泉,除非最
美丽的这条小路是他们刚刚走过的,且还有其它小路可走。在这种情况下,他们会选择第二
美丽的小路离开该喷泉。当然,如果没有第二美丽的小路可选,他们会选择刚刚走过的小路
再走回去。注意,对于 Somhed 来说没有两条小路是同样美丽的。
Somhed 的学生们对小路的美丽与否不感兴趣,他们喜欢在喷泉 P 旁边的豪华餐厅吃午
饭。Somhed  知道他的学生在走过恰好 K 条小路后会感觉饥饿,当然,对于不同组的学生
K 可以不同。Somhed  想知道在下列条件下,对于每组学生有多少条不同的路径可选。
每组可以从任意喷泉出发; 
但是接下来的路径必须按照上面描述的规则进行选择; 
每组必须在恰好走过 K 条小路后到达喷泉 P 。
注意:他们在最终到达喷泉 P 之前可能曾经到过喷泉 P。
任务
给定喷泉和小路的信息,以及 Q 个不同的 K,你要回答对于每个 K 来说,  有多少条不同的
路径可供候选。
N<=150000
M<=150000
Q<=2000

长跑比赛(Race)
举办 IOI2011 的同时,pattaya 还在举办 2011 年国际奥林匹克长跑比赛(IOR)。作为东道
主,我们需要找到最佳比赛线路。
在 Pattaya-Chonburi 范围内有 N 个城市,它们通过 N-1 条双向的高速公路相互连通,每
条高速公路的长度是一个整数(单位:公里),它连接 2 个不同的城市。注意:连接任何两
个城市之间的路径有且仅有一条,即只有一条路径从一个城市到另一城市,该路径由一系列
的高速公路组成,且路径上的任何一个城市都只能经过一次。
IOR 要求的比赛线路是一条总长度为 K 公里的路径,且该路径的起点城市和终点城市
不同。任何一条高速公路只可能在比赛线路上出现一次,任何一个城市也只能在比赛线路上
出现一次。最佳比赛线路是指包含的高速公路数目最少的线路。
对于给定的 K,你的函数必须返回最佳比赛线路中高速公路的数目,如果不存在符合条件的
比赛线路,返回-1。
N<=200000
K<=1000000

米仓(Rice Hub)
乡间有一条笔直而长的路称为“米道”。沿着这条米道上 R 块稻田,每块稻田的坐标均
为一个 1 到 L 之间(含 1 和 L)的整数。这些稻田按照坐标以不减的顺序给出,即对于 0 ≤ i <
R,稻田 i 的坐标 X[i]满足 1 ≤ X[0] ≤ ... ≤ X[R-1] ≤ L。 
注意:可能有多块稻田位于同一个坐标上。 
我们计划建造一个米仓用于储存尽可能多的稻米。和稻田一样,米仓将建在米道上,其
坐标也是一个 1 到 L 之间的整数(含 1 和 L)。这个米仓可以建在满足上述条件的任一个位
置上,包括那些原来已有一个或多个稻田存在的位置。 
在收获季节,每一块稻田刚好出产一滿货车的稻米。为了将这些稻米运到米仓,需要雇
用一位货车司机来运米。司机的收费是每一满货车运送一个单位的距离收取 1 元。換言之,
将稻米从特定的稻田运到米仓的费用在数值上等于稻田坐标与米仓坐标之差的绝对值。 
不幸的是,今年预算有限,我们至多只能花费 B 元运费。你的任务是要帮我们找出一个
建造米仓的位置,可以收集到尽可能多的稻米。 
1 ≤ R ≤ 100,000  
1 ≤ L ≤ 1,000,000,000 
0 ≤ B ≤ 2,000,000,000,000,000

Day2:

鳄鱼的地下宫殿
Crocodile's Underground City
考古学家 Benjamas 考察了神秘的鳄鱼地下宫殿之后需要设法逃离。这个地下宫殿包含N 个洞穴和 M 条双向的通道。每条通道连接一对不同的洞穴,两个洞穴之间最多只有一条通道,在不同的通道上行走可能需要不同的时间。N 个洞穴中有 K 个洞穴是出口洞穴,
Benjamas 可以从出口洞穴逃离。Benjamas 从 0 号洞穴出发,她希望尽快地到达一个出口洞穴。鳄鱼门卫要阻止 Benjamas 逃离宫殿。它可以通过机关来堵住任意一个的通道(任意时刻,只能堵住一个通道)。即无论何时,鳄鱼门卫堵住一个新的通道,则之前堵住的通道就会被打开。
Benjamas 逃离过程可以描述如下:每次她试图离开一个洞穴时,鳄鱼门卫都会封闭一条连接该洞穴的通道。Benjamas 只能选择没有被封闭的通道走到下一个洞穴。Benjamas 一旦进入一条通道,在她到达该通道的另一端前,鳄鱼门卫不能封闭这条通道。当 Benjamas到达下一个洞穴,鳄鱼门卫可以选择再封闭一条通道(可以是 Benjamas 刚刚走过的那条通道)。
Benjamas 需要设计一个逃生计划,确切地说,她希望有一系列指令告诉她如何逃生。
设 A 是一个洞穴,如果 A 是出口洞穴,Benjamas 可以直接逃生。否则,对洞穴 A,指令是下列形式中的一种:
 在洞穴 A,优先选择一条通道到洞穴 B。如果该通道被封堵,则选择另一通道去洞穴C。
不用考虑洞穴 A,按照逃生计划不会到达 A。
注意:数据保证不管鳄鱼门卫如何封闭通道,总能找到一个好的逃生计划保证 Benjamas在有限时间内可以到达一个出口洞穴。在所有逃生计划中,在最坏情况下用时最短的逃生计划所用的时间定义为 T。
你的函数必须返回最短时间 T,测试数据保证 T 存在,且 T ≤1,000,000,000。任意非出
口洞穴间至少有 2 条通道与之相连。
3 ≤ N ≤ 100,000。
2 ≤ M ≤ 1,000,000。

跳舞的大象(Dancing Elephants)
        Pattaya  的大象跳舞表演非常有名。整个表演中,N 只大象站成一排跳舞。
        经过多年的训练,大象们能够在表演时做很多迷人的舞蹈动作。表演由一系列的动作组
成。在每个动作中,只有一只大象可能会移动到一个新的位置上。
大象表演的组织者想要拍摄一本包括全部动作的相册。在每个动作之后,他们要拍摄到
所有的大象。
      在表演中的任何时刻,多只大象可能站在同一个位置上。在这种情况下,在同一个位置
上的大象会从前到后站成一排。
        一架相机的拍摄宽度为 L(包括两个端点),即一架相机可以拍摄到位于连续的 L+1 个
位置上的大象(有些位置可能没有大象)。因为舞台比较大,所以需要多架相机才能同时拍
摄到所有的大象。
        例如,如果 L=10, 四只大象位于舞台的 10, 15, 17 和 20  的位置。此时,一架相机就可
以把大象们全部拍摄下来。如下图所示(大象用三角形表示,相机用梯形表示)。
在下一个动作中,在位置 15 的大象移动到了位置 32。这个动作过后,我们就需要至少两架
相机才能同时拍摄到所有的大象。
在接下来的动作中,在位置 10 的大象移动到了位置 7。此时,我们需要至少三架相机同时
拍摄,才能拍摄到所有的大象。
        在这个题目中,你需要确定每一个动作之后,至少需要多少架相机才能同时拍摄到全部
的大象。注意,所需相机的最小数目会随着动作的进行而增加、减少或者保持不变。
N<=150000

鹦鹉(Parrots)
Yanee 是一名鸟类爱好者。最近,她正在学习禽 鸟 IP 协议(IPoAC:IP over Avian Carriers),受此启发,她产生了让鹦鹉送信的想法。
Yanee 想让鹦鹉传送一条信息 M。M 是一个由 N 个整数组成的序列,其中每个整数都在 0 到 255(包含 0 和 255)之间。这 N 个整数中可以有相同的。鹦鹉之间没有区别。每个鹦鹉都可以记住 0 到 R(包含 0 和 R)之间的一个整数。
开始,Yanee 用一种简单的方案来传送信息。她让鹦鹉一只一只地出笼,在每只鹦鹉出笼之前,她按顺序从信息 M 中取出一个数字让这只待出笼的鹦鹉记住。后来她发现,虽然所有鹦鹉都可以到达目的地,但是它们不能保证按照出发时的顺序到达目的地。所以 Yanee无法还原出原始信息 M。
现在,Yanee 需要你帮助她找到一个更好的方案。给定信息 M,与之前一样,鹦鹉会一个接一个地出笼,请你写程序实现下面两项操作:
第一,你的程序要能读入信息 M,并把 M 转化成一个最多由 K 个整数组成的序列,该序列中的整数范围是 0 到 R,鹦鹉可以记住这些整数。
第二,你的程序要能读入一个整数列表(列表中的整数是鹦鹉到达目的地时传递的,每个整数都在 0 到 R 之间),并将这一整数列表转化为原始信息 M。
假定所有的鹦鹉都抵达目的地,且每只鹦鹉都能记住出笼前分给它的那个数字。再次提
醒你,鹦鹉可能以任何顺序抵达。注意:Yanee 只有 K 只鹦鹉,所以你产生的由 0 到 R 之
间的整数组成的整数序列最多包含 K 个整数。
子任务 4 
1 ≤ N ≤ 32。
R=255,即编码后的整数必须在 0 到 255 之间(含 0 和 255)。
K=10×N,即你最多能调用 send 函数 10×N 次。
子任务 5 (最多 19 分)
16 ≤ N ≤ 64。
R=255,即编码后的整数必须在 0 到 255 之间(含 0 和 255)。
K=15×N,即你最多能调用 send 函数 15×N 次。
重要提醒:本任务的分数与编码后信息的长度和原始信息的长度的比值有关。
本子任务中,对于给定的测试数据 t,Lt 是编码后的信息长度,Nt 是原始信息长度,
Pt=Lt/Nt,P 是所有 Pt 中的最大值,评分规则如下:
如果 P ≤ 5,得满分 19 分;
如果 5 < P ≤ 6,得分为 18;
如果 6 < P ≤ 7,得分为 17;
如果 7 < P ≤ 15,得分为 1 + 2 × (15 - P)向下取整的结果;
如果 P > 15 或者任意一条输出信息不对,得分为 0。

我会在可预见的未来把我的299分的程序贴出来,充当标程了。
说说算法吧:

热带花园:
把每个点拆成两个点使得每个点有唯一的出度。找出P和P'(P拆出的点)所在的仙人掌。从P和P'向回找。计算每个点到P和P'的距离并按对环长的模分类。各种扫描。(来自周而进的思路)。另:O(QN)的暴力是可以过的(我是这么干的)。
长跑比赛:
树分治,不多说了。其实可以用启发式合并的平衡树来搞(来自周而进的思路)
米仓:
求前缀和。线性扫描。米仓一定建在选出的稻田的中位数上。

鳄鱼:
Dijkstra,用多说吗?
大象:
我的做法:动态树。把每个大象看作一个黑点P,大象往后L+1的地方建立一个白点P'。P的父亲P',P’的父亲是它靠右的最近的一个点(不管颜色)。答案就是最左边的黑点到根的路径上黑点的个数。用动态树、multiset来维护。
鹦鹉:
这是一个很bug的题。官方题解上没有能拿满分的算法。Tourist竟然满了!详细内容我以后贴官方题解吧。
一个小小的提示:
接受者获得的信息实际上是:发送者传送了多少个0、多少个1、。。。、多少个255.
  评论这张
 
阅读(2763)| 评论(6)
推荐 转载

历史上的今天

评论

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

页脚

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