会声会影自带的录音器2113你可在剪5261辑好视频后，用你电脑的耳麦就可以录音4102了：
1、点击下图1标志1653
3、开始录音，调整音量大小
4、点击下图3标志，停止录音
5、拖时间飞梭到下一位置，录制下一录音
6、双击每段录音，在属性中可单独调整音量
这是先视频后音频的方法。
如果你先有文稿后根据文稿剪辑视频的，建议你用GoldWave.exe或adobeaudition先录音、剪辑编排好画外音内容软件可调整音量、降噪音和调音色。然后将音频放声音轨再按音频的内容將视频内容放入并剪辑，最后在音乐轨加上背景音乐背景音乐音量不应超过主音量的一半。这样剪辑出的音视频内容会较吻合画外音吔较为连贯。这是我们做专题节目的常用方法
利用假期空闲之时将这几年GCJ，ACMTopCoder 参加的一些重要比赛作个
回顾。昨天是GCJ2006 的回忆今天时间上更早一些吧，我现在还清晰记得3 年
前我刚刚参加ACM 时参加北京赛区2005 和杭州赛區2005 的情况。
我进入清华大学开始本科学习的时间是2004 年8 月在进入清华大学的第一
年里，由于基础课学习比较紧张再加上计算机系不允许夶一学生自带电脑，我没
有参加2004 年的ACM 比赛不过在大一一年中没有停止这方面的练习，对ACM
大概在2005 年7 月底与同班同学shell（贝小辉）和superzn（张宁）一起
决定组队参加ACM 比赛。对于队名没有太多的想法就随便取了一个字典序靠前
一点的bomber。随后进行的几场训练中我的编程状态一直保歭得很好，训练比
赛的主要方式都是：我主写程序shell 和superzn 负责翻译题目，思考算法和测试
这种组队模式一直沿用到我们后面的所有比赛中。
2005 年底我们报名参加了2005 年的北京赛区和杭州赛区的比赛。顺利通过
了预赛进入了现场决赛记得当时北京赛区预赛的时候，我和superzn 一起在參加
百度之星程序设计大赛shell 依靠一人之力过了6 题，最后以第二名的资格参加
2005 年的北京赛区地点设在隔壁的北京大学由于交通非常方便，我们没有
和大部分选手住在一起不过也没有参加Java-Challenge 和晚上的表演。
练习赛之前说到比赛位置抽签，本身意义不是很大可是邬老师神渏的RP
把两只清华的队伍抽在一起，结果练习赛进行了一半另一只清华的队伍THU1
（队员是：吴景岳，栗师和金凯好像后来队名改成了DreamCatcher，不昰很确
定）被要求换到一个比较远的地方理由是有些学校觉得这样不合理。后来很多赛
区也出现过队伍座位在一起的情况邬老师的RP 果嘫不是盖的。
记得练习赛时和复旦的LemonTree（盛城）一起在场地里闲逛结果果然不到
10 分钟就被要求回座位了。还有当时比赛场地是一个体育馆有些队伍把气球放
飞之后气球就飘在天花板下了，总裁判李文新老师还威胁我们说如果明天正式比
赛把气球放飞，就不算通过相应的題目除非有办法把气球取下来。
然后就是比赛的过程了下面有底纹的文字是我找到的当时留下的比赛总结：
E：快速排序。5 分钟1Y
我想5 汾钟的时间可以争取这几年ACM 国内赛区的最快出题记录了吧。
G：二分答案+最小生成树25 分钟1Y。
利用假期空闲之时将这几年GCJ，ACMTopCoder 参加的一些偅要比赛作个
今天晚上先回顾Mobile Robot 成立先期的事情吧，明天再总结惊心动魄的ACM 上
回忆到2005 年清华没有组织校内PK 选拔选择了成都赛区的冠军队THU1 参
加全球总决赛，bomber 从那时也就宣布解散了
队伍就已经成立了。队伍其他两名选手是一起参加IOI2004 的geworm(鬲融)和
次合作的时候使用的帐号如果回到2004 姩的PKU 月赛，也许可以看到thmr3191
Robot 的缩写当然我们觉得Mobile Robot 读起来也比较容易上口。
我们队伍的主要模式都是：
(1) geworm 全程负责读题思考算法和出数据；
(2) wd.h 囷我在比赛前2 个小时一起攻简单的题目；
(3) 2 小时后wd.h 就开始死磕难题，我主写程序一直到3 个半小时左右结
合wd.h 对难题的把握，大家开始合攻难題
这种拖后中卫的打法，对于NEERC 的题目难度非常合适两场比赛我们都做
到了AK（全过11 题）。这种组队模式也一直沿用至总决赛当时wd.h 的状態很
好，对于NEERC 的题目难度我觉得世界上很难有队伍能够有信心做到AK。
队伍成立初期的顺利使我们更有信心我们利用署假时间进行了一些必要的训
练以迎接2006 年下半年的ACM 分区比赛。
北京赛区预赛——网络赛赛网络：
2006 下半年有3 个国内赛区包括北京，上海和西安其中北京赛區最先举
行。2006 年北京赛区的地点设在了清华大学这也是我唯一一次参与组织ACM 分
10 月 中旬举行了北京赛区网络预赛，网络预赛的参与者是所囿报名参加北京
赛区的队伍以决定哪些队伍拥有参加现场比赛的资格。那段时间我们队伍主要
精力放在了 准备比赛上，我们都没有参與网络预赛的命题和测试平台工作由于
清华距离上次承办分区比赛已经相隔很多时间，直接导致网络比赛过程中出现了严
重的网络问 题在这里作为清华ACM 队的一员向受到影响的队伍道歉。
不 过我也是作为“局外人”来了解这次网络阻塞的，因为我确实没有参加
任何与网絡赛有关的活动现在回想起来，我认为平台的稳定性是一个不可推卸的
原因但 是主要应该归咎于题目描述和样例的设计，当然还有测試数据的错误
设想这样一种情况，如果一个比赛过程中从某一时刻起，突然增加1000 个提交
需要rejudge然后所有队伍还都在这一时刻起尝试提茭，我想现有的大部分OJ 都
很难在1 小时之内平息这些提交吧再举一个更夸张的例子，如果OJ 准备的测试
机器的测试速度已经完全跟不上提交嘚速度那么卡住是不可避免的。我们通过网
络预赛的教训总结出一些网络预赛题目的重要经验：
(1) 对于容易上手的题目测试样例一定要足够强。
(2) 对于简单的题目必须仔细确保测试数据是正确的。
(3) 题目描述必须没有任何歧义避免选手通过提交来不断尝试各种理解。
如果題目能够很有效控制提交数目对于测试系统的要求其实不是很高。例
如复活赛和现场决赛的时候测试系统会大部分时间处在空闲阶段。反之如果提
交处在上述病态的情况下，只有非常专业的测试系统才能胜任这样的挑战当然不
总之，对于网络问题我作为清华ACM 队的一員深表歉意如果还有下一次的
机会，我们一定努力做得更好
如果说网络预赛过程中，网络出了一些问题那么，决赛则是结果更出乎峩
们的意料之外在北京赛区现场赛之前几天，我们3 支队伍进行了验题赛比赛
虽然不正式，但是过程仍然很激烈
先列一下决赛的9 道题目吧：
现场赛只有BEHI 这4 道题目有队伍成功通过，可是在验题赛中我们队伍的进
程完全不是这样下面是我们的做题情况：
22 分钟 A 题，数学方法1Y
首先，我们3 支队伍在30 分钟之内都1Y 了A 题A 题是一道中等难度的数学
题，可能A 题需要明确高次等差数列的求和公式而且通过枚举来代替一些假设
可以大大简化问题。现场比赛时有些队伍做了不正确的假设导致始终WA
记得当时zhuzeyuan 使用了一个奇怪的贪心方法，后来被OpenGL 找到一个反
例这个测试用例被添加到正式比赛的测试数据之中，这个反例也成为了现场赛中
使得许多提交WA 的重要数据之一
E 是2006 北京赛区最简单的题目，只需要直接的贪心法就可以解决
52 分钟H 题，深度优先搜索1Y
H 是一道搜索题，题目时限不是很紧不需要太多的优化就可以通过。
75 分钟I 题标准的博弈SG 问题，1Y
I 是标准的博弈问题通过计算SG 就可以得到结果。这题其实有一个阴险的
地方就是当某位置石子为大于0 的偶数时，也需要考虑以保证结果的字典序最
小好在我们及时避开了这个陷阱。现场很多队伍调入这个陷阱中耽误了一些时
129 分钟B 题，最短路径问题3Y
B 是一张平面图的最大流问题，由于图形比较有特点所以可以建图来计算最
小割。但是这张图有106 个点2*106 条边，最短路径需要用堆来辅助實现首先
由于数组开小了RTE 了一次，然后由于用map 实现TLE 了一次这题浪费了许多
G 题，实现和调试了30 分钟超时
G 是2006 北京赛区最困难的题目之一，题目描述很简单判断一张图是否为
co-graph。我们算法的复杂度是O(n*m/32)的不过由于数据个数比较多，程序运
C 题贪心法实现50 分钟，WA
C 题是计算平面圖曼哈顿最小生成树直接计算是O(n2)的，但是题目中n 接
近100000我使用了一个贪心算法，其实和标准算法差距不大不过还是导致
WA。其实提前写C 鈈是很合理的选择当时没有注意到D。C 和G 难度相差无几
F 题是很变态的构造问题，这题完全是wd.h 做的我至今还不是很清楚算法。
250 分钟D 题計算几何，2Y
D 题是一道比较复杂的计算几何当判断一条直线是否穿过一个多边形的时候
忘记考虑了一种情况，WA 了1 次现场许多队伍其实都呮忘记考虑了这一种情况，
但是可惜没有队伍该正确
这场比赛最终我们队伍以7 题结束，另外两队也都通过了7 题我们因此也
没有修改题目难度，随后让大家没有想到的是：一场极低通过率的比赛即将开始了
现场比赛中，我负责在某一个房间为参赛选手送打印资料比赛60 汾钟左右
由于技术问题到Judge 室处理一些问题。经过5 个小时的比赛最终中科大
Student 队通过4 题获得冠军，厦门大学btALT 通过3 题获得亚军北京大学
回顾仳赛现场过程，首先让我们出乎意料的是EE 是2006 北京赛区中最简
单的题目，贪心法的方法参加比赛的同学都想到了可是有一个小小的细节，对于
实数比较大小时需要加入一个微小量eps 来控制精度。E 题没有加eps 的提交占
到总提交的50%以上我们称之为“经典提交”。这个小tricky 不慎导致很多队伍
迟迟不能通过第一题对许多队伍的状态有不小的影响。
其次是AA 题收到了很多队伍的提交，但是最终都没有队伍通过A原因昰
大家做了一些不保证正确的假设，当时我们都通过枚举的方法避免了这些假设
另外，有一些队伍提早接触了F 和G并深深地陷入其中。Φ科大早在240 分
钟就通过了第4 题可是之后他们在G 上花费了不少精力，我们甚至想跑到他们
那里告诉他们G 是最难的
记得180 分钟到240 分钟，我们呮接收到了不超过10 次提交每次大家听到
提交的声音，所有Judge 一起点鼠标抢测试权后来，在TCCC2006 上和Ying 说起
此事据他说和2004 年的广州赛区有许多楿似之处。
赛并再次对网络赛给大家带来的不便道歉。后来清华举行了名为复活赛的比赛
我想复活赛应该就是从那时开始出现的吧？
當年清华一共有6 支队伍但是只参加两个赛区的比赛，造成每个赛区之前
都要进行小规模PK最终只有4 支队伍有机会参加ACM 分区赛。Mobile Robot 建
立之初仳较顺利获得了参加两个赛区比赛的机会，迎接Mobile Robot 的将是上
我们3 人能够走在一起要感谢吴文虎老师的支持，组队初期虽然没有经历
大战但是那些快乐的时光至今都很难忘怀。
利用假期空闲之时将这几年GCJ，ACMTopCoder 参加的一些重要比赛作
收，昨天晚上回顾了Mobile Robot 成立先期的事情吧今天先发惊心动魄的ACM
回忆到，当年清华一共有6 支队伍但是只参加两个赛区的比赛，造成每个赛
区之前都要进行小规模PK最终只有4 支队伍有机会参加ACM 分区赛。Mobile
Robot 建立之初比较顺利获得了参加两个赛区比赛的机会，迎接Mobile Robot 的
将是上海和西安赛区的挑战
比赛前：空前的豪华阵嫆
记得清华大学出发上海赛区的时间是10 月20 日晚上，至于为什么能记得如此
精确是因为在那之前我经历了真正意义上的“赶火车”。10 月18 日TCCC2006
茬圣地亚哥落下帷幕19 日从旧金山机场起飞会北京，飞机着陆时间是20 日下午
2 点半进海关之后已经快4 点了，我立即乘坐机场大巴直奔火车站与大部队会合
之间都没有时间回寝室。
来到中亚饭店报道拿到参赛队伍名单的时候就赫然发现上海2006 的参赛队
伍实力达到了几年来一個不可逾越的巅峰。上海交大的1234 队都出现在了名单中
还有浙大和北大的Final 队都来了，这些还不够芜湖一中的Loner(周冬)，上海微
软ATC 的lympanda 也参加比賽上海交大一直是这几年来清华国内最强劲的对手，
如今交大又占据主场优势实力深不可测。上海微软ATC 虽然是旅游队但是
lympanda 凭借在TopCoder 上嘚表现，没有人敢轻视这位无冕之王的实力
对于上海赛区，清华也派出了华丽的阵容参赛的有3 支队伍，除了Mobile
大家一起围圆桌吃饭朱晨光突然和旁边的王俊说，好像就我们两个没有参加过
IOI然后另一边林希德补了一句，就我们三个不是金牌
我第一次有机会敬仰候启明嘚时候，是自己第一次参加NOI——NOI2002 天津
候启明以满分的成绩获得冠军，当时的亚军就是林希德之后的冬令营，我以非正
式营员参加测试鉮奇得获得第三名但更重要的是冬令营测试的冠亚军就是候启明
和林希德，之后我再没有和两位前辈在OI 上交过手时光飞逝，我代表bomber
队參加2005 年的杭州赛区被候启明领军的Legendary Team打得一败涂地。随后
得亚军的候启明同住在总统套房其实在上海赛区之前我没有在正式比赛中战胜過
然是Target（你可是早点在今年Final 之前把Target 拿回来呀，几次涨停就可以
了）实力也不在前二人之下。
面对知根知底的Shangri-La大家都知道一场大战在即，从实力上分析我觉
得Mobile Robot 略弱，不过赛前我们都没有信心一定能够在比赛中占据优势而
且我们心里深知，上海赛区的结果将很有可能直接决定清华大学当年的总决赛队伍
面对这种残酷的现实，我们都无可奈何有时一些有实力进军总决赛的队伍在清华
都没有机会参加分區比赛。
个人的经验看来我认为在势均力敌的时候，最重要一点是明白自己的优势和
劣势所在要用自己最强的方面来对抗对手，避免暴露出自己的劣势我想在这一
点上Shangri-La 可能没有我们做得好。Shangri-La 的优势是三人的总体实力很强
他们完全可以采用三大高手的组队模式；我们組队时间长，配合默契而且当时自
己刚刚从TCCC2006 以100%正确率回国，保持了良好的状态从单人比赛上讲，
当时我的状态即使有Petr 和Tomek 在场我都并鈈认为自己一定会有明显的劣势。
比赛场地是上海大学的一个大体育馆现场气氛很热烈，想到我们用4 个机房
办的北京赛区的现场比赛鈈由地觉得有些寒酸。
在场外碰到了lympanda他向我了解刚结束的TCCC2006 的情况，我于是给
他描述了一下几道现场比赛过程中1000 分的题目结果全部都被panda 秒杀了，
无限敬仰呀！同时也第一次见到了周冬
提一件飘逸事情，记得当时练习赛有3 题封版时没有队伍通过B 题，但是其
实在封版后我們通过了这题我们应该是当时唯一在练习赛中AK 的队伍。记得之
后好像还和中山大学的郭老师交流过这题不过至于B 为什么能够AC：B 题是一
噵需要SPJ 的题目，可是练习赛的时候没有SPJ而我又坚信自己的程序是正确的，
于是我不断提交可能是由于Judge 不耐烦了，才用Yes 的方法让我们停圵
比赛之前的晚上我们都休息得很好，第二天早上以充足的精力迎接史诗般的上
比赛过程：400 米赛跑
我中学是很喜欢参加400 米比赛400 米比赛從起跑姿势角度应该认为是短跑，
但是400 米已经远远超过了冲刺极限所以400 米跑中，要求我们从发令枪响起的
时候就加速启动直到拼尽全仂为止。
我们回顾一下比赛的过程吧上海赛区比赛之后，我们写下了详细的比赛过程：
按照一贯的方法鬲融从A 开始读，胡伟栋从J 开始讀我准备编程的环境，
然后从中间选择题目读鬲融读完A 后，发现A 是一道简单题于是选择先写A
A：给定ACM网上预选赛的比赛晋级规则，求烸所学校的晋级队伍数
简单模拟题，时间复杂度O(N)本题题目有一个疑问：一个学校出线的队伍
数目可能比该学校参加预选赛的队伍数目還多，但是题目描述和样例表明不需要考
ACM 比赛的第一题的选择对比赛的进程影响很大当没有优先选择比赛中最
简单 的题目时，更需要保歭冷静
在我写A 的过程中，鬲融看了B 和C发现C 也非常简单，于是马上做C
C：将一棵节点带权的树划分成两半，使两半的权值和的差最小
枚举或者树的遍历，时间复杂度O(N)去年有一个深刻的教训：当遍历树的
时候，很容易造成堆栈溢出(杭州赛区留下的疙瘩)对于本题的范围，保险起见没
有使用DFS而是使用BFS。使用BFS 略微增加了编程量但是可以在一定程度
鬲融发现D 是一道经典的统计题，在不到3 分钟的讨论后我們得出了可行的
算法，于是下面写了D在写D 的时候，鬲融和胡伟栋把题看完了经过讨论，
决定胡伟栋开始想一道数学题I而鬲融继续看題义不是很清楚的G 和J 两题。
D：给出平面里的一系列点要找一个矩形，使矩形边上的点最多
离散化后，先判断一条直线的情况枚举两條横边，然后枚举竖边一旦一条
右边的边比左边的边好，左边的边就不会再有作用因此，枚举竖边的过程很容易
这题其实存在O(N2logN)的算法我想出题人也应该没有在第一时间想到吧。
做出D 后写了B原因是B 的算法相对简单。但是意想不到的是：B 的样例不
合法而且Clarification 的速度非常慢，于是只好先把B 放在一边这个过程浪费
随后看到team109(Shangri-La)过了一道红色气球，感觉是G于是鬲融给我讲
了G，但是发现G 实在不像算法简单或程序簡单的题目
此时，胡伟栋推出了I 的一个很简明的公式而且我们发现I 的气球也是红色
的。刚才看G 很可能是被误导的于是写了I。
写I 的过程中由于鬲融看的题基本已经被做完了，胡伟栋给鬲融讲了H 的题
意鬲融想出了一个可行的做法，不过由于还有更简单的题并没有马上莋
I：求杨晖三角形第N+1 行不能被质数整除的数的个数。
可以找出规律然后写出公式，时间复杂度O(logN)我在并不知题目意思的
情况下写过了I，依靠胡伟栋的公式我们度过了此次比赛第一段艰难的时期。
从过D 题到过I 题大概有40 分钟的时间。这段时间我们主要的失误有：
(1) B 的样例鈈合法这其实不是我们的错误。
(2) 受气球颜色的误导过早思考一道很难的题目。
(3) 后来听朱泽园的建议：由于一个人的问题导致卡住应該一个人解决，不
应该让全队都陷入混乱中
我认为我们直接选择写另外一道题目主要有两个原因：一是B 卡住的原因比较
特殊，不是我们婲时间就能克服的；二是I 的算法比较清楚非常稳定。
B：给出16 个数将他们排成十字架形，使力矩平衡求本质不同的方案数。
十字架一囲有4 个“臂”首先找出一个“臂”的所有情况。然后将等值的无
重复的合并成两个相对的“臂”然后从16 个数中选出8 个，将他们作为一組
另外8 个作为另一组，这种方案的总数为前8 个成对的方案数乘后8 个成对的方案
数最后把方案数求和除4。
本题属于搜索题而且时限特別紧，由于搜索问题的优化空间往往很大而且
又是多组数据，所以很容易造成TLE在调对样例后TLE 了一次，改进了算法后
由于开小数组RE 了一佽终于在第三次提交通过了B 题。
记得高中时一次在网上做题(只记得是xreborner 出的题目)的时候比赛一开始
就写一道时限很紧的题目，估计开始程序的正确性是没有问题的就是效率比较低；
但是，在不断优化的过程中改错了程序导致1 个小时以后当程序不TLE 了以后，
程序变成了WA這样使得信心完全崩溃。
听了很多同学讨论之后发现不少队伍就完全卡在了B 题上。以后对这种题目
只能倍加小心现在我们还没有什么特别好的方法。而且B 题的样例只具有测试
性，不具有调试性编程时必须特别仔细才行。
这时大概才1 个多小时我们看似顺利地通过了5 題；但是现场的情况并没有
任何优势可言，Shangri-La 在几分钟后通过第5 题两个队伍的罚时只相差1 分钟。
随后我们到达了第二段艰难的时期主要原因是鬲融把F 的题目看漏了一个条
件，与胡伟栋讨论后误以为这个题比较容易很快这题出现Run-time Error 好在重
读题后发现错误并及时放弃，没有再浪费时间去把Run-time Error 调成WA如果
当时死做此题则后果不堪设想。
在鬲融和胡伟栋分别读F 的程序以及题目的时候由于现在剩下的题目都比较
复杂，我们选择了一道相对清楚的题目H 继续做
H：对一个集合进行两种操作：插入一个数和询问MOD Y 最小的数中最后一
由于数字的范围是[1..500000]，先选择┅个合适的M当Y<=M时，通过插入
时直接保存来处理当Y>M 时直接枚举，用并查集求一个元素的后续这样每一
但是，开始选择M为1000并没有充分估计复杂度的平衡性。开始我们认为
并查集的常数较大但是后来感觉到并查集的常数相对小一些，于是把M选为
500 就过了后来在同出题人茭流的时候，被告之M取在400-800 的范围内都可以
第二段艰难的时期的原因可能不仅仅是题目看漏，也由于题目难度已经增加
好在当时特别是當H 的程序TLE 之后，我们都比较冷静相信自己H 题的算法是
正确的算法，只是参数的选择不够合理这种考验在平时一般是很少遇到的，经受
這次考验之后再遇到类似的问题，我们应该能够更冷静一些
过了H 之后，鬲融已经再次确认了J 的题意随着气球的指引，我们决定攻克
夲次比赛最大的“纸老虎”：J而做J 的过程中胡伟栋一直在想G，已经大致得
J：给出一些数的大小限制的关系求更精确的关系后者判断为矛盾。
转换成图的模型不断迭带调整，直到不能调整为止当然这题由于大小限制
关系中既有’<=’还有’<’，所以需要判断XI<XI 是不合法的时间复杂度O(N
J 题的数据输入输出比较复杂，但是题目本身很简单这题对编程能力提出了很高
通过J 题之后，看了一下board当时Shangri-La 只有5 题，不过茬我们还没
有反应过来的时候Shangri-La 就也同样7 题了罚时上我们领先4 次提交。
在比赛的前200 分钟我延续了TCCC2006 的良好状态。我们配合默契在面
对BHJ 这樣琐碎的题目时，队友会提前把需要注意的细节总结在纸上整个 过程
都保持得很平滑。另外鬲融和胡伟栋在我做每一题时都准备了很匼适的测试数据，
大大减小了我测试的时间并很有效地提高了提交正确率由于剩下的题目难 度明
显高出一个档次，在通过7 题时的罚时领先是最后获得比赛胜利的重要砝码
现在剩下的只有E，FG 三道没有队通过的题目了，其实最终也没有队伍通
过我们曾经读错过F，因此这佽分别尝试了E 和G但是都失败了。这里我们曾
经讨论过先做E 还是先做G当时面临的选择是：E 的复杂度估计较高，不知优化
后能否通过而G 嘚算法性更强，胡伟栋仍然没能完全清楚如何解决实现的复
杂度高于E。我们这次带有赌博性的选择了E并没有仔细考虑如果E 的时间要求
過于严格会出现什么问题（可能与B 的相对轻松通过有一定关系），在此后的比
赛中我们应该注意周全考虑尽量选择题意清楚并且复杂度嫆易估计的题目。
E：带限制的有向图的第K 短路
本题其实有标准的A*算法，我们也使用了这个算法但由于复杂度过高，我
们的程序一直TLE據Judge 说这题对时间的要求非常严格。
G：在一个森林的若干点布置仪器仪器有作用范围D，仪器之间的距离需要
大于等于D求最大的覆盖长度囷最小的权。
本题可以使用二次方状态的动态规划类似CTSC2004 的一题。我和胡伟栋讨
论后成功想出了正确的方法并且在最后时刻写出了程序，而鬲融和胡伟栋则出了
一些测试数据将数据调过后时间已经很紧张了。首先由于忘记优化floyd 超时了
几次在优化了floyd 算法之后，还是没有栲虑到图不连通的情况未能在比赛结
F：给出一些公理，假设和定理之间的关系依次尝试，推出尽可能多的定理
在同等情况下要求使鼡的假设最少。
本题可以用最小费用最大流解决但是比较容易实现的网络流算法都很难在时
现在看来，EFG 三题中的E 没有比赛中想像得那么難当时比赛中受到巨大压
力的影响没能攻破此题，不过FG 题即使出现在CTSC 难度的比赛上也非常合适
比赛结束时我们与Shangri-La 同为7 题，上海交大一隊最终也通过了7 题我
们依靠罚时的微弱优势险胜。经过惊天地泣鬼神的300 分钟我们终于获得了梦寐
以求的2006 上海赛区冠军。Mobile Robot 凭借着上海赛區的夺冠已经可以认为
获得了进军2007 东京世界总决赛的入场券。
比赛结束后见到了很多复旦的老朋友和吴永辉老师吴老师还是和以前一樣，
玩笑开个不停那些复旦的老朋友赛前由于是参与出题，我们一直没有看到颁奖
仪式之前，我们终于有机会在后场一起聊天不过聊天这些时间中，我和b142857
错过了郭老师在颁奖仪式前进行的“点名”（当时郭老师要求我们上去讲解题目）
首先向Shangri-La 致敬，即使在最后一刻相信大家都还仍然有机会，棋逢对
手也是我ACM生涯中的一大到十八简介幸事当两支队伍都通过7 题的时候，排在第3 名的
队伍才刚刚5 题也僦是说，我们两支队伍其实只用了2/3 的比赛时间就锁定了上
上海交大一队最终也通过了7 题比赛开始时我们就注意到了交大开场时非常
不顺利，不过顽强的交大一队稳扎稳打在最后一小时也成功通过了第7 题。在这
里向交大致敬开场的种种不利不亚于我在杭州2005 时的起跑，你們能够沉着应
战破釜沉舟的精神一直值得我们学习。当时交大一队中有一位来自辽宁的选手辛
韬记得NOI2003 之前我们有数次交手都以我失败告终，后来经常在许多网上比
赛中切磋2005 年ACM 北京赛区也有你熟悉的身影，在清华早有耳闻你在交大的
优异成绩祝福你今后越来越好。
这佽比赛的命题工作是由复旦大学担任的复旦大学的命题特点与东欧的命题
风格很接近，题目的算法性偏强题目对程序运行速度要求普遍高。
按照panda 的说法上海微软ATC 队由于一些配合的失误，最终只通过5 题
不过也是前10 的队伍之一。另外芜湖一中队也顺利通过5 题排进前十。GotoFly
通过第3 题的时候还排在第3不过后来卡死在J 上了，有些可惜
后来，分配总决赛名额的时候上海赛区得到了10 个总决赛名额，这个数字
楿信也是这些年来的之最吧
这是一场值得纪念的比赛，参加2006 上海赛区的强队实力远高于几年内的各
大赛区能够站立在上海赛区的最高領奖台是Mobile Robot 获得的最高荣誉之一。
经历了上海赛区大战的洗礼接下来的西安赛区出场的则是更成熟的Mobile Robot。
利用假期空闲之时将这几年GCJ，ACMTopCoder 參加的一些重要比赛作
艰苦的ACM2006 上海赛区结束之后，我们原本以为清华会选择另外3 支队伍
参加西安赛区的比赛况且，大三的课程的实验任務很重我们也就停止了计划的
定期训练。大概在25 天之后12 月20 日左右突然收到邬老师的通知，准备出发
参加ACM 西安赛区比赛我们的2006 西安之旅也就是在这比较仓促的准备中开
西安赛区之前，我们没有定下明确的目标比赛过程中处处都采用了追求稳健
的方法，当时也是为了避免一年前的杭州悲剧重演
西安的比赛没有太多兴奋的AC，没有惊心动魄的场面所有过程都在类似旅
游的气氛中结束了。作为Mobile Robot 的最后一战这里也作一个简要的回顾吧。
由于这次题目又是Srbga（刘汝佳）命题的我最后也顺便列举一下我总结的他命
2006 年清华同样派出了3 支队伍参加覀安赛区，除了Mobile Robot（我
和liuhe(刘贺)，如果你第一眼看见这个词就知道是什么意思我相信您一定准备过
2006 年冬天是我第一次来到西安，刚下火车僦深深感受到了西安的古城气息
到达宾馆之后，我们做得第一件事情就是玩印象很深的是钟楼，鼓楼还有大雁塔
我们做的最主要的倳情可以用GotoFLY 的4 个大写字母GFLY 来表示，就是“公
比赛之前的晚上我们认真讨论了比赛中采用的策略，参加西安赛区没有太多
传统强队我们┅致觉得应该优先采用比较稳健的策略。赛后有比较简短的总结：
按照一贯的方法鬲融从A 开始读，胡伟栋从J 开始读我准备编程的环境，
然后从中间选择题目读与上海赛区相比，比较顺利的是我一下就看到了一道比较
简单的题目B于是我马上写了B 题。
B：使用火柴棒拼接數字给定n,m，求使用不超过n 根火柴棒拼成的m 的倍
本题主要的思想是动态规划方程很容易得出，时间复杂度O(nm*10)但是
(1)如何得到最大的数字？標准的方法是使用BFS搜索的过程中必须非常注意
搜索的顺序，但是这样实现很容易出错我注意到了n<=100 的条件，因此结果不
会超过50 位于是峩使用3 个int64 来保存结果，这样既实现简单又不容易错虽
然程序常数比较大，但是不至于导致超时
(2)不能不使用火柴棒，而数字0 也需要火柴棒来拼成例如n=5，m=97 的结
ACM 比赛的第一题的选择对比赛的进程影响很大此次比赛很成功地使用了
E：标准的课堂睡觉问题，求最早所有人不睡覺的时间
简单的模拟题，而且时限很宽松
E 其实是最简单题目，但是由于我的低级错误不仅得到了一次罚时，而且浪
费了宝贵的时间好在当时比较冷静，很快改正了错误
D：对于一个不超过100*100=10000 的表达式，可以在其中加入*来表示任何
字符如果一个表达式只能和唯一的等式对应，则称为A 类表达式给定一个表
达式B，要求通过改变最少的字符使它变成A 类表达式
本题使用了一次搜索再检索的方法，可以有效控制程序的速度估计时限问题
后选择先提交节省了不少时间。
J：给定一个4*4 的网格的边框图形问是否可以通过在4*4 的网格上放6 个
2*2 的正方形框得到。
H：给定一组旋转后的乐谱及初始音符及结束音符求原始的音符序列。
开始胡伟栋没有看到旋转的角度是整数的条件于是推出叻可以解决实数角度
的数学公式。但是由于公式需要考虑的情况比较复杂幸运的是我们使用了枚举角
写了读入部分之后，看到Panacea 过了H 题鬲融重新读了题目，发现了角度是整
数的条件于是稍微修改就得到了正确的程序。
本题需要判断的条件很多需要考虑得很仔细：
(1) 先把唑标按照X排序。
(2) 通过初始音符及结束音符得到sd判断sd 是否在1 到5 之间。
(3) 判断相邻两个字符的距离是否在sd 到5sd 之间
(4) 判断每个点的坐标是否可以對应一个音符。
F：求3 维空间的Voronoi 图输出每个Voronoi 块体积占的比例。
胡伟栋提出了本题的正确算法：分割立方体如果一个立方体的8 个顶点都到
┅个点最近，那么这个矩形内的所有点都到这个点最近否则就分割这个立方体，
直到立方体的体积少到一定程度为止
开始程序的精度鈈够，后来胡伟栋提出了一个启发式的分割立方体的方法思
想就是使得两个立方体的分割面以尽量大的概率穿过Vorinoi 平面。程序的效果很
好而且那时时限也已经放宽，于是顺利通过了F 题其实本题蒙特卡罗法也可
以过，我们也想到了这个方法但是由于随机过程写的效果有問题，导致精度不够
通过F 题的时间是270 分钟，封版时除了Panacea 通过4 题其他队伍最多只
有3 题。当时Panacea 正好坐在我们背后很可惜他们卡在了D 和G 上，最终也
只有4 题最后半小时我们也没有尝试H 或者A，因为其他队伍很难在最后一小
时通过4 题我们就简单尝试了几次C 就默默地等待着西安賽区比赛的结束。
最终我们通过6 题排名第一由于已经获得了上海赛区的冠军，不参加ICPC
的排名不过仍然获得了Solaris 杯。
西安的ICPC 冠军是北京大學的T2（rainerdzx 和cici），后来他们依靠西安
的夺冠成绩进入了2007 年的全球总决赛T2 在最后一小时表现极其神勇，顺利通
过2 题一举超过了GotoFly 和Panacea而且最后幾分钟还很有希望通过H，赛后
和rainer 讨论之后发现算法相差无几可能就是一些小细节缺陷吧。 年
度的ACM 比赛从上海到西安，还有东京的总决賽Mobile Robot 每次比赛都能
看到了T2 熟悉的身影。我们在封版之后常常由于压力较大很难攻破题目他们在
封版之后的冷静心态非常值得我们的学习。
题依靠罚时优势排在第四两队都欠缺一些运气，很可惜另外印象很深的是，坐
在对面的朝鲜队通过了4 题在ICPC 中排名第2如果西安能够哆一个名额的话，
他们就能够出现在总决赛赛场了
西安赛区是Srbga（刘汝佳）出的题目，从高中时期就开始做了Srbga 出的题
目西安赛区的题目叒一次体现出了刘汝佳命题的许多重要特色：
(1) 如果Srbga 大哥出是一套题目，那么你会明显觉得题目拿在手上明显重一
些Srbga 大哥出题很重视题目描述或者故事的完整性，他很少使用一些僵
硬的题目模型和描述有时读着他出的题目更像是在读小说，欣赏故事
当然，由于Srbga 大哥出的題目描述完整刚拿到题目的时候会感觉很难
上手。我们很容易发现没有一道题目容易上手用数据表达，比赛开始时
(2) Srbga 大哥出的题目和世堺总决赛的题目风格近似题目多半对编程能力
提出很高的要求，相比之下对算法的要求不是非常高考察的都是比较基
本的算法。如果鼡一个字形容就是：野
(3) Srbga 大哥出的题目对算法的考察范围非常广，虽然对于某特殊的算法要
求不高有时还需要很强的组合算法能力。
(4) Srbga 大謌出的题目中很注意数据的设计例如C 题中特别生成了极端的
情况，J 则使用了接近20000 组数据一般情况下，不经过精心设计的随机
Mobile Robot 来说是丰收的一年我们圆梦了上海和西安的双冠军。在随后的冬天
我们加紧训练准备东京的总决赛。
利用假期空闲之时将这几年GCJ，ACMTopCoder 参加的┅些重要比赛作个
世界在校学生的程序设计大赛，2006 年的TCCC 在圣地亚哥举行从北京到旧金山
的飞行只需要11 个小时左右，所以不至于那么疲劳路上一切都很顺利，很感谢
OpenGL 的提醒对于超过8 个小时飞行自带拖鞋和枕头对我来说还是很重要的。
TCCC2006 使用的标准的TopCoder 现场比赛形式比赛有48 洺选手参加，首
先48 名选手被分为16 个人一组每组分别进行半决赛，前2 名直接晋级决赛3-
决赛由8 个选手参加。TopCoder 现场比赛中很重要的一个创新昰：每名比赛选手
在观众席前都有一个同步的显示器这样观众可以看到选手任何时刻做的事情，极
下这两场激烈的比赛吧
至于3 个房间嘚分配，TopCoder 按照注册截止时选手的Rating 分布蛇形分配
但是TCCC2006 的房间实力分布极不平衡，我与上届冠军tomek著名选手reid，
1赛前Room 1 成为公认的死亡之组。
茬圣地亚哥我和师兄Macsy（张一飞）同一个房间，很感谢师兄的关心我
那几天休息的都很好。要知道如果同房的人有10 小时左右的时差的话一人必须
很小心才能保证不影响另一人的休息。
Room 1 在我抵达美国的第二天早上进行选手允许提前30 分钟准备一些必要
代码。不过现在大家嘟比较喜欢学习Petr 那样一行代码都不打下面就是比赛的
250 分题目是：给定n(n<=50)个整数AI 和一个阈值d，计算n 个整数所有排列
PI 中满足|API-API+1|<=d 的排列中所有不哃可能AP1 的个数。这题最标准的方法是
动态规划基本思想是把n 个整数排序之后，计算两条相邻元素不超过d 的序列
我使用了一种更精巧的算法，把n 个整数排序之后对于AI，如果AI 可能作为排
列的第一个元素那么AI 必定在某一个方向（大小）连续而在另一个方向每间隔
两个元素楿连。这个算法比较容易实现但是正确性证明比较难，甚至让人第一感
觉是错的我写完程序测试了所有样例都正确就提交了，243 分提茭之后我又测
试了许多数据，并在纸上尝试证明正确性
赛后，我看了网络上的讨论记录在我提交250 分题之后，立刻遭到了misof
的怀疑他认為我的算法有问题。据Macsy 学长的回忆OpenGL 在我屏幕前看我
写完程序，也认为我的算法是错的不过后来他们讨论之后发现没有反例。
而是250-600-900现茬看来，对于250 比较顺利的情况应该先做500，若250
不顺利或者想出奇制胜的话可以先开1000 分。当时没有什么经验我认为900
比600 应该简单一些，于昰就打开了900
900 分题目是：给定一张n(n<=10)个点的带权有向完全图（也就是n2 个实数）
和一个衰减系数p，求一条经过d(d<=10)条边路径（不需要保证简单路径）要求
这条路径的指数衰减长度（指数衰减是指第i 段的长度乘以pi-1 然后求和）最接近
1000。这题如果使用穷举法就需要1010 左右的计算量，在TopCoder 的測试机上
也不能通过由于路径长度很容易超过1000，所以很难找到多项式时间的动态规
划我马上有了一个想法——双向搜索。对于长度为d 嘚路径其实可以看作从
某一个点p 出发的一条反向的长度[d/2]的路径和一条正向的d-[d/2]的路径，对于
固定的节点v 来说这种两个方向的路径都不超過n[d/2]，这样只要枚举一个方向
的路径然后二分查找另一个方向即可复杂度是O(dn2+[d/2]) 。
现场比赛调试环境不是很好我花了不少时间调试以发现程序中的错误。提
交之后690 多分还不到700。不过对于900 分的题目在那种压力下还可以接受
提交之后我花了15 分钟左右测试，没有发现错误于是僦准备做600 了。
600 分题目是：一道经典的数学题给定一些盘子叠放的规则，计算顶层盘子
的最大可能大小其实算法不是很难，只要二分顶層盘子的大小然后依次贪心计
算来判断底层是否能够满足即可。只是贪心的时候要考虑两种情况一时想不清楚。
我当时已经感觉很疲勞思路不是很清楚，最后40 分钟时间也没能调试通过这
题过于琐碎，Room 1 中最终没有选手通过600 分题并且成就了一个刺激的
Coding 阶段我和tomek 采用了截然不同的策略，我跳过600 直攻900而
tomek 在600 中挣扎了很长时间才放弃。Coding 阶段结束时有4 名选手提交了3
题。我依靠速度优势领先同样提交250 和900 的tomek 35 分左祐
分程序，但是由于我选择的数据实在太弱失去了25 分。这样我和后面的tomek
只相差10 分左右了所以我决定只要tomek 不动，我也不动了其实，當时
tomek 已经知道自己的900 是错的Challenge 阶段他估计已经放弃了。我的
了所有提交的600凭借225 分的加分超过了我，排在榜首这样比赛的形式也一
目了嘫了，7 位选手提交了900我依靠速度优势领先第四名reid 超过100 分。只
排名倒序进行的测试到我时，除了tomek 的4 名选手的900 都过了显示我的
结果时，兩个绿框闪烁了很久终于显示出了两个大大的钩我终于可以欢呼庆祝胜
利了。我前面的Ying 也两题全过了这样我们两位中国选手得以在死亡之组携手
出现，这场比赛真可谓是中国选手的胜利Reid 只能在Wildcard 赛再作努力，
tomek 则被直接淘汰出局了
我们参加了TopCoder 赞助的Laser Tag 游戏，我们所有中国囚组成了一队我的发
挥很差，原因是这个游戏与CS 不同选手头上没有感光器，而我喜欢遇到人就攻
击头部所以狭路相逢多半是我失败。活动中我有幸结识了许多Dev 的神人，
当时由于vividmxx 没有参加magicpig 和PE 的竞争很激烈，最终PE 获得了“浙江
大学建校100 年来第一个TCCC 冠军”记得赛后我uncle 來到现场，我uncle 是
浙江大学本科毕业的magicpig 见我uncle 第一句话就是“浙江大学建校有100 年
历史了吧？”汗死了另外zjq 也获得了Design 的亚军。
第三天中午Championship Round 开始了决赛时，场地里安装了很多摄像头
可以说我们的任何举动都在严密监视下了。这回我提前确认了题目分数是标准的
Eryxmathijs，Petr 和Ying面对決赛选手的实力，我已经没有意义定一个类似于
“保几争几”的目标了努力发挥自己的水平是最应该做的。下面就是比赛的过程
250 分题目昰：给定n 个正三角形每个顶点都有数字，选出6 个三角形拼成
一个正六边形要求相邻的数字必须相同。三角形允许旋转计算能够得到哆少个
本质不同的正六边形。题目很长我仔细读了两遍才开始写，算法很清楚就是枚
举六边形中心和四周的7 个数字，然后判断是否有足够的三角形在判断本质不
同的时候犯了一个错误，调试了几分钟提交之后只有215 分了，看了一下排名
Petr 有232 分之高，其他选手都还没有提交测试了几分钟发现程序的运行时间不
是很稳健，很容易到达0.8 秒左右测试了15 分钟之多才逐渐放心下来，因为基
本上所有数据都0.8 秒左祐赛后Macsy 告诉我，我的程序速度瓶颈是在set 的判
断所以时间比较稳定，不会超时我当时的犹豫和没有经验浪费了至少20 分钟
按照赛前的计劃，我这时应该打开1000 的题目的但是由于自己对250 没有
信心，而且求稳思想比较重我先打开了500 分的题目。现在看来开500 分的
题目并不算错誤，其实在打开500 分题目的时候与Petr 的差距不是很大。
500 分题目是：给定一个机器人的移动命令序列要求计算结束时机器人的位
置。由于移動序列中允许()这样的重复操作直接模拟是超时的。这类题目的标准
算法是利用矩阵乘法由于之前对于此类题目没有经验，没有准备好僦开始写了
导致矩阵处理失败。我果断放弃了调试换用一种记录中间结果的搜索方法，写完
的时候已经只有280 分了更重要的是我已经沒有时间进攻1000 分了。提交之后
1000 分题目是：给出一个排队取菜的模型计算一个等待时间的排队序列。
而且对于多种答案的情况要求计算芓典序最小的序列。题目其实不是很复杂集
合动态规划就可以解决，不过模拟取菜过程时需要非常注意细节Petr 提交了一个
660 分左右的程序，Ying 则在最后一分钟提交了400+分排在第2。
我瞬间提升到了第二名的位置不过虽然Petr 的1000 分挂了，但是他依旧凭借
250 和500 的速度获得了冠军
在这里說一下1000 分的真实情况吧，因为这些时间来对于TCCC2006 Final
Round 的1000 分题目有很多不同的说法比赛结果中显示没有选手通过1000 分题，
如果仔细分析测试结果Petr 嘚程序由于超时出错，而Ying 的程序由于一个地方
没有清0 而导致错误确实很可惜。因为如果Ying 的1000 能够Pass 的话他将
是TCCC 的冠军。不过Ying 的算法犯了与慥成Petr 超时一样的错误他们的动态
规划程序比标准方法多出一个n 倍的时间，我曾经成功生成了一个用例可以让
Ying 和Petr 的程序都超时，这个例孓已经得到了Ying 的认可需要指出的是
TCCC2006 是TopCoder 的测试机的速度还是很慢的，两个程序如果在现在的机子上
运行可能只需要1 秒左右了
比赛之后和uncle 箌downtown 游玩了一下，参加完颁奖晚会第二天就回国
TCCC2006 是我第一次参加TopCoder 的现场比赛，很有幸能够在这么多的第一
次中就进入决赛并且获得第2 名的荿绩很感谢同参加比赛的同学Macsy，
OpenGLYing 还有PMH 的关心和帮助，你们在我比赛时全程在场边让我感觉很
另外，我还有幸认识了visualage现在他已经是arena 嘚负责人了吧。记得他
和OpenGL 在Room 1 的Challenge 阶段通过大声叫中文（在国外这是最好的密码）
告诉我tomek 的900 是错的，可惜我没有听见
TCCC2006 对于中国来说是不小嘚收获，中国选手占领了Dev 比赛PE 获得
的亚军，也就是说中国包揽了所有亚军在比赛之余，我很高兴认识了众多
Petr 在决赛中表现了非常良好嘚状态TCCC 的夺冠标志着Petr 收获了2006
年的大满贯。Ying 也采用了很合理的策略只可惜他的赌博由于运气差一些惜败。
我采用了比较保守的策略在所有决赛选手中排名第2，这也是我在TopCoder 的
现场赛事中的最高名次了
TCCC2006 我很感谢家人的关心，父母凌晨很早起床查看我的比赛结果而
uncle 还特地趕来现场为我加油。这几年的TopCoder 现场比赛的赞助商列表里都能
右的全程直播父母和uncle 都在网络上观看了现场的影像直播。
正确率提出了更高嘚要求我们不必太在意Coding 阶段的那些高分，只要自己的
程序是正确的就是成功的。
利用假期空闲之时将这几年GCJ，ACMTopCoder 参加的一些重要比賽作个
回顾。首先是GCJ2006 的回忆
Code Jam 2006 的比赛地点设在了纽约，这次纽约之行之前的签证出了不小的问题
这里非常感谢大家对我们的关心，特别感谢吴总（wyy）和鲁小石的帮助使我最
从北京到纽约的飞行时间是13 个半小时，由于是第一次做超过8 小时的飞机
没有什么必要的经验和准備，路途非常疲劳一到宾馆就睡了，结果由于手机铃声
的时间使用的是东方时间差了12 个小时，一觉把所有事情连晚饭一起都睡过了
隨便吃点东西就继续睡了。之后的所有现场比赛我都养成了提前睡觉的习惯以保
比赛时精神状态还算可以，但是分配了比赛房间之后发現自己和tomek 分在一
个房间真是很不爽；在和旁边的zhuzeyuan 抱怨的时候，发现他和Petr 一个房
下面就是比赛过程了总体来说比赛过程比想象的艰苦，鈈过其实在System
Test 之前的结果还是很满意的先简单描述一下3 道题目吧。
250 分的题目是一道平面极值问题给定n 个点，求一条直线使得n 个点到
这條直线的y 方向截距总和最小。我回忆起金凯在2003 年集训队论文中报告中讲
到的很类似的一道题目记得一个重要结论是这条直线一定经过两個点，虽然题目
有些不同但是很快得到了相同的重要性质：这条直线一定经过两个点。这样很容
易得到一个O(n3)的算法
500 分的题目是一道反Hash 函数问题，给定一个Hash 函数和x求一个最小
的非负数y 使得H(y)=x。估计了一下单向搜索需要26^8，于是我改用双向搜索
这样就变成了26^4。但是实现过程比想象的复杂很多提交了后只有280 左右了。
其实这题有更简单的数学方法，tomek 的程序有450+
1000 分的题目是涉及卷积函数和计算反函数的问题，通过转化变成线性方程
求解问题当时受到现场气氛的影响有些紧张，浪费了不少时间提交之后550
分左右。其实当时一些原理问题都沒有想清楚，不过后来和Ying（王颖）经过讨
先得比较多我和其余3 人差距50 分以内。
Challenge 阶段开始之后我由于500 分题自己使用的是双向搜索的算法，没
有注意到有些单向的搜索加模线性方程的方法其实是正确在10 分钟以内cha 错
了2 次。落后于上述的4 个人排在第五。
但是下面的5 分钟发生叻戏剧性的一幕首先是Petr 的250 被cha 了，接着
andrewzta 领先我30+分由于我和tomek 处在一个房间，所以我做出了一个大胆
的决定就是challenge tomek 的1000 分题，我随机生成了一個随机大数据在最
后时刻提交了这个challenge，系统返回了一个令人窒息的结果：successfully
我很有幸能够在第一次参加现场比赛时就能够和冠军这么接菦，如果System
Test 能够全部Pass 的话这可以认为是一场完美的比赛。
可是整个故事就好像是被刻意设计的一样，System Test 之后的结果使我目瞪
口呆：首先是250 汾的题目我由于有一个地方没有及时使用double，而造成整
数越界；然后1000 分的题目简直是悲剧的最高境界，我在高斯消元的时候没有
及时把┅个重要变量暂存导致影响了结果，没有想到竟然躲过了那么多大数据
但是不能通过System Test。最后排在50 名左右这两个错误至今刻骨铭心。
11 朤的纽约有些冷我随大队人马一同去了一趟帝国大厦，景色很迷人第
二天休息一下后与几个中国选手打了一会“找朋友”，第一次美國之行就结束了
比赛结果虽然不是很理想，但是对于第一次参加世界比赛的我还算可以接受
也算是为今后的比赛留下一些教训吧。
在渧国大厦上见识了大家的拍摄功底我由于技术差没有拍到任何合适的照片。
在比赛过程中首次见识了liympanda 的大将风度，和panda 在一起总是笑口
瑺开他无论遇到什么情况都无所畏惧，这一点我一直在努力学习不过一直做的
不好。但是panda 打牌的时候就不一样了总是喜欢偷看别人嘚牌，还炫耀自己
会说广东话被Ying 和rocking 两位广东选手狠狠鄙视了一番。
Petr 加上之前的TCO 和之后的TCCC拿到了2006 年的大满贯，可以算是历史
性的突破吧Tomek 有些可惜，比完了还问我怎么cha 他1000 分的呵呵。
其实这次比赛Ying 挺可惜的其实Petr 的发挥并不很好，如果Ying 运气再好
一些的话历史从那时就要偅写了。不过Ying 还是体现了他超强的数学功底让
人佩服。另外来自复旦的同省队友LemonTree 也获得了好成绩。
这好像是自己最后一次和xreborner 同场竞技叻（由于之后xreborner 退役了
很长时间忘记GCJ2008 我们又见面了，谢谢Savior 的提醒）感谢您在我高中
时期教授了我许多编程技巧，我一直沿用至今
利用假期空闲之时，将这几年GCJACM，TopCoder 参加的一些重要比赛作个
回顾今天到了2007 年初的东京，回顾一下2007 世界总决赛发生的趣事吧
2007 年的东京ACM-ICPC 全球总決赛在樱花盛开的3 月初拉开序幕。成立了一
记得黄金雄教授在杭州2008 时说ACM 总决赛的实力分布由原先的美洲独霸
逐渐转向了现在的亚欧争霸。2007 年同样来自亚洲的上海交大具有很强的夺冠
实力，欧洲2007 年虽然没有顶尖高手Petr 和tomek 的参与但是ACM 传统名校
其豪华的阵容。虽然在2000 年前后美洲队伍成绩不佳但是近些年由于众多欧洲
选手的加盟，美洲MIT 等顶尖名校也在总决赛中表现得非常强势
记得，每次世界总决赛之前TopCoder 的論坛上都会罗列出所有参加总决赛
的TopCoder 选 手名单。但是我不是很看重这些数据因为在很多次与欧洲选手切
磋之后，我发现了自己与欧洲选掱相比的一个重大缺陷：我参加各类赛事以来起
初比赛过程中常 常受压力的影响很大，很难正常发挥自己的水平后来情况有所
好转，茬大多数比赛中都能正常发挥自己的水平可是，令我感到意外的是许多
来自西方的选手在 巨大的压力下，反而表现得极其兴奋而能超瑺发挥出自己的水
平来自西方的各队，我相信他们只要达到了兴奋的状态都拥有获得冠军的实力。
去年上海交大总决 赛总结中他们吔提到了自己没有发挥出应有的水平，而IMFO
即使在比赛压力下仍然能够做出8 题可见他们平时训练实力之强。但是我觉得
现场比赛发挥受影響可能是少数中国选手的坏习惯可能不适合用同样的思路分析
出发的前一天晚上，我仍然熬夜参加了TopCoder 上的SRM 比赛竟然是Petr
出的题目。当时峩与Petr 的Rating 差距很小当时我3 道题目都交出了很高的分
数，在System Tests 之前遥遥领先但是500 和1000 分的题目都由于一些很小的
粗心而失败了。我也失去了在總决赛之前超过Petr 的大好机会结果到达日本之
后的第二天，吃早餐的时候我就碰到了作为教练来到东京的Petr，他一看到我就
扯前天比赛的倳情汗。现在回想起来那场SRM 对我的总决赛之旅确实有不小
抵达东京之后才发现，所有队伍中只有我们选择了与所有志愿者衣服颜色
楿同的清华校色紫色，开幕式过程中许多队伍都把我们当成志愿者了。
练习赛前一天的晚会很丰盛大多食物都是中国风格的，水果也非常好吃
晚会期间，我见到了众多大陆学校的队伍当年大陆至少有15 支队伍参加总决赛，
随处可以感觉到说着国语的选手同时还见到叻许多TCCC 上出现过的面孔，随后
发现ardiankp 也来参加了我们还聊起了ACM 在新加坡（ardiankp 是代表南洋理
工大学参加的）的情况。类似总决赛这样的比赛峩觉得选手之间的交流则更重要
了，因为每次总决赛都会集结众多熟悉的ID 但陌生的面孔晚一些之后，我们与
北京大学的T2 一起打牌队友geworm 囷wd.h 都抽签到了另一方，他们的牌太猛
了在加上我和李文新老师的牌都不好，结果我们惨败
从正式比赛的前一天的中午开始，主办方组織我们游玩当地的Disney 乐园
日本3 月的景色很美，当地人也很热情唯一的缺点就是无论用日语还是日式英
语都很难交流。我们在Disney 乐园中主要鉯观看表演为主没有参与过多的活动。
东京到了晚上有些冷我嘴唇都有些结冰了，可是发现路上许多日本女高中生还穿
总决赛的队伍昰按照学校的音序排座位的练习赛时我们发现自己坐在来自
荷兰的上届亚军Twente 大学旁边，刚打招呼就发现他们3 人的最低身高也有190
据说荷蘭女子的平均身高也有180 以上，似乎觉得自己是从小人国来的
练习赛过程中，我已经丝毫感受不到娱乐的气息了现场的紧张气氛已经笼
罩了我们全队。所有队伍都在抓紧一分一秒熟悉比赛环境赛场中敲击键盘的声音
已经完全覆盖了观众鼓掌的声音。比赛中使用的PC2 提交系統比想象得稳定我们
努力尝试各种功能以熟悉机子上的编程环境。东京的总决赛使用了一个形状奇特的
键盘由于当时早已养成了自带鍵盘的习惯，这次总决赛中奇形怪状的键盘对我编
总决赛正式比赛在第二天9 点左右开始Bill 想尽各种办法活跃气氛，不过比
赛开始前几分钟現场还是静得可怕比赛开始5 分钟之后，现场就被键盘声笼罩
直到结束我们回顾一下比赛的过程吧，底纹的文字是我比赛后写下的总结：
这次World Final 的题目又基本由编程题组成可能是由于比赛时不够兴奋，
比赛全程都非常不顺利
大概从2003 年开始，世界总决赛的题目风格已经完铨倒向以编程题为主的特
点对此我们早有准备。不过由于时差问题还有几天前SRM 比赛由于错两题导
致Rating 跌停对我信心的影响，使我比赛中┅直不是很兴奋不过比赛过程中，
我们仍然坚定的采用前面提到过的常用组队模式：
(1) geworm 全程负责读题思考算法和出数据；
(2) wd.h 和我在比赛前2 個小时一起攻简单的题目；
(3) 2 小时后wd.h 就开始死磕难题，我主写程序一直到3 个半小时左右结
合wd.h 对难题的把握，大家开始合攻难题
25 分钟：Problem A，簡单地枚举可是我生物没有学好，没有考虑父母基因
的顺序问题错了一次。
比赛开始时正常情况我会从B-I 中间寻找容易上手的题目。鈳是由于有些紧
张直到geworm 给我翻译A 题目内容时，我还没有读懂任何题目这种情况很少
题目A 的描述，需要一些必要的生物知识帮助理解鈳是这些东西我早已忘
记。geworm 花了不少时间帮助我理解这题我还是由于没有考虑父母基因的顺序
WA 了一次。不过改过来之后我们竟然是所囿队伍中第一个通过A 题的，可见当
时很多队伍也没有完全放开
43 分钟：Problem B，最长上升子序列开始算法没有想好，莫名其妙地错了
如果说题A 嘚WA 是生物问题那B 的WA 简直就是莫名其妙。B 就是最长上
升子序列问题好像刚开始写时我和wd.h 都没有想清楚，写了一个神鬼莫测的程
序WA 一次の后才改成正确算法。可是当时我们都没有想到的总决赛中我们队
伍莫名其妙的WA 噩梦才刚刚开始。
97 分钟：Problem G枚举+模拟。这是很扯淡的一題题目很容易看错，我
们由于看错题目错了两次等看到Twente 大学过了之后才重读题目，找到了正确
的理解浪费了大量的时间。
G 的题目描述确实不是很清楚许多队伍都发生了理解错误，我们也不例外
不过第2 次提交错误就不能理解了，当时也不知道出于什么原因又提交了苐二次
难道是想先抢一个提交冠军吗？当时我们确实受到了开局不顺利的影响这样做在
罚时本身就落后的情况更是下雪上加霜。
146 分钟：Problem FBFS。其实这题是我发挥编程能力的机会但是我开始
用了一个很奇怪的搜索方法，错了一次才改用BFS 过了
在G 题迷茫而放弃之后，我又尝試实现了FF 的第一次WA 是我们Final 之行
的第三次“莫名其妙”了，我也不知道自己用了什么一种奇怪的搜索方法竟然过了
样例还马上提交了，媔对这种情况我有些着急表现得很不冷静。好在geworm
及时提醒我马上改成BFS 过了。在这期间wd.h 已经实现出了I 题，并提交了一
178 分钟：Problem C排序+枚舉。这题有一个阴险的地方就是theta=0 的
情况，还好我们考虑到了这也是我们唯一一次AC 的题目了。
C 题的算法其实非常清楚阴险的情况我们吔考虑到了，我终于没有再搞笑一
次这也是我们唯一一次AC 的题目了。从通过C 的时刻讲我们的形式还是很有
利的，因为难度很大的I 我们巳经实现得差不多了
224 分钟：Problem D，数学题这题本是一道很简单的数学题目，但是不知
出题人怎么想的搞了一些没有任何意义的东西，真昰这次题目的一大到十八简介败笔我们
开始由于没有注意三点共线的情况错了3-4 次，然后由于int64 越界又错了3-4 次
最后错了7 次才AC。这题一共浪費了1 个多小时
在BGF 各一次奇怪的WA 之后，我们又完全陷在了D 题的陷阱之中如果顺
利的话D 题只需要15 分钟就可以写完，可是我们忘记考虑了D 题Φ很多的阴险情
况拖延了1 个多小时，贡献了7 个莫名其妙的WA可是，当时我并没有想到
这已经是我AC 的最后一道题目了。
227 分钟：Problem I数学+模擬。这题是Jelly 写的有很多特殊情况。
平心而论我在总决赛上的状态不是很好，编程速度受到影响而且有10 次
以上的错误提交。最后我们7 題的罚时高达1200 多而上海赛区同样7 题的罚时
只有700 多，从这一点上也可以看出当时实在不在状态不过，wd.h 很好地执行
了我们预定的组队模式顺利完成了拖后中卫的角色。在我通过D 题之后他改
正了I 程序中的最后一个bug。I 题最终也只有我们和华沙两支队伍通过可是说
是我们最終能够获得亚军的杀手锏。记得在颁奖仪式之前基本上所有选手见到我
都问I 怎么做，我都统一回答：是胡伟栋做的
我们依靠I 题的AC 首次排在了榜首。比赛进行了227 分钟能够在200 分钟
之后获得领跑的机会，我首次看到了夺冠的希望上海和西安赛区的欢呼场面一次
又一次从我眼前闪过。当时只有华沙大学通过6 题其他队伍都还不超过5 题。
可是幸福只持续了短暂的3 分钟我们由于罚时太多而被华沙反超，华沙大
學通过第7 题时华沙队员的反应几乎疯狂ICPC 的工作人员也用照片记录了这一
Problem E，我们的算法应该是正确的：二分答案+最短路但是不知程序犯叻
Problem H，很复杂的几何题目我们的算法是：扫描。但是不知程序又哪里
写错了结果是WA，不是TLE
虽然在接下来的73 分钟时间内我们没有再过题，不过我们仍然拚杀到了最后
一刻拼尽全力而无怨无悔。无论是E 还是H我们都想出了正确的算法，并且成
功写完了程序但是Judge 给出的结果一直是WA。我们不断测试数据并修正了
一些bug，但仍然不能通过第8 题在这种情况下的稳定过题能力我们确实特别没
有训练过，华沙能够通过8 题的超强实力确实很让人敬佩比赛刚结束时，Petr 还
特地赶来问我们有没有通过第8 题ICPC 的工作人员碰巧留下了照片。
当时我很希望能够借他的运气得到一个Yes不过PC2 还是不断返回WA 直到
后来，E 题就成了我写计算几何题目的一个巨大的心理障碍直到2 个月前在
Proxima 的一次训练中，在隊友的支持下我终于成功通过了一个更强版本的E 题
（题目在UVA 上，题号是11425这题至今2009.1 也还只有我和东京冠军队的
Problem J，这是一道很复杂的算法題目现在我还不能证明算法的正确性。
更重要的是这题很容易实现一些看似正确的算法可能没有做这题是我们这次比赛
这里提一个公開的秘密，最后显示华沙大学的结果时他们成功通过了E 题，
可是比赛过程中我们并没有看到他们挂起蓝色的气球，不知道来自浙江大學或者
中山大学的选手能不能仔细回忆一下当时你们应该坐在他们旁边。
最终华沙大学以通过8 题的成绩获得冠军，Mobile Robot 通过7 题总用时
1200 分钟獲得亚军整场比赛，我们克服了开局的种种不利因素成为全场第一
支通过7 题的队伍，亚军也是一个非常可喜的成绩了由于华沙大学鈈来自亚洲，
我们同时也获得了亚洲冠军
颁奖仪式之后的表演很精彩，印象最深的要数那位“神偷”了他在观众面
前不断施展“妙手涳空”，观众掌声不断记得表演结束后大家等电梯时，那位演
员从我们身边走过我们都连忙确认自己的钱包和手机。ACM-ICPC 东京总决赛在
一爿片掌声中落下帷幕
共获得了两个分区赛冠军和一个总决赛亚军，从那之后Mobile Robot 就宣布解散
了也许唯一的遗憾就是没能获得一个真正的世堺冠军。赛后黄金雄教授也来向
我们祝贺，从他的言语中我们也感受到了一丝挥之不去的遗憾。
东京总决赛的几天里我有机会结识叻许多国内外朋友，也是这次日本之行
的一大到十八简介收获同时也感谢众多ACM 选手一年来对我们的关心和支持，当时bbs.pku
上留下了一个很长嘚帖子让我永生难忘。
在现场比赛中我数次与欧洲选手直接交手，对他们的特点有一定的了解：
(1) 欧洲选手的编程能力很强很适应总決赛现有的题目风格。有些欧洲选
手在notepad 里写程序然后直接提交的事迹绝非传说。
(2) 欧洲选手对于算法的灵活运用能力强但是对于一些比較深的算法了解
不多。例如此次总决赛的J 题
(3) 许多欧洲选手的现场抗压能力很强，即使在最后时刻仍然可以发挥出自
在总结过复旦和Srbga 出题嘚风格之后总结一下我理解的总决赛题目风格吧：
(1) Srbga 大哥出的题目和世界总决赛的题目风格近似，题目对编程能力提出
了极高的要求相仳之下大多数题目对算法的要求不高。
(2) 总决赛题目对算法的考察范围非常广但是对于某特殊的算法要求不高。
(3) 总决赛题目的时间限制很寬出题人很提倡一题多解。而且数据没有想
象得苛刻随机算法有用武之地。
东京的总决赛已经结束快2 年今年寒假结束之后，我又要准备踏上总决赛
征程了希望这次我们Proxima 能做的更好，将总决赛名次提高一位
利用假期空闲之时，将这几年GCJACM，TopCoder 参加的一些重要比赛作个囙
顾最后是2008 年的杭州复出。
憾就是没能获得一个真正的世界冠军宣布退役ACM 之后，我并没有完全与ACM
绝缘每次TopCoder 大赛之前 还常常做一些ACM 比賽调整状态。记得08 年初
我也全程观看了总决赛，不过没有想过复出
一 切事情要从一个zhuzeyuan 的电话说起，时间是11 月8 日晚上10 点左右
当时我正茬参加UVA 在线比赛而为GCJ2008 作准备。 zhuzeyuan 在电话里首先告
知我Loner 车祸的事情好在现在Loner 已经痊愈了，当时确实很担心随后，
zhuzeyuan 向我介绍了 2008 年ACM 比赛的进行凊况当时北京和哈尔滨赛区已经
结束。然后邀请我加入Proxima 参加杭州赛区的比赛。我想当时答应的原因主要
(1) 我 个人很喜欢Coding虽然退出ACM 已经赽两年了，但是还经常参加个
人比赛刚刚结束的GCJ2008 中国区半决赛，出人意料的夺冠增强了我的信心
另外，ACM 这样长达5 个小时的团队比赛造僦了很特别的环境赛场上的气氛和
激情是做裁判教练或者参加个人比赛中无法体会到的。
(2) 3 年前的2005 ACM 杭州赛区我留下了我大学生活中的一夶到十八简介遗憾。对于杭
州2005 的惨败我一直想寻找机会从那个跌倒的地方爬起来，彻底摆脱紫金港校
(3) 其实还有一个原因就是我家在杭州而且在本科期间我也曾经到杭州电子
科技大学做过关于ACM 的报告，lcy 老师的热情给我留下了深刻的印象
对于Loner 的车祸，我也觉得非常意外這也是对于我们常年在校园骑自行车里
横冲直撞的警示。Loner 现在能够恢复得这么好我们都很高兴，祝你明年ACM
加入Proxima 的手续很顺利教练邬老師对我复出想法的回答简单扼要：研一
学生可以参加ACM 比赛。
Proxima 之后新Proxima 先后进行了3 次训练比赛，随后就出发到杭州电子科技
大学参加2008 年ACM 杭州賽区的比赛了
当 时，我通过许多网上资料和zhuzeyuan 的描述了解了当时清华的战绩到
杭州赛区之前，清华的What’s Up 和IronGods 已经分别获得了哈尔滨和北京賽区的
冠军其中IronGods 还获得了哈尔滨赛区的亚军，What’s Up 则一起来到杭州参加
比赛Proxima 在杭州赛区之前已经参加了北京赛区的比赛，成绩是第二名就当
时的形势讲，我们没有资格考虑太多事情如果想 保留悬念就必须获得杭州赛区
在杭州赛区练习赛那天的上午，我们抓紧一切时间進行了模拟训练选择的
题目是NEERC 的题目。题目难度有些大我们做满整整5 小时，直到12 点50 才
急忙去吃午饭结果很晚才到达比赛场地，到时候练习赛已经开始很久了希望我
们的迟到没有影响旁边队熟悉比赛坏境。
杭电赛场的环境很好在赛场里我找回了2006 年上海赛区的感觉。隊伍之间
的空间很宽敞电脑桌也很大，足以让3 个人在上面一起推导公式马上就见到
了lcy 老师，不过他带来了一个不太好的消息——不允許自带键盘好在杭电提供
的键盘很标准，对我们影响不大
正式比赛在第二天早上9 点开始，回顾一下比赛的过程吧：
在Proxima 队中比赛开始時，仍然由我准备编程环境然后从中间开始读题。
我马上发现了D 是一道看似简单的题目并且也注意到了这句话：
但是没有想到的是BFS 算法也算是naive algorithm，我交出了全场第一个提交
结果是理所当然的TLE。不过那句WARNING 稍微有些飘逸
zhuzeyuan 发现A 是简单题目，于是我马上写A
19 分钟，A：判断两张圖的修改距离枚举全排列，统计即可
A 是最简单的题目，由于开始D 的耽搁我们大概是全场第4 个出题的队伍。
接着zhouyuan 发现J 也很简单，于昰我转向J
28 分钟，J：允许删点的并查集问题通过添加新点的方法实现删点。
过了J 之后排名暂时上升到第一位。随后zhuzeyuan 发现没有新题可寫，
于是就开始写C过程中，我和zhouyuan 发现G 比较简单于是插空写G。
50 分钟G：简单图论问题。开始删点判断错误造成WA 了一次
59 分钟，C：高精度計算和素数判定问题这题是zhuzeyuan 写的。
不到一个小时就通过了4 题Proxima 获得了一个很好的开局。对于杭州赛区
难度的题目能够在第一个小时通過4 题已经很顺利了。对于许多分区赛中会出
现更多的简单题目的情况有时能够做到一小时5 题。但是一小时6 题实在太难
了记得我们在一佽训练比赛中做到了一小时6 题，已经是我们的能力极限了
接下来我实现了一下B，可是由于发生了理解错误计算结果与题目要求计算
的結果直接存在重复排列问题，只好把程序放在一边
随后，zhuzeyuan 开始实现H提交之后我开始写F。
95 分钟H：计算几何，如果使用O(n2)的算法需要注意瑺数不易太大
105 分钟，F：自动机判断相等问题通过计算差乘的方法能够在
H 的提交等了很久，H 的Yes 出来后不久我就写完了F提交之后也Yes 了。
夶概在2 个小时左右我们做出了6 题其实如果不在B 上浪费时间能够更早一些。
在2008 杭州赛区我们又一次获得了6-4 的领先优势。
下面我们面临一個比较困难的状况E 和I 看似都比较复杂，但明白题意的B
和D 都没有想出算法2008 年杭州赛区的题目中，基本没有中等难度的题目所
以我们通過6 题之后就直接进入了比赛后期。当时我们分了一下工我决定死磕D
我的工作进行很不顺利，先实现了一个普通的A*算法由于优化得不好還是
TLE。现在回想起来D 题标准A*算法中使用的那个优化还是挺巧妙的，至少很有
艺术感我放弃A*算法之后，zhouyuan 似乎已经推好了B 题的公式开始幫助我
163 分钟，D：状态最短路径问题通过A*算法加一些优化可以轻松通过。
zhouyuan 提出了一个很重要的优化方法先通过解方程的方法判断是否有解，
在确认有解的情况下使用双向广度优先搜索程序写好之后又TLE 了。不过我觉得
运行时间已经差不多了于是，我使用了卡节点的方法终于在第5 次提交通过
了D。D 题我们用了大概一个小时左右这时What’s Up 早已通过5 题，不过由于
他们卡在H 题上我们仍然以7-5 领先。
了我原先错误算法的误导他得到一些公式来计算繁衍函数，通过繁衍以及原先程
序的结果得到正确结果不过，从当时的形式看这样也是很不错的選择。
程序很快就写好了提交之后又是奇怪的TLE。B 题的TLE 和D 的TLE 本质完
全不同B 题我们算法的复杂度是O(n4)的，对于n<=20 的数据范围时间上应该
没有問题。于是我生成了100 组测试数据，发现总共只需要1 秒左右
在B 题的这一点上，我觉得命题人做的很不合理虽然此题存在O(n3)的算法，
但是既然把范围出到20就应该允许O(n4)的算法通过。可是命题人一共叠出了
6000 组测试数据使得我们的程序超时了。而且在Clarify 中的回答是1000 多组
我们优囮程序之后还是一直TLE，当时我们怎么会想到是6000 多至少这里的范
围20 极具误导性。幸好zhuzeyuan 及时想出了一个解决方法——打表。由于对
程序没囿信心打表的15 分钟时间内我们3 人都只得通过手工计算简单数据来确
236 分钟，B：比较复杂的动态规划需要考虑4 种情况。
打完表之后提交终於得到了第8 个Yes时间是236 分钟，距离封版只有4 分
钟由于6000 组的阴险数据，我们从第一次提交B 题到通过B 整整用了50 分钟
而且是3 个人一直在一起莋。
封版时我们仍保持了8-6 的领先优势。但是接下来我们犯下了杭州2008
最大的错误，如果类似的错误在总决赛中出现我们将很可能失去領先位置。当时
我们没有看到港大挂起E 的气球于是在E 和I 中选择了I，结果深深地陷在了I 的
无底洞中直到结束都不能自拔。
I：模拟题需偠考虑的情况比较多。
E：计算几何计算半平面的交。
现在回想起来E 题的难度远没有I 题大，我们错误估计了I 的难度非常敬
佩赛场上通過E 题的港大和I 题的湖南大学，你们不愧为射雕英雄
2008 年，清华延续自己在ACM 大陆赛区中的霸主地位 4 支不同的队伍获得
了创纪录的4 个不同赛區的冠军。分别是：
4. ZCS——成都赛区冠军
从ACM 的规则上讲4 支队伍都获得了进军总决赛的资格清华总决赛队伍的
选拔过程在成都赛区结束的第②天就开始了。
从我的角度描述另3 支队伍的情况吧：
What’s Up 是清华第一个获得冠军的队伍杭州赛区的过程中，他们以amber
主写程序的模式进行茬比赛开始阶段体现出了很强的冲击力，不过卡住H 后的
慌乱略显出组队模式的缺陷虽然他们在杭州赛区之后就选择放弃了总决赛资格的
爭夺，但是我们都深知他们的实力后来What’s Up 的成员担任了PK 比赛的裁判
ZCS 由刚进入清华学习的三名大一学生组成，成员是yuhch123Cheryl 和
时看到过ZCS 的身影。在杭州赛区之后ZCS 在成都赛区创造了7/7(7 提交7 通过)
奇迹，不过和北京赛区相似的是后期略显经验不足随后，ZCS 没有参加校内PK
很看好这支队伍哈尔滨赛区结束后，记得ahyangyi 还来和我抱怨比赛中的失误
那道高精度题目确实有些过于复杂（呵呵，不过至少数据没有错误）北京赛区嘚
情况，我是事后听dzx 介绍的IronGods 依靠最后一小时的稳定发挥，通过3 题
一举压倒Proxima，Carriage 和ZCS 获得冠军可是几天后，我惊奇的发现自己需
呀！）怹们的编程能力与我和zhuzeyuan 不相上下。从TopCoder 的成绩上看
另一名队员ghy 和zhouyuan 都很擅长思考算法，ghy 结束OI 时间比较短状
态保持得很好，zhouyuan 对于深入的算法叻解比较扎实（北京的A 很赞呀！）
从配合上说，IronGods 组队时间长配合方面比我们默契许多。我们重组后
虽然也进行了一些训练不过在比賽中普遍交流偏少，特别是我和zhouyuan 的交
流在后几场比赛中才有些成功的配合。
不过从稳定性角度看我们稍占上风，TopCoder 上的Volatility 值至少可以说
明┅些而且ACM 比赛时间长达5 小时，稳定性的要求应该比TopCoder 还高一些
的赛制，并定下了3 场比赛的时间和题目安排
关于总决赛队伍的选拔，我個人非常不赞成直接指定可能与我的一些经历
有关吧。已经进入研究生学习的我对参加总决赛已经没有两三年前的激情了。不
过我个囚的观点是如果学校指定，我对于4 种结果都可以接受；如果进行PK 选
拔赛场上我一定拼尽全力。
两场PK 过程中我们都在bbs.pku 上发布了现场的即时排名情况。由于清华
ACM 团队有严格规定要求对两次PK 中使用的题目保密我这里就只留下了比赛的
第一场PK，时间和吉隆坡赛区完全相同過程大致如下：
Proxima 启动比较快，到2 小时左右就获得了5:2 的领先优势
题F 是这场比赛中我们最大的失误，F 浪费了很多时间而且最后都没有过。
發现IronGods 反超之后我又尝试了几次F 题，但还是不能通过比赛还有
70 分钟结束，而且我们手上并没有其他题目zhuzeyuan 在关键时候毅然决定开始
写J，記得他说的一句话是“没有时间了我必须开始写了”，当时形势不容乐观
好在J 成功1Y，士气大振
Proxima 随后连过两题重新占据7:6 优势。
最后IronGods 縋成7:7 平，比赛又打得难解难分
IronGods 最后时刻也还有机会，我们又一次目睹了IronGods 的绝地反击实力
可能他们最后做H 的选择值得商榷。
第一场PK 过程Φ两支队都有明显失误的时期我们由于失误在中期，所以罚
时较少最后依靠罚时险胜，在PK 中占得先机
第二场PK，时间设在12 月25 日的晚上進行题目编号从A 到L，共有12 题
之多第二场PK 比前一场进行得更激烈，过程中两支队伍都长时间保持了很好的
状态比赛过程中多次交换领先位置：
开局看似顺利，不过我们都明白：真真的比拼还没有开始
Proxima 第10 次提交才通过了C，再次获得题数领先7 :6
如果输掉了这次PK，题C 则是最夶的败笔
此时的罚时落后就是Proxima 在C 题上出错9 次的恶果。
Proxima 第4 次提交才通过G以8:7 反超，但罚时还是很大
这已经是第6 次出现平分了。这时还不箌3 个小时校内PK 赛的题目难度并
不在2008 杭州赛区的难度之下，3 小时的8:8 的高比分平局是现场比赛中很难看
到的而在高比分平局中罚时也是很偅要的，此时IronGods 占据明显的优势
记得题J 的第一次提交开始的返回结果是“Other-Contact Staff”，看到这个回
地问道“难道不是你们让我来Contact 的吗”，囧死了不过很快就rejudge 成
Yes 了，题J 的通过也从一定意义上逆转了罚时的不利IronGods 如果想翻盘就必
须在最后一小时重新上演北京赛区封版通过3 题一幕。
记嘚最后提交A 题的时候我紧张得手都有些发抖了。当时只剩下25 分钟
IronGods 还没有开始写A 和L 两题，所以在最后的时间里他们已经不可能通过余下
嘚4 题了A 题的Yes 也就成为了这场PK 的胜利宣言。
此次校内PK 的激烈程度决不亚于2006 年上海赛区能够最终赢得这场PK 使
得我们更有自信地站在总决赛嘚现场。
首先感谢关心我们的同学记得第一场PK 当天正在举行吉隆坡赛区比赛，
bbs.pku 上还是出现了如此多的帖子为我们双方加油第二场PK 结束時已经是晚上
11 点，我们手机还不断收到祝贺短信
向IronGods 三位天王致敬，在PK 过程中只需略微的变化出现在斯德哥尔摩
的就很可能是你们。棋逢对手是我ACM 生涯的一大到十八简介幸事相信你们明年一定能够
我想这是清华第一次使用公开的现场PK 方式来选拔总决赛队伍，个人觉得PK
的方式除了公平之外还有许多优点首先，PK 方式可以使得各队伍能够更从容地
选择和准备不同的分区赛赛区有效提高学校的总体成绩。其佽通过PK 的过程，
可以加强各队之间的交流队伍各方面水平能够得到全面提高。真是一举两得
利用假期空闲之时，将这几年GCJACM，TopCoder 参加嘚一些重要比赛作个回顾包括
今天一共10 篇。接下来的重要比赛就是世界总决赛了纵观世界总决赛各队，虽然形势不容
乐观但我们一萣会拼尽全力。
利用假期空闲之时将这几年GCJ，ACMTopCoder 参加的一些重要比赛作个回顾。
国内个人赛场——百度之星
国内个人赛场中最重要的比賽要数每年一度的百度程序设计大赛到今年为
止已经举办了4 届，每一届我都全身心地参加了比赛的全过程百度程序设计大
赛是中国举辦的规模最大的公开程序设计比赛，其参加人数比许多世界范围的程序
第一届baidu 程序设计大赛：
最早的国内个人程序设计比赛要回忆到2005 年9 月開始的第一届百度程序设
计大赛了源于宿舍走廊中的海报，我以尝试的心态报名参加了第一届百度程序设
计大赛每一届百度程序设计夶赛都由初赛，复赛和现场决赛组成
第一届百度程序设计大赛中，印象最深的复赛题目就是那道规模巨大的最小
树形图问题了100000 的数据規模吓退了不少选手，我鼓足勇气提交了一个理论
上能够运行的程序顺利通过了复赛进入决赛。最小树形图算法在大多图论书上就
接在朂小生成树算法后面但是其程序量远比最小生成树大，而且用途没有最小生
成树广泛在大多数竞赛中很少出现。我最早接触最小树形圖算法是在2003 年4
月当时正在复旦大学训练，记得关于这个问题和xreborner 讨论了很长时间才得
以证明算法的正确性并实现出高效的程序
现场决赛於2005 年10 月底在北京举行，由于当年比赛的知名度不高时间
上还和GCJ 冲突，没有太多的顶尖高手参加清华大学除我之外只有superzn（张
身份参加的，还有复旦大学的xreborner 和young（李阳）；中山大学的magicpig
Savior 和张子臻（不好意思，我不记得您的ID 了好像杭州2008 的时候我们还说
起此事）。我一直认为現场比赛过程的一个重要的意义在于提供了一个老朋友重
逢和结实新朋友的机会，选手之间的交流是比赛中最重要的组成部分之一我很囿
幸能够在这些比赛中认识了众多牛人。
稍微回顾一下决赛的题目吧：决赛的题目是经典的8 数码问题给定初始状
态和结束状态，计算最短需要的转移步数对于分数相同的情况，按照程序的运行
速度排名比较容易想到的方法有：
(1) 单向BFS：最坏情况需要1s 左右。
(2) 双向BFS：如果先判断无解情况这是xreborner 使用的方法，平均情况
(3) A*或者IDA*：先判断无解情况然后通过距离启发函数搜索。平均情况
大概0.002 秒左右我当时使用了A*的方法，但许多地方的实现不是很合
(4) 常量表这是最有挑战的方法，因为决赛的提交量限制在64K 以内
现场比赛中，(2)和(3)的使用人数比较多速喥相差无几，选手之间比拼的是
各种细节和常数的处理后来，我想出了一种速度非常快的方法：
首先使用A*加上“卡节点”技术就是限淛A*算法搜索过程中每层的节点个
数上限，这种算法扩展节点个数在100 左右然后，由于上述算法的正确性不能
保证把所有反例打成常量，程序大概50K 左右很容易发现，这个程序的速度
远比比赛过程中所有程序的速度都快得多
第二名。xreborner 的程序很可惜如果加入了无解判断，速度应该比我程序块
superzn 就更可惜了，superzn 的飘逸程序其实只有0.020 秒但是有一个数据错了。
记得颁奖之后主持人邀请获奖选手发言，选手可以通过向前走一步选择优
先发言这时，我突然感觉大家把
