搬家咯！！！请访问以下网址：

我的ACM故事(6)

亚特兰蒂斯征途（下）：帝国归来

———— 记!Atlantis!的GDCPC2006

1、赛前篇

前文再续，书接上一回。

上回说到 !Atlantis! 在预选赛时历经沧桑，受尽磨难，过程颇为不顺，但最终依然受RP照顾，创造了奇迹，保住了三甲。同时，坚信 !Atlantis! 会在省赛时再创奇迹，让失落已久的帝国复苏。此等重任自然地扛在了我们的肩上。

五一刚在中山鱼肉别人，回来马上就要被别人鱼肉了。休息不到一星期就省赛，状态真的有点不适应。一周没做题，手感全无。而我们队的队宝bug也在比赛前夕来了个重感冒，雪上加霜。正所谓每个王朝的背后都有一个伟大的做题手，bug魔王要是倒下了，我和Aesop是撑不住的。还好比赛当天bug依然活蹦乱跳，生龙活虎，这才让我们放下心来，准备迎战。

2、题目篇

闲话少说，直入正题。先简单介绍一下比赛的10道题：

A、大水题，略。 3Y by bug

B、 超经典的L形覆盖，代码只需5行。 1Y by RC

C、 由于被肥哥搞事，大家都以为是BT题。实际上只是一道普通的搜索题，搜索量并不大。 2Y by bug

D、蛇形覆盖，程序设计的基本题…… 1Y by RC

E、 bug说的“很简单的DP”，结果全场就3支队过=,=  3Y by bug

F、  本次比赛最难的网络流的题目，但被人水过了=,=。没有做。

G、构造题，三人齐齐想，最后AesopRP高，顺利水过。 1Y by Aesop

H、简单计算几何，但由于PI精度问题害了不少罚时。3Y by Aesop

I、   普通的模拟题，题目描述有点烦。一直WA到比赛结束……55555……

J、   最短路，经典的Bellmen-Ford，但由于bug在题意理解上出了点问题，结果浪费了不少罚时。3Y by bug

3、比赛篇

今年真的多了不少新花样，比赛开始前还有倒计时呢。比赛开始后，按之前的计划，bug读前面ABC，Aesop读后面HIJ，我从中间DEFG读起。肥哥那题对我们的诱惑并不大，一开始并没有受那题影响。我先把D读完了，感觉是水题，规划的时候bug已经上去敲A了，看来更水。不过bug昨天重感冒，而且没有试机，今天不知道还是不是信得过的产品，更何况bug平时不会这么冲动的……担心ing。担心之余继续规划D，争取在bug过了A后就能上去敲这题。

D才想没几秒钟，bug就说可以交A了，快得离谱。真的有那么水？作为队长，觉得很有必要看看他的程序先，昨天没有试机，不知道会不会漏了文件输入呢？不会吧，bug应该没有那么水的。不过还是看看吧。结果我一瞅屏幕——果然没有文件输入！！我连忙大呼：“文件啊——” 话未落音，一个框框就已经弹了出来——就是那个可爱又熟悉的submit成功窗口……

第一次提交就拿到了TLE，难得。bug加了文件输入后，马上又交一次，换我上去做D。D没敲多久，A题就返回了——结果居然是WA。惨了，bug今天状态看来真的有点不佳。还好bug改得快，第三次提交终于YES了，但在罚时上真的亏大了……第一道水题就如此，有点打击士气。

后来我敲D时没有规划好，写到一半写不下去，而此时Aesop说H可以敲，就先把机子让给Aesop敲H，我退下来继续规划D。看一下Rank list，发现有队过B了，就问bug B题怎样，bug却说不太会做，和Aesop讨论过也没有什么好想法。问了一下题意，我晕，这不超经典的L形覆盖吗？中学时就看过……快速地遍历一次我的大脑后，想到了好像是和(n*m)%8有关。Aesop的H WA后换我上去敲B和D，B很快敲完就交了，很顺利地拿到了第二个YES。D题重新规划后思路也很清晰，很快也过掉了。此时我们三题，但因为罚时问题，排名并不太前。看来今天要靠题数了。

接下来的分工是bug做J，我帮Aesop找H的bug。bug的J交得很快，也WA得很快。bug认为是题意问题，clar了一下后，judge理直气壮地叫bug认真读题。“看来judge对这题的描述很有信心喔！”自言自语后，bug找到了J的一个大bug，改了之后再交，还是WA……完了，bug今天果然失水准。Aesop的H找了不少bug，改过之后交第二次，还是WA……而这时我叫bug按另外一种理解改了J后再交，终于拿到了YES……Aesop的H提高一下PI的精度和实数判断的精度后，提交，YES。5题。此时名次算是比较靠前了。

I题描述很烦，但因为有队过，我只好硬着头皮把它读完。后来觉得是可以做的模拟题，于是便开始构思。bug在Aesop改H的时候看完了E，说是“很简单的DP”，想扔给我，但我更偏好模拟题，而且算法题一向是bug的，就又推回给他。然而他却说：“这道根本不算是算法题啦，很水的DP来的……”（听到这句话后想K他的人请re此文，我为你们准备机会——作者注）接着bug就上去写E了，Aesop看G，我继续想I。bug又是很快敲完E就交了，又是很快就WA了（今天bug的coding异常的快，但正确率却异常的低）。此时我的I规划得差不多了，我就叫bug先退下来冷静地想一想，换我上去敲I。

I题敲了一段时间后，我们队的红色气球突然爆了，吓得我的心扑通扑通的跳，许久不能平复，程序也越敲越乱。Aesop的G似乎找到了构造的办法，于是就先让他上去敲，我退下来再好好想I。Aesop的办法并没有证明，但却很有信心可以水过（或许是因为有支队很快就过了G而且是1AC的吧）。结果就真的水过了，爽啊！士气突然就上来了，而我也坚信我的I题最后一定能够出来。此时我们队7题，暂时排名第一，直到封board后还是只有我们一支队7题，看到夺冠的希望了。

I题又敲了一段时间后，提交之，WA。bug和Aesop经过热烈的讨论，决定用暴搜+const的办法把C解决掉。然而我们似乎慢了一步，我们左前方已经有支队把这题切掉了，拿奖品的愿望变成泡影。但却更让我们坚定了过C的信心，于是便换bug上去写暴搜的程序，写完后让它运行，我继续上去敲I。

I题再敲了一段时间后，又提交之，又WA。此时C题的暴搜程序已经run完了，bug把结果const后满怀信心地提交，结果却返回WA。bug很快发现了自己暴搜程序的bug，第N次把我赶下来，改好后一run，居然不到1秒就出解了，真快！const一下再次提交，YES！8题！全队都兴奋起来了。再把I题切掉，9题就稳拿冠军了！看一下pc^2，离比赛结束还有20分钟……

4、最后20分钟 

       “过了这题，我们就夺冠了。”

整整20分钟，这句话都一直在我的大脑里徘徊。

每次提交，我都希望能弹出一个YES窗口。

只剩下5分钟的时候，我期待着我的RP再次爆发。

我开始想象如果弹出一个YES后我们队的兴奋程度。

比赛结束了，还有2个值得期待的submit没有返回。

“别担心，我一向都是最后才爆RP的啦。”我这样对自己说。

第一个返回了。Wrong Answer。

第二个也返回了。同样，Wrong Answer。

我的视野开始变得模糊起来……

我对不起队友，夺冠的任务，我没有完成……

我的ACM故事(5)

亚特兰蒂斯征途（上）：相信奇迹，相信RP

———— 记!Atlantis!的06中大预选

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：？  }

  ( to be continued...)