我的ACM故事(5) 亚特兰蒂斯征途（上）：相信奇迹，相信 RP —— 记 !Atlantis!的 06中大预选

1

上周才刚刚告别05赛季的集训队，这周就马上开始ZSUCPC2006的预选了。回忆起去年的ZSUCPC2005，仍然感觉很近很近。不觉间，我的ACM故事也已经写到第5篇了，真是感慨万分啊。

今年，我们哈根达斯原班人马再次倾情出动，在讨论新队名的时候，否定了!Haagen-Dazs! Pro（哈根达斯专业版）和!Haagen-Dazs! SE（哈根达斯II：加价不加料）等名字后，决定脱胎换骨，雪糕销售商摇身一变，变成一个传说中的失落帝国——!Atlantis!（亚特兰蒂斯）。从此，我们正式踏上了去往亚特兰蒂斯的征途——又一个追梦的历程。 

2

征途第一站是预选热身赛。在预选之前，我们只拿了这个热身赛来做组队配合练习。可惜结果并不如意。此时不禁让我想起去年，哈根达斯刚成立后的第一仗就打得相当出色——取得了汕大OJ某次比赛的第一。那次比赛的名字叫“Lead us to a good beginning”。结果就真如那名字一样，极大地鼓舞了我们。从那以后，哈根达斯就一直春风得意。

似乎这次亚特兰蒂斯要吃点苦头了。由于热身赛第二天就是预选了，不能让它影响心情，于是三人都参加了凌晨1点的SRM。结果热身赛失意的bug在SRM中重夺RP，取得了所在room的第三（DIV 1），由于这次是有M的，所以bug又有$$进帐了。羡慕啊……

我就没有这么幸运了。这次DIV 2的题可谓是相当简单，而我的coding却突然出奇的慢，结果coding phase结束后我才排第5，拿M愿望落空。本来已经够失落了，没想到SYSTEST后居然Fail了250，原因是打错一个字母，狂ft……Fail了DIV 2的250真是相当丢脸……那晚就在这样忐忑不安的心情下睡着了。

3

准时11点起来。此时志荣发短信来说已经在吃饭了，于是原定的聚餐就取消了，各自吃饭后再集中过去。后来bug没收到我的短信，结果要自己一个人吃面，当时真是感到挺对不起他的，这队长也当得太差了……@_@

后来一起走过去的时候，bug定了两条总方针，第一条是“一定不要拿第一”（看来是去年BG怕了），第二条是“最好能保住三甲”。后来我觉得这样的方针不利于调动团队积极性，于是就改成“最好不要拿第一”和“一定要保住三甲”，感觉这样比较鼓舞，于是就这么定了。

比赛开始前又是到处闲逛，吹水。小熊找sniper打赌，看谁能最快出第一题，赢的要BG，我也跟着凑热闹。后来比赛又要推迟，不过才15分钟，比上年好，不用那么郁闷地斗扫雷了。不久后比赛就要开始了，由于只顾吹水，没做好心理准备，突然感到一点紧张……

4

       为方便叙述，首先介绍一下各题：

A：给你两组字符串，要求找出在第一组而不在第二组的字符串的个数；

B：求几个区间的所有数的和，采取b进制无进位加法；

C：给出一个关系集和变量之间的关系，问你里面是否存在冲突；

D：给你一个含通配符?与*的字串，问你另一组字串中能表示成该串的个数；

E：给你n个字串，将这些字串连接在一起成为新的长串，求这样的长串中字典序最小的那个；

F：求[1..n]中与n的最大公约数不小于m的数的个数

G：太水了，略

5

比赛开始后就分题各自阅读，他们两个各拿一份打印版，而我则在电脑上看题。很快地，我发现了G题是水题，正开始构思时，发现小熊已经开敲了（他们坐我们前面的前面，sniper坐我们旁边）。不能输给他，于是我也立马开始code了。还没敲完，就听到前面一声“Yes！”，不愧为是新一代水王小熊啊，才6分钟武当老柴就过题了。两年都是他做出第一题，不爽……我似乎受昨晚影响，敲得比较慢，过G的时候前面已经有6支队左右了。由此可见我又忘了HQM老大的话了，比赛时不应该想比赛前的东西的。{ RP：normal }

 后来好像是志荣上来敲E，我则开始看其它题。很快地，前面又一声欢呼：武当老柴过第二题了。感觉有点被牵着走了，郁闷。后来得知过的是志荣手上的E，就放心交给他继续code了。结果却意外的WA了。于是我便过来问一下算法，志荣说把字符串排序一下就行了，我却觉得有反例。志荣说是bug提出来的，我看bug挺肯定的样子，就没理算法了，帮志荣看会不会写错什么或有trick。当时担心是scanf的问题，改成gets，还是WA；以为字符串可能含空格，再处理一下，还是WA……全队RP骤降。{ RP：low }

