月
21日到
30日在泰国芭提雅举行，共有来自七十八个国家的
291名选手参赛。经过两试共十个小时的激烈较量，代表我国参赛的四名选手获得三金一银的优异成绩，这四名选手分别是：来自中国人民大学附属中学的范浩强（金牌第2名），浙江绍兴一中的周而进（金牌第7名）、江苏常州高级中学的蒋中天（金牌第10名）和上海复旦大学附属中学的周奕超（银牌第
34名）。中国队领队分别是
CCF NOI科学委员会副主席、北京大学李文新教授和
CCF NOI科学委员会委员、中国人民大学孙辉博士。
IOI记行
作者：范浩强 2011-07-31 11:03:49
先把我的代码贴出来：
http://builtinclz.abcz8.com/showcode.php?id=2011/IOI2011/ricehub.cpp
http://builtinclz.abcz8.com/showcode.php?id=2011/IOI2011/garden.cpp
http://builtinclz.abcz8.com/showcode.php?id=2011/IOI2011/race.cpp
http://builtinclz.abcz8.com/showcode.php?id=2011/IOI2011/crocodile.cpp
http://builtinclz.abcz8.com/showcode.php?id=2011/IOI2011/elephants.cpp
http://builtinclz.abcz8.com/showcode.php?id=2011/IOI2011/encoder.cpp
http://builtinclz.abcz8.com/showcode.php?id=2011/IOI2011/decoder.cpp
以及我写的解题报告：
http://builtinclz.abcz8.com/art/2011/IOI2011/solution_elephants.doc
http://builtinclz.abcz8.com/art/2011/IOI2011/solution_ricehub.doc
首先，感谢CCF、科协、人大附中。正是因为这些机构我才能去泰国比赛。
今年的IOI是在泰国的一个叫Pattaya（梦里江河注：
芭提雅）的旅游城市举办的。泰国和中国的时差只有一个小时，并没有对队员产生太多影响。Royal
Cliff酒店联盟为我们提供食宿，住的是五星级宾馆。宾馆里设施齐全，窗户正对着窗外的海景，每天清晨在阳台上欣赏大海十分惬意。唯一遗憾的是房间里没有网络，导致只能在Internet
Cafe里上网，不是特别方便。每天餐厅提供自助餐，食品各种风味齐全，基本上世界各国的人都能适应。餐厅提供的蔬菜并不是特别多，但是水果不少，尤其是各种我见都没见过的水果（Guava到底是个什么东西？）。宾馆服务人员十分热情，刚刚在餐厅坐下就会有人上前为我们倒上冰水，早上还会有人过来询问是否需要咖啡和茶。在酒店里，我们遇见的服务人员不管是搬运行李的还是打扫房间的都会主动问好，既有英文的“good
morning”，也有泰文的“Sawasdee”（用泰文字母当然不是这么写）。泰国有一个双手在胸前贴合的礼节，叫做'Wai'。
似乎正是泰国这种“并不特别发达”的国家对于IOI这样的国际赛事的重视程度特别地高。听向导介绍，泰国人的性格是比较随和的，很难听到泰国人之间的争吵。前年的“红衫军”和“黄衫军”的游行也是有组织有计划的，并不是国内媒体报道地那样恐怖。或许是泰国这方神奇的土地养育了充满东方色彩的泰国人。
我们的guide是一个从中国来的学英语的留学生Xiang
Fazhou，他的中文当然非常地好，和他交流没有障碍。他每天早上都十分准时地（6：00）用电话把我们叫起来，各种活动他都和我们在一起，充当翻译（其实是把中文翻译成英文，他只会说一些泰文但是不会读和写）。临别时我们向他赠送了小礼品。在泰国，英文基本上在哪里都能使用，在旅游景点里中文是通畅无阻的。我们四个同学并没有遇到太大的语言障碍。比赛的时候面对有一些媒体的采访需要英文表达，蒋中天作为我们的“对外接口”承担了大部分的任务。而某些参赛选手在镜头前的英语就有点窘迫了。
IOI行程中的旅游部分是十分有意思的。第一天我们到热带花园里去游玩，欣赏各种植物，还有看大象。大象的鼻子的灵活程度超过我们的想象，我正在喝一个椰子的时候突然一个大象路过，用鼻子把我手里的椰子抢走后把椰子吃掉了。我们观看了大象的表演，包括踢球、画画等等。第二天的比赛之后我们到古城里去游玩，欣赏了各种样式的泰国建筑。
我们与来自各个国家和地区的选手展开了广泛深入的交流，包括交换礼品、和南非同学玩魔方、和日本选手交流题目以及和台湾选手打DotA等等，为赛事增添了友好和谐的氛围。其中，中国队和加拿大队住的房间是紧邻的，之前又有一些联系，加上加拿大队的同学的中文都不错，两个队间的交流尤其密切。IOI
不止是一个比赛，也是一个选手之间的大party。我觉得中国对待这个赛事的态度是十分适合的。
今年IOI题目的总体风格是偏向传统的。同时，题目的难度并不是特别大。第一天的题目是纯粹的经典题，有很多满分的同学。中国队的总体表现很好，有两个同学3个多小时就拿到了满分，我花了4个小时多。看来这种题目风格和国内的选拔试题是很接近的。第二天的题目的标题是三种动物：大象、鹦鹉、鳄鱼。这天的题目也表现出了一些特色。其中，鹦鹉是通讯题，延续了去年saveit的风格。鳄鱼比较传统。大象则是一个高级数据结构的题目，有一定难度。
我在第一天的时候在某些题目上没有写出性价比最高的写法，导致提交时间比较晚。第二天我则是先骗分，在把分数骗到金牌线之后专攻大象和鹦鹉。其中，大象被十分优雅地解决了，程序运行速度秒杀标程。而鹦鹉我则是想和很久才意识到题目的本质，而所剩时间已经不多了，我只能选择了一个比较稳妥的写法，导致最后1分没有拿到。
虽然和冠军差一分的第二名的成绩看上去有一些遗憾，但是我已经满足了，毕竟和第一名Tourist相比，我真的是技不如人，且差距巨大。
明年的IOI将在意大利举办。祝福未来的中国队队员！
来自：
http://fanhq666.blog.163.com/blog/static/81943426201163110335392/
IOI2011题目、算法
作者：范浩强 2011-07-26
17:49:48
中国队成绩不错。
说说题目及算法吧： 完整版的题目参见官网：
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 &l
