本次比赛的整体难度相当于NOIP提高组的中等难度题目的水平，许多选手都取得了相当高的分数。
据统计，有89名选手的成绩不低于100分，37名选手的成绩不低于150分，25名选手的成绩不低于200分，7名同学的成绩不低于250分。**Mato完整版**、**SHUXK**，两名来自合肥四十五中的同学完整解答了三道题目，取得了满分。
以下是简要题解：
1.Wormhole
容易发现建立虫洞的两个城市之一必定在点1。
证：不妨设在点i和点j（i < j）建立虫洞。那么任意点k与点1的最短路程 = min{X[k]- X[1], |X[k] - X[j]| + X[i] - X[1]}，前者与i, j无关，后者若令i = 1则更小。于是命题得证。
这样，我们便只需枚举除了点1外另一个建立虫洞的城市，记为i。则此时与点1最短路程长度最大的点p，要么是点N，要么是1~i之间与两侧距离的较小值最大的城市。不妨设j = max{k: X[k] - X[1]
6 条评论
-
b460092149 LV 7 @ 2012-11-07 19:04:43
标程在哪儿..
标程在哪儿..
-
@ 2012-11-07 17:06:06
第二题 预处理所有矩形 再用堆找到两个不相交的最大矩形。
-
@ 2012-11-07 15:06:37
Wormhole有问题
貌似是我理解粗了，是点1为首都，而不是点坐标1为首都……
-
@ 2012-11-07 14:55:25
Wormhole有问题
Wormhole题目并没有明确首都是否属于城市（从题目上），样例1中1（首都）为城市，样例2中并没有1为城市，我认为像样例2这样的情况不能在1建立虫洞。
-
@ 2012-11-06 21:21:28
最后一句话有歧义！
"希望得到数据的同学请参考题解和标程"可以理解为“希望 （ 得到数据的同学 ） ”，或者
（ 希望得到数据） 的同学 -
@ 2012-11-06 21:07:34
异议：第二题题解
第二题题解不完整！
前述“一定可以通过一条纵线或一条横线将二维矩阵一分为二，使得两个矩形分别位于两部分。”但最后只讨论了“将矩形划分成(1, 1)~(n, p)和(1, p+1)~(n, m)两部分” 即将一条纵线分割的情况，没有讨论一条横线分割的情况。
应该再加上一段“假如我们将矩形划分成(1, 1)~(p, m)和(p+1, 1)~(n, m)两部分，那么前一部分的最大矩形就是rightbottom(p, m)，后一部分中的最大矩形就是lefttop(p+1, 1)，此时的最优解就等于两者之和。”此最优解再与前面的最优解比较输出即可。
- 1