WA了3次后，过2题的队已经很多了，武当老柴在又一声欢呼后也3题了。而这题其它队都很快过的，我们的罚时可真是浪费了……无奈之下，只好暂时放下这题，让bug上去敲D，我来看武当老柴过的第3题A。{ RP：lower }

bug敲完D后，发现样例好像有错，于是去问评委。得到了肯定的答复后，bug就叫我把D交上去。结果在评委宣布改D题样例数据时，我们已经过D了。刷新一下排名，名次已经很后了，但由于有D的优势，而A、E都是水题，追回三甲还是有希望的。幸好我们被题卡住时能够及时放下，否则可能会卡得更惨。{ RP：normal }

bug过D后我就上去敲A了。用STL很快敲完后，交上去居然又WA了。看来这时RP真是太低啦。重新读了一会题，以为自己理解错，按另一种理解敲完交上去，还是WA。后来发现原来的理解是对的，错在哪里就变得莫名其妙了。郁闷了一会后，bug指出了我用map的一处错误（当时感叹：STL没学好啊），惊喜地改过来了，结果还是WA……崩溃……又暂时放弃A了。{ RP：lower }

此时武当老柴、Encore和Entropy都4题了，我们还是2题，我的A和志荣的E都被卡住了，还找不到错，真是超级郁闷……{ RP：lowest }

后来bug上去重写E，准备再次提交时，我叫他们再好好想清楚。幸好在我这个队长的英明指导下，志荣很快找出了反例，证实了bug的算法是错了，原来志荣一直被bug误导了……bug面壁的同时志荣用搜索重写了E，结果一交，AC。于是bug又欠我们一顿BG了。{ RP：low }

RP理论真是不可思议。在志荣过E没多久，我马上注意了A题的insensitive。其实之前我也读到了，只不过像胖仔等大多数人一样，习惯性地以为是对大小写敏感。最FT的是我当时还问bug那个map是不是区分大小写的呢。此时让我看到了该死的“in”，加上这个处理后，A题总算过掉了。真没想到会有如此不细心的时候……该好好反省。{ RP：normal }

此时我们4题了，RP回升了一点。但因A、E浪费罚时太多（尤其是E，别的队都很快过），排名仅在第6、7左右，拿三甲变得非常困难。此时志荣看B，我看F，bug主要看C，但也会帮我看看F。     { RP：low }

后来志荣上去敲B，我则继续想F。不久后志荣写不下去了，而我则想了F的一个不成熟的搜索算法，为了充分利用机时，就先上去敲了。志荣和bug则一起攻B。我由于之前没想清楚，敲得很慢，结果连样例也过不了。调试一段时间后，过了前两个样例，但最后一个仍然过不了。郁闷……我又犯了去年4+2的错误，还没规划好就上去敲了，这样很容易造成思维混乱。  { RP：lower }

好长时间我们都没有进展，Entropy居然6题了，Encore和武当老柴各5题，我们还是4题。由于罚时多，要拿三甲一定要出多两题才行。时间非常有限，出两题可是相当困难了……  { RP：lowest }

离比赛还有一个小时左右，右上角传来一声惊人的欢呼，接着便看见Entropy全体起立，收拾东西：原来他们已经做完7题，收工了。无语啊……原本已经脆弱的心灵再次受到打击……RP已经跌到最低谷了。{ RP：lowest - }

志荣好像忍不住了，把B交给bug后，问了一下我的算法，觉得很有问题，但此时bug写不了B，于是我还是硬着头皮上，结果还是徒劳。此时除了Entropy全过外，Encore也过6题了，武当老柴5题排第三。时间只剩下半个小时了，过一道还是有希望的（B题已经有想法了），但过两道似乎接近Impossible了……{ RP：lowest --  }

后来bug规划好B便上来敲了，我继续下去想F。志荣对我的方法提出更多的质疑，我也打算放弃了。此时即使有新的更好的算法，也没时间实验了。郁闷啊，保不住三甲了……虽然HQM老大曾教导过比赛时不要想比赛后的东西，但我还是不可避免地想象假如保不住三甲，而且还输给第一名两题的话，对我以及我们对会是怎样的一个打击……怎么会有这样的事情发生啊……我无法接受。我的RP呢，什么时候才来拯救我？？   { RP：？  }

6

奇迹开始发生了。

