July 14th, 2008
Monday, July 14th, 2008
每个或有或无意义的开始，我都会变得兴奋而躁动，一些忘却抛弃，一些憧憬期许。就像今年一月我无理由地坚定地认为2008年是美好的一年一样，七月的最初，我同样坚定地做出七八月的暑训、今年下半年以及整个大一的一年时光都将美丽姣好的没有理由的结论。——七月四日
过了二分之一的这个七月，给我的感觉不同于以往的任何一个时期。——极度繁复的同时，也极度简约。极度火热的同时，又极度冷寂。贯穿每日的主线是，一边拼命挣钱、一边拼命花钱，一边努力出题、一边努力做题，一边尽力提高自己、一边尽力指导别人。就是这样，若非亲历很难体会。
集训前两周期已经结束的六场比赛需要总结一下。
Contest 2 by Balloon 是没进行任何ACM/ICPC有关的活动几十天之久后第一次比赛，完全没状态，Rank 12。依序看到D，便知道该怎么做了，19 min 1Y，是全场第一个AC此题的。看到有两人AC了A，略思考便想到了跟NOI某题类似的做法。当时认为，精度的缘故，需要写一个分数类，很快的敲完了。后来的事实证明，我现场敲的分数类对负数的处理有极大漏洞。可我错误地估计了错误，一遍遍地在主程序中寻找bug，WA无数次才意识到是分数类写得有问题。后来我发现，只要把我第一次提交的很垃圾的程序加上两行补丁，就可以AC。现场在66min交到第九次才AC的原因，一是一开始错误地估计了bug的位置，二是正确地找出bug以后没有仔细思考就开始写较为复杂的补丁，而没有看清错误的本质所在。这两个题水过以后，看上去可做的题目有B和E。对于B，我非常怀疑自己此时的coding能力能否应对这个算法不难代码似乎不好写的题目，于是看E，这个我最终交了13次也没AC的题目。交了4次E，完全不知道为什么WA，放弃了。然后开始很慢的写B，写一种极度麻烦的算法，一直到145min才交了两次AC。再次概览剩下的题目，仍然认为只有E可做，拼命查错和提交，一直到比赛结束都无果。最终才明白，原来E是因为误解了scanf中”\n”的意思，导致读入出错了……交的第二个程序的算法就是完全无误的。如果能更早地做掉E，显然与它的加强版F题不存在AC的障碍。真没想到算法一点问题都没有还会败在输入上……
Contest 3 by Cannon 也是一场郁闷的比赛，Rank 8，虽然Rank有所上升，但是题数上非常不满意，只有两题，是第一名的三分之一。陷入两个大坑，是做过的所有比赛中最郁闷的一次。看了A就觉得可做，不过大概由于慢热的缘故，26min时交到第4次才AC，原因主要是coding时欠考虑吧。又看了B和C，B觉得略有麻烦，C似乎是裸的高精而已，就开始写大数类。看来是完全没有吸取上次手写分数类的教训，对自己当下的coding能力认识不足，大数类不是写错就是效率有问题。期间推了下B的式子，也AC了。在C还是没能AC的情况下，又陷入了F，记忆化搜索，WA无数。后来发现，我的算法和标程不一样，但也没找到实质性的错误。剩下的时间就是在疯狂地改和交C和F，无果。比赛结束前20min意识到C可以用模板，可惜对学校的大数模板完全不熟悉，C++中stream相关的内容也基本忘了，输入输出都有点搞不定……现在看来，这次比赛AC
题数过少的原因之一是我较为熟悉和擅长的DP一题都没出。见到的题目太少，略有些 ad hoc 的题目就会搞不定，这是目前最大弱点。
Contest 4 by Die 的感觉稍微好一点，Rank 5。35 min时一次AC了H，擅长的套路。然后67min时用了三次提交AC了G，算法完全正确，问题在于无视了题目中一个条件，导致两次WA。然后就看到很多人过了B，便也很容易地AC了，在此之前的一次提交竟然是MLE……原因是忘了输入完成以后break。下一道题的目标我选了E，交了9次基本都TLE以后，确定自己的算法错了，就中途离开机房吃饭去了。这场比赛做得太急，导致不细心。赛后觉得，如果更多地花点时间思考下D，是应该能搞出来的，错误地估计了其难度与麻烦程度。
第一轮完毕以后，计罚时和不计罚时的rank分别是9和11。
第二轮，从 Contest 5 by Balloon 开始，逐步有了状态，Rank 3，比赛过程可称顺利。一开始看到了B，觉得是一般难度的DP，随手写了交上去，然后WA。静下来看一下，发现整个算法是错的，换了正确的算法重写，结果疏忽了一句保持单调性的话，交到第三遍才AC。下面是E，非算法题，比较熟练地用着STL，1Y了。F又是一个DP，吸取教训仔细想清楚了才写，同样1Y。接下来做A的时候又卡了一下。最开始写的是搜索，没有估计好复杂度，TLE两次，第一次交TLE了以后还以为是被卡了常数，第二次TLE后算了下复杂度才意识到必须加上记忆化。加记忆化的时候又写错了一次，第四次才AC，属于失误。看到wanwei似乎很轻松的1Y了winsty的小蘑菇题G，虽然明知自己对这种题目根本不擅长，但也没发现有别的可做的题目了。写了很久，调了很久，花费了近一个小时，还好1Y了。在这一段过程中一直都是紧随Murphy，排名第二，看到他过了C，就也去搞。没想到一下子就看出了C的本质，用DP预处理一下后，又1Y了。这时，只剩下了一道没人碰的蘑菇题D，我怎么看都没信心，很累，又计算了一下发现后面的人不大可能超过来，就很高兴地提前近一个小时出去吃饭了。后来得知G的数据有小问题，rejudge了以后rank 2的位置变成了watashi。在题数上，应该说没有任何遗憾，1Y率有提高，很满意。
Contest 6 by Cannon 是目前位置的最好成绩，Rank 2，但是不像上次一样毫无遗憾，因为是由于不必要的失误没得到Rank 1。前一天晚上只睡了五个小时不到导致状态很差。开场先做了矩阵题G，打算秒杀之，没想到一开始就因为矩阵乘法写得不太好而TLE两次，优化了效率以后又接连地WA，要郁闷死了。到论坛里看了答疑才知道原来自己把题意理解错了，改之即AC。91min第7次才AC这题，真是开场不利。AC了G以后开始做C，很老的题，用匹配做，没想到竟然WA。难道自己已经退化到连Hungary这样简单的算法都会写错？很沮丧，就暂时放下了。看到A是不难的DP。哦……好吧，对于我来说不难的DP，WA一次以后AC了，WA的原因是没看清题……寒。把手放在键盘旁的圣经上，定神了以后做C，一个不太难的搜索题，终于一次AC。接下来的时间就在搞C，出很多组数据来测，怎么都看不出为何会WA……这时看到自己是Rank 2，3题的两人之一，但由于罚时太多太多后面的人很有可能超过来。十一点一刻的时候最后交了一次WA终于放弃了，因为实在是找不到错误，加上极其瞌睡，就跑掉了。没想到但是直到结束竟然能保持住Rank 2的位置。后来得知，C是因为输入处理错了导致不断WA。竟然又是该死的scanf里面的”\n”，第三道题了！所以太遗憾了……真不应该那么早离开的。以后再遇到这种莫名其妙的WA一定要仔细验证下输入输出。
Contest 7 by Die 打破了前五场Rank单调递减的神话，Rank 6。做得不够好，罚时太多了，而且策略有失误。开场以后大致看了一遍题，发现A是可做的DP，虽然有点麻烦。写了四十多分钟，交上去WA。惊讶地发现这时AC两题的都有了，都是B和E，E有十几个AC的。意识到E是第一遍没看出来的极水的题，随便一写就1Y了。又去做A，又WA一次，发现没看清题，53min第三次提交才AC了。接下来当然是做B，做的过程很不顺利。一开始发现搜索可做，经历了MLE、TLE和两次WA以后，对搜索有些绝望了。惊奇地发现用匹配可做，粘贴了任意图匹配的模板，终于很不容易地AC了。事实上这题完全可以用搜索，是我一开始写丑了。接下来的目标我锁定在D上，自以为对这类最优比率的题目非常熟悉，不就是二分答案么。虽然写起来也有点繁，不过还是很有信心地在写。写完以后，就总是WA，发现我的Bellman-Ford总是莫名其妙地找不到负环……在那边拼命地调啊改啊，基本上各种可能的错误返回都经历了一遍，还是没能AC。期间发现比我多一题的都是AC了F，但是F使我非常不熟悉的类型，完全没法形成完整的思路。到了只剩一个小时的时候，我终于放弃了搞了一个半小时的D，开始硬着头皮写思路还想不清楚的F，加上这时已经很累了，一直到比赛结束还没调出样例来……罚时太多就不说了，看错题写错代码还可以解释成状态不好。关键是，这场比赛的策略太失误了！像A那么麻烦的DP显然不应该作为第一道题来做，要相信肯定会有比这水的题嘛，这直接导致了E和B的用时比正常值多多了。至于D，后来知道，应该用迭代法做的。自己不会这个方法，AC不了，也没什么不正常。但问题就在于，D搞了那么长时间，交了24次，实在有些过于固执了。虽然E是我不熟悉的类型，但毕竟是非常可做的题，那么多人都AC了，只要有时间慢慢搞应该不存在问题的，至少完全可以写个复杂度略高但好写很多的算法。唉，还是经验少，太莽撞。
第二轮结束以后，计罚时和不计罚时的Rank都是6。
~~~~以下是三、四轮的总结~~~~、
Contest 9 by Cannon，一场有失误、没遗憾的比赛，Rank 6。开场扫了一遍题，没发现特别秒杀的，就开始写F，一道简单的树的题，轻松1A。不久后又有人过了A，属于经典问题。一开始没想清楚算法，WA了，又因 为忘了删掉调试语句Output Limit Exceeded了一次（第一次得到这种返回的说- -）。好在第三次提交就AC了。这时有一些人过了C，一个小蘑菇题。这种题我也掌握了一些诀窍了，就是不厌其烦地尽量结构化，让自己能掌握全局的思路，就 可以了。似乎用了十多分钟就很高兴地AC了这题。E是一个数论题，略加考虑写了一个递推求欧拉函数的程序，还不厌其烦地加了很多优化，没悬念地AC了。这 时，比赛开始才一个半小时，我AC了4题，速度都很快，排名第一位。这时，D那种蘑菇题我显然是不写的，F可以看出来是搜索可怎么分析都会TLE（后来知 道标程是IDA*)。可做的题目只剩下B，一个背包问题的变体。我yy了一会儿，发现自己可能“证明”了，可以将一种规模一定不可做的01背包问题规约到 这个题，所以说，这题一定不可做了！我甚至抱定了“标程的算法是错的”这样的信念。加上我很期盼的快件到了，便很潇洒地离开了机房。当然，当时“规约”的 证明是完全错误的，属于失误了。最后有五个人很艰难地搞出了B题，我就排到了第六，不过也没什么遗憾的。呵呵，恐怕我觉得不遗憾的原因之一是我离开机房以 […]