posts - 274, comments - 1258, trackbacks - 0

前言
　　其实这篇报告一早就规划好了，就是一直都没有时间把它敲下来。回到广州后，又是签三方又是体检又是办理退宿，之后又坐了一天的火车来北京，直到今晚在室友代黎明同学的帮助下终于可以上网敲报告了，在此先谢谢代黎明同学。

经历
　　上回说到我们Alioth在长春很郁闷了一下。于是这次谁也不敢大意，临出发前大家都狠做了一些题，也狠积了一些ＲＰ。当时我有个预感，我们队应该不会卡题（调不过）。
　　这次比赛的策略与在长春时略有不同，大致来说，由我来负责敲水题与中等难度的题或模拟题，德健主攻比较繁难的题，德健的推导能力比较强，数论题与比较难的ＤＰ就靠他了。
　　比赛开始时，德健看ＡＢＣ，枫耀看ＤＥＦ，我看ＧＨＩＪ。
　　Ｇ题一看便知是一道很繁琐的计算几何题，我们都不太熟，于是先放下。然后ＨＩＪ中Ｉ题很短，便先看Ｉ题，看完之后觉得很难（这个判断之后证明是正确的），想了一下觉得没头绪便也放下了。此时刷board发现Ｊ题有人过，便马上看Ｊ，果然很水，立敲之，过。然后枫耀觉得Ｄ题可以用线段树做，便把题意告诉了我，我想了一下觉得用STL set只要重定义一下排序函数就可以很简单地过掉，而用线段树或平衡树反而会很繁。此时德健与枫耀讨论一下后发现Ａ题可以做，但比较繁，于是我决定先让我过Ｄ题，不出预料，Ｄ题很快也被过掉了。
　　这时德健发现Ａ题有个地方没有处理好，同时发现Ｈ题有很多队过，便看Ｈ题，发现是水题，敲之，ＷＡ，于是打印，发现有小bug，改之，也过了。这时我们过了三题，排名较前。
　　此时德健继续敲Ａ，枫耀把Ｂ题的题意告诉了我。十分可惜的是，我鬼使神差地记错了题目的规模，竟以为只有NlogN以下的复杂度才能过，苦思了一段时间，没任何有意义的结果，于是继续规划Ｇ题，此时德健交了一次Ａ题，ＷＡ，发现题目输出上限是１０亿，刚好爆int，狂晕后改long long交，过，暂时排第一，而Ｃ题是一道类似Apple Tree的树形ＤＰ，很有信心能过，形势一片大好，众皆乐。
　　Ｃ题代码量也不小，于是给德健敲，期间枫耀在想Ｆ题，很神奇地想到一种3⁹*3⁹*9*50的ＤＰ方法，可惜我当时没有给予足够的关注，后来我发现只要稍加一些改进就可以把3⁹变成2⁹，但那已经是比赛结束以后的事了。
　　德健敲Ｃ题时很小心，再加上平时大量做题换来的丰富经验，魔术般地１AC了这道很繁的ＤＰ题，这时离比赛结束还有大约一个半小时。
　　这时我们比较了一下剩下的题目，Ｂ题没想法，Ｆ题复杂度太高，Ｇ题敲起来太烦。想了想还是攻Ｇ题比较好。规划讨论了二十分钟左右时我们发现Ｂ题很多队过，便重新看了Ｂ题，发现了一种Ｎ²的算法，便决定改为全力攻Ｂ题。德健负责敲，我在旁边看，枫耀验证算法。很快地，我们就把程序敲完，交，ＷＡ了。这个ＷＡ来的很诡异，集训时当我们一起攻题时很少遇到这种情况。于是我让德健去看程序，我和枫耀出数据检验，但大家都没能发现问题。一直郁闷到比赛结束。回到酒店后我与ＡＣ一讨论，才发现原来我们把题意理解错了，有一句模棱两可的话把德健和枫耀都骗过了。
　　最终，我们队队排名第４，学校排名第３，虽然还有不少遗憾，但终于能拿到一块金牌，而且还能出线，已经可以算是完美的结局了。

教训
　　我们队的数论，组合数学，博弈方面的能力还是太弱，热身赛时一道ＳＧ定理的水题就把我们ＢＳ掉了。这次比赛能够取得较好的成绩，其实不过是因为没有出到这方面的难题罢了。
　　题目过不了时一定要找人重新审查题目描述，最好能找没有看过题的人来看。假如当时我能重新看一下Ｂ题，很可能我们就能把Ｂ过掉了。
　　
感言
　　这次比赛，是我两年的ACM/ICPC生涯的最后一战，非常感谢我的队友德健与枫耀，是他们的努力使我能够以最好的成绩退役。两年以前，我还没有意识到算法对我会有多重要，那时候，我只是觉得学算法很好玩，做ＯＪ题很有趣而已。而两年之后，当我要到处面试、找工作的时候，才发现原来算法是这么重要，它使我在参加各大公司的面试时都能一路绿灯。因此我非常感激郭老师，给了一个很好的平台去学习算法，去检验学习的成果，给了我很多证明自己能力的机会。还要特别感谢虫子，他给了我最多的帮助，是真正的“有问必答”，没有这个Final级大牛的帮助，我是不可能在短短两年内学到这么多东西的。还有老战友狐狸和飞飞，我永远不会忘记那段一边吃ＢＢＱ一边讨论各种算法难题的日子。感谢所有帮助过我的牛人们。最后还要勉励一下各位师弟师妹，多花点时间和精力研究一下算法吧，保证你不会后悔的～

花絮