在bug敲B的时候，我突然翻到了数论书上的一个定理，那个定理似乎对F极有帮助。此时的我开始紧张了，连忙告诉志荣，志荣拿了几个数据来试，却得不到正确结果。此时志荣似乎已经完全不敢奢望6题了，只想bug过了B有5题就够了。但我却不死心。我深信那定理是有用的，虽然反例摆在面前。我的执著证明了我是对的：志荣记错了欧拉函数。经过再次验证，该定理确实是有用的。F题的希望来了……

看一下时间，15分钟。bug在调试B。虽然已经知道F的定理，但仍需要一定的coding时间。要想拿6题，除非bug在5分钟之内过了B，然后5分钟敲完F，3分钟调试，2分钟提交。这看起来似乎有点天方夜谭，但我坚信impossible is nothing。我内心的血液已经开始变得澎湃起来。

奇迹看来真的发生了。bug的B过样例后，向我们要数据，我叫他直接submit好了，不管罚时了，时间宝贵。结果居然一次AC了。此时时间还有12分钟。关键时刻，咱们的bug还是靠得住的！

接下来就完全看我了，内心可是多么的紧张和激动啊！敲键盘的手都在抖了。幸好关键时候我的coding也是靠得住的，很快敲完之后，看了下时间，还剩7分钟。赶紧开始调试！！把样例一贴，全错—_—。此时还有6分30秒。调试了一段时间后，时间剩下4分钟，样例还是一个不过！！但找不到错了啊……我更加紧张了，鼠标都抓不稳了！

3分钟的时候，我突然发现我在深搜的时候打错了一个数组下标！！把深度变量d错打成了循环变量i！！晕！！这个bug也太夸张了吧！！但找到了就是好事啊。把这个改过来之后，运行，过样例！！！此时bug和志荣似乎也兴奋起来，马上叫我：交！！！

我稳定自己的情绪后，对着VC++，按下Ctrl+A，再按Ctrl+C，再用鼠标点到F的提交窗口，按下Ctrl+V，输入密码，然后把鼠标移到Submit按钮，轻轻按下……

Submitting.......

我们三个都屏住了呼吸……希望能看到绿色……结果却是红色的……而且还是W开头……惨了……

后来发现是Wating，我FT。关键时刻，怎能Wating？再刷一次，还是Wating。再刷一次，又是Wating。喂，别开玩笑啦……刷第四次后，终于不是Wating了，但却是另一个让我们吓了半死的Running……惨啦，我的程序复杂度真的很难估计，该不会真的TLE了吧，如果TLE了那就要死心了……

最后再刷一次……此时已经不是红色了！！而是绿色的Accepted！！！我当即忍不住拍桌尖叫，我们全队也都沸腾起来了！！我们相互击掌，相互拥抱，那可不是一般的兴奋，而是相当兴奋了！！！这种感觉，19年来只在GDOI2003和去年的预选赛上体验过……用亢奋来形容也不为过。

后来武当老柴也帮我们鼓掌了，此时剩下2分10秒，我们保住了三甲，也保住了东校区第一。接下来的时间里，我都一直处于兴奋状态，一直持续了好久，好久……

7

       比赛最终还是保住了三甲，成绩还可以接受。总的来说，我们队继承了哈根达斯的优良传统，整体配合还是相当好的。这次暴露的主要问题是读题还是不够仔细、思考问题不够谨慎，以及作决定时过于仓促。这体现在A、E题的罚时，以及F题浪费的机时上。

       比赛完后的FB就略去了。唯一值得一提的是，如果最后没有保住三甲，恐怕我也没什么心情FB了。如果只有4题，那就更痛心了。这次的反差真是相当大，比去年还大。虽然去年也是前面很郁闷，后来很兴奋，但今年的郁闷程度是比去年要大得多的。尤其是在最后半小时，要想保住三甲，还要再过两道题，而那时的F还没找到公式，bug的B还没完全规划好。在当时看来真的是不可能。

       我也无法解释清楚，为什么去年和今年都发生了最后爆RP的奇迹。小熊曾经开玩笑地说过，我总是会在最后爆RP的。想想好像是，去年的预选赛、省赛以及4+2都是例子。但遗憾的是，这种事件却未能发生在最重要的成都赛区比赛上。我不知道那会不会是因为那时最后的G不是我来敲的，我只知道RP这东西与奇迹一样，都是可欲而不可求的。

我们不能依赖RP，而要努力拥有真正的实力。但在你比赛失意的时候，在你即将灰心、即将放弃的时候，不妨相信奇迹，相信RP。

最后，我坚信，亚特兰蒂斯会在省赛再次创造奇迹的。失落已久的帝国，是时候苏醒了。

分类： IT竞赛比赛 培训考证