ACM 校预选赛记

又是好久没有写东西了，算算时间隔了六天了吧。按我以往的速度，都能产出两篇了。我在弄 ACM，荒废博客的打理那是好孩子的行为。我想说这些天我很有感觉，很有过劳死的感觉，某天晚上做完题感觉头晕眼花的。和师兄组队之后很有压力，感觉不把师兄留下给我的 Sicilly 习题全做完就可以自杀以谢天下。可是一直做到前天，还是有两道图论的题目死活做不出来，我很郁闷，不过不管怎样，我们昨天下午去参加比赛了。

比赛前的上午在复习以前做过的 Sicilly 题目，把 DP 等等都再看了一遍，甚至还有空在 Sicilly 上看到我有道题 (Catch the thief) 的效率竟然排名 20/60，很是感动到我了。看完后抓紧时间睡觉，从差不多十一点睡到十二点，起床收拾一下东西就去吃饭去实验室。

我们的比赛地点是在 B401(好熟悉的教室，实验课和数模都在这里呆过)。这源自于我们报名报得晚，我们的队号是 163，也就是第 164 个报名的队伍。结果安排教室安排不下来只好让我们去 B401 了。我们约好在 B301 门口碰面（以前没见过蔡师兄）。差不多一点了，比赛时间就是 1 点开始，吴师兄匆匆跑来，发现就只有我一个在那里看太阳，说时间不够了我们先上去吧，然后找我要了张纸，写上几个大字：“蔡，我们在 B401。” 把纸往墙上一贴，我们就钻上 B401 去了。

上到 B401，却发现了蔡师兄已经在里面了，唉唉浪费了我一张草稿纸。我们赶紧坐好，紧接着比赛就开始了。发好题目后，蔡师兄看 A 题，吴师兄看 B 题，我看 C 题。几分钟不到，蔡师兄说水题，斐波那契，于是就敲代码去了，再过了一会儿他说 AC（Accept）了，我大惊，我看的 C 题还没看完理解透，我暗想这次比赛我真的是看客了，让两个大牛师兄充分地发挥吧（真是不知道什么滋味）…

C 题虽然很长，两页纸，还充满了中国人写的单词，这是个玩纸牌的游戏。我想说我好多单词看不懂，可能是很久不做考研阅读理解的缘故，把 Discard 和 Play 弄了好久才明白是哪里不同，但是理解完后原来是个模拟过程，写代码就很轻松了。接着我上去敲 C 题，两个师兄在旁边讨论 E 题。敲了好一会儿我也敲完了，师兄帮调了一下测试数据也过了，我按不住就提交了，尽管师兄在旁边惊呼：“别！” 原来我忘记把测试语句给删掉了唉，结果被罚了 20 分钟。删掉测试语句再提交，竟然超时。回头检查一下原来是某个变量忘记初始化（我感觉我好弱智），初始化后再提交，就 AC 了。

我接着看最后一道，D 题。矩阵切割问题，数据量好大好大，30000*30000，用普通比较的话必然超时，想了一会儿都想不出用怎样的结构去处理，算了我看 F 题吧。看啊看啊，看不懂说什么意思，我很郁闷。不过后来听说没有一个队做出这道，嗯嗯还好。然后我跳到去做最后一题，H 题。这时候吴师兄在敲 E 题的子串问题了。

H 题说的是一个平方数的问题，题目是这样的：定义一个数是 K-OSN（K 是偶数），那它符合以下: 第一，它是一个平方数；第二，它不小于 10^K；第三，它的最末的数字不是 0；第四，如果去掉最后的 K 位数字，它还是一个平方数。给定输入 K(2<=K<=200)，请找出符合条件的最大的 K-OSN 数，并输出 K-OSN{5f7b659ff3b2818cd787bc9e2e970b98d3e4ece1905bf98c409dc266242d6105}2009 的数值。我证啊证啊，终于弄出了这个 K-OSN 是什么东西，当然因为它很大，要做高精度求余，我又没做过，还弱弱地问师兄 200 位的数字做求余会不会超时呢，不过师兄很厉害，一边跟我解释一边三下五除二写完了高精度求余。我看着屏幕，啊？写完了？才半个屏幕左右的代码，简单测试了一下样本数据，提交，又 AC 了，这时候离比赛结束不足半小时了。赛况的 standing 也停止了更新，我们做对两道题的时候是 39 名，做对三道题的话应该排名会更高一些吧。

接着师兄们继续弄 E 题，因为老超时，数据量实在太大了，O(N) 的复杂度也要 1000W，但是不可能少于 O(N) 的，所以要异常小心才是，不过可惜的是尽管我们提交了 15 次，每次都超时唉唉，最后还是没过，于是比赛就结束了，我们总共做出了三道题，由于 standing 在半小时前就锁定了，所以比赛完了还不知道自己 rank 多少。

比赛回来，跟同系的同学交流一下，大多是只做出了一道（就是师兄说水题那一道，我至今还不知道是什么题目），还有一个队做出了两道，我们队算是最好的成绩了，做出了三道。我还很忐忑，因为进省赛的名额只有 30 个，如果我们被刷，这三周来的努力就白费了。晚上跑步回来后，最终比赛的 standing 也出来了，我们做对三道，加上罚时 40 分钟（都是我的错），排 27 名。我们系的其他同学可能是初次接触 ACM，成绩都不太好 (今天中午吃饭的时候遇到一个更无语的)。我们队如无意外，总算是进省赛了，总算是忐忑的心安定下来了。

最后说一下我们的队名是：suibian（随便）。