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题，我就排到了第六，不过也没什么遗憾的。呵呵，恐怕我觉得不遗憾的原因之一是我离开机房以 后取到了期盼已久的相当漂亮的原版书吧，Music: An Appreciation Fifth Brief Edition (with 4 CDs and 1 CD-ROM)。
Contest 10 by Die，发挥正常，成绩斐然，Rank 2。顺序看到C以后觉得好做，一道不难写的图论。第19分钟，全场第一个提交，AC了，然后继续看题。一分钟以后的全场第二次提交是hhgg的，AC了G 题。于是马上去看，发现又是一道跟背包有关的DP。由于细节的错误，拖到52分钟交了第三次才AC。不过仍然是全场第一个2题的，保持rank 1。再次仔细看了剩下的题目，A根本读不懂题意，B是我绝对不碰的蘑菇题，D是暂时不想碰的小蘑菇，E和F好像都是建立图论的模型。于是在那里做E，连续 WA了四次以后才领悟：我建立的图论模型完全是错误的，这不是一道图论题！（事实上，赛后得知是用搜索做的。）放弃了E以后，在很麻烦地写F。一次TLE 和一次WA以后，感到对这题没有把握，无法控制程序的思维复杂度，放下了。看到好多人都在写不太好处理的D，只好跟风了。这题是一道较为麻烦的文本处理的 题目。做这题我采取了非常正确的策略：先在forum里看了长达数页的问题，确保正确理解了题意、没有漏掉细节，然后仔细地设计了程序的结构，怎样最方便 处理，很充足的准备以后才开始写。第一次提交返回的PE比较让人振奋，194分钟时交了第三次AC了。很囧的是，两次PE的唯一原因是没看到输出的 cases之间要加空行的要求……很有喜剧效果。这时好多好多人都三题了，没想到我竟然是总罚时最少的。不记得最后的及时分钟在做什么了，大约已经放弃写 程序了，坐在那里静静地读圣经吧。结果，比赛剩不到十分钟时Fire大神AC了B，就得了第二。
Contest 12 by Balloon，有一定失误，Rank 10。大致看了题以后，没发现能秒杀的。只有小蘑菇题G似乎能做，快速地敲完了代码，却TLE，尝试优化时间效率，却TLE依旧，非常茫然。半小时左右的 时候，看到有很多人AC了F，便去做。写程序找了半天规律，推出了公式，拷贝了大数模块，提交以后SF。改了大数类里的数组大小，就AC了。同时，有不少 人1Y了A，判断出一定是第一次没看出来的秒杀题。找到了一个必要条件，充分性不会证，写出程序过了样例就提交了，一次AC。想到了B的算法，二分答案加 匹配，于是做。第一次有种特例没处理到，SF了，第二次提交AC。期间还在修改和提交最开始写的题G，找到了一处导致死循环的错误，把TLE变成了WA， 又因为某种小错误折腾了很久，终于在九次提交以后AC了，真是很没状态。剩下的题目里，C与E，由于算法复杂和程序蘑菇的缘故，对于我来说不可做。D与H 是可以考虑的，前者是大家都在搞的字符串蘑菇题，后者是数据结构题，用平衡树或者块链做都没问题。二者之间，我选择了H，开始写需要不少扩展的 Treap。最后两小时一直在搞这题，太久没有写这种东西，期间失误数不胜数，最终也没能AC。这次的失误在于：面对令人困扰的G，没能冷静、细致地查 错，而是一遍遍地无策略地乱提交，导致在相同题数的家伙中间排名很靠后。H在实现时有失误，为了删除操作的简洁，采用了懒惰删除的策略，却没有意识到，这 会使其它每种操作都要额外考虑更多的情况，大大提高了整个程序的编程和思维复杂度。B组比赛的特点，似乎是每到题目多多少少都会融入蘑菇的元素，导致我做 起来不顺。这大约与B组组长的特质有关？^_^
Contest 13 by Die，发挥不错，Rank 1，第一次呢，8题的比赛AC掉7题也算比较圆满了。开场看到C题以后觉得比较水，8 min的时候秒杀了（其实还小调试了一会儿弱智错误）。提交的时候看到好几个人过了A，判定一定是水题，找了个充分不必要条件就写了很短的程序交了，13 min时1A。下一道去做的是H，一道多少有点old的题，隐式图里BFS找最短路，同样还是因为弱智错误调试了一会儿，没想到38 min AC的时候还是全场第一个三题的。这时剩下的就没有水题了，明显的广搜但写起来很繁的是B，不太擅长的几何题是D，E看上去挺大自然的，简单但是处理起来 麻烦的是F，一般困难但完全可做的图论题G。考虑了以后，我还是选了F先做，因为这题到最后会被很多人AC，我是不得不做的。好在没有出什么低级失 误，83 min时1A。接下来的选择就不太好做。别人在这时大概都会选D做，因为这的确是剩下的题里面难度最小的一道，不过考虑到我不擅长几何，还是去做了更有把 握的G，果然写起来很顺利，113 min时一次AC。迄今的五题全部是一次AC，用时非常低，Rank 1保持。这时D好几个人过了，B还没人碰，不得不写D了。发现自己这么晚写D还是有好处的，因为一开始题目描述有误，更新了以后变简单了。写好了以后，不 断地过不了样例，不断地发现一开始的思路就有错。好不容易把样例调过了，交上去，返回了我本场的第一个WA……检查了好久才发现是题目要求输出之前要排 序，175 min用了三次提交AC。剩下的两道题里看上去可做的只有B。离结束还有半小时的时候写好了，提交上去WA。很无望地在读代码查错，怎么看都觉得代码无懈 可击，用了几种诡异的办法打补丁，仍持续WA。直到距比赛结束还有五分钟时才猛然发现：自己开数组时犯了一个6*6=24的错误！又是这种令人沮丧的情 形，数组开小了造成的后果是WA而非SF……把数组开大以后，终于在最后时刻AC了，凭借相对很少的罚时，保住了Rank 1。赛后发现，最终也没人碰的E事实上是完全可做的，如果B的数组没有开小，最后留下半小时写E的话，还是有一定可能圆满8题的，算一点点遗憾吧。
Contest 15 by Balloon，令人没想到的是，在上场的个人最好成绩以后，这场迎来了暑期集训的最差表现，Rank 16，惨不忍睹，感觉整个比赛都在梦游。总结教训的话，却找不到什么能凸显出来的失误，只是不知为何一直在犯低级错误。
Contest 16 by Cannon，最后一场，比得如何都很难影响最终的结果，所以对我是一场轻松平淡的比赛，Rank 4。开场很快AC了B和G，简单图论和简单DP。C是一道有一定难度的猜数字的题，O(N^2)的DP是显然的，但这样会TLE也是显然的，我把DP写出 来了以后一直找规律，但无果。后来发现从另一个不太显然的角度去设计状态复杂度就低了，就AC了这题。期间小失误若干，TLE一次，因为忘了测试时 main里写的是for(;;)，汗。F是搜索题，时限5s非常厚道，我的复杂度非常高的程序用时4.4s一次AC了，呵呵。 剩下的题里面，可做的只有D，一道可以用RMQ解决的题。SF、MLE很多次，才发现用的RMQ模块有bug……很艰难地用了七次提交AC了。剩下的时间 在yy A题，看到有人过了，但是想不出来，就去吃饭了。
