大约是去年侥幸得了河南省选第一的缘故，好几个下一届的学弟学妹找我问怎样准备省选，在这边统一回答一下。

第一，把USACO Training做完。我曾经不无天真地认为，只要做完了USACO，进河南省队就没有任何问题。然而事实上，按照07年的情况来看，这个判断好像真的没有例外。在现在时间比较紧的情况下，写不出来就看题解没问题，但要保证看完题解以后代码是自己独立完成的，且你真的理解了这题目的算法。

第二，学一些最常用的高级数据结构与算法，但不必全学，按照自己的时间安排和兴趣选学好了，因为谁也不知道会考什么。参考清单：网络流（最好学Dinic算法，要知道最大流最小割定理的内容）、Treap或者Splay、KMP算法、Trie树、线段树、求割点和桥、收缩强联通分量。

第三，找一些高质量的套题限时做。这样的目的一方面是查漏补缺，另外是培养比赛的感觉。推荐山东、浙江、天津、重庆、河南的一些省选题，难度适中且比较贴近国情。也推荐USACO历次月赛的Gold和部分Silver题，这些题的好处是有完整的题解，当然阅读英文有障碍的就很遗憾了。

第四，把心态放低，告诉自己省选没有那么重要，进NOI并不是值得赌上全部去追求的东西，若选不上不一定是坏事，在河南这种太受歧视的地域，也许有保送资格以后把文化课搞好才是更合适的道路。把心态放稳，告诉自己河南是弱省，根本没什么强人，只要发挥正常就能进。心理调节很重要，我的经验是，当你心中不会经常出现“省选”或者“省队”这些字眼，而只会专注于一个一个的算法、一道一道的题目时，状态是最好的。

第五，需要更多心理调节以及任何合理的帮助可以直接打我手机，号码给我留个言就会告诉你，MM特别欢迎。

20日。

物是人非。Nothing changed but you. 这是我的翻译。我不想多做解释。

一往如常的街道，依然闪烁的城市霓虹，去过的餐厅，和眼前似乎突然增多的美女。

提包里几十页密密麻麻的打印纸，记载了这三个星期的努力和梦想。考前看两遍，重要的都看了三遍。

21日上午。

进考场，在座位前看到几个在网上见过的同学，寒暄几句。

发试题，看完题目后就平静下来。没难题。

一个小时左右，写完题目。第一题是O(n^2)的算法，第二题是有技巧的暴力算法。

想出了二维RMQ该怎么弄，重写一遍第二题，约用半个小时。

将第一题改成了O(nlogn)，原型/迭代，很Agile，很eXtrem Programming。

两个小时过去了。

剩下的一个多小时，对前两题设计测试数据。

出来以后对老师说，展现出了自己的全部真实实力，但也没有超常发挥。

中午昏昏沉沉，没怎么睡。

下午心态挺轻松，两道题都没有去想完美的算法，第一题用了随机化贪心，第二题则搜索加剪枝。

出来以后，便听说我是上午的第一，190分。同时得知上午的第一题竟完全理解错了题意。

后面的事情不复杂。过一会儿就知道自己是总分第一。看到了郑州的一些牛人，略谈几句。

晚上老师请客，无聊地看电视，两点还没睡着。

次日归家。

今日，学校门口已宣传起来。

4月21日就是省选了，这是我放弃其它一切付出最大努力认真准备了三个星期的一次考试。

它的结果将密切影响我高中阶段的走向，所以很重要。

我已充满信心和勇气去面对它。我相信我超群的实力，我相信我一定会成功。

我的朋友，4月21日，请祝福我！

明日是最后的调整时间，休博一天，勿念。

很容易看出来这几天的效率降低了，似乎已经没有了那么多的算法要学，也没有那么多题目可写。是调整状态和心境的时候了。

消除了写并查集时的一个重大缺陷，值得微笑。

初步掌握了用矩阵乘法优化的DP，第一次写这种题目就AC了呢！实在是太高兴了。

掌握了求凸包的Gramham’s Scan的简便实现方法，大大缩短了代码长度。

认识了一位伊朗同学，呵呵，练了练英语，体验了不太寻常的经历，是很有意思的放松方式。

做了几套题目。山东04day2很有意思的说：prz是区间加法，lan我用了记忆化搜索（又很练了下静态调试），pro考到了并查集，最后作了一个不太严谨的优化，不过还是过了，呵呵。浙江05day1有广搜，有矩乘的DP，有思路特别的DP（其实还是跟背包相关）。这两套题目做的时候好像分别都放弃了一题，但基本保证了剩下的题目不出错（除了没辙的思路方向问题），这样也是值得的。学会细心，学会取舍。

做USACO的feb07gold也很有收获。newbarn是对中位数的比较强的考察，我更加理解了这个概念和应用，不过我还是觉得标程的算法有洞；lilypad是点带权值的最短路，给了我最短路模型构图的新思路；csort考到了置换群，算是对这个生僻的东西再用了一下。这次比赛的题目很有些“剑走偏逢”，真是收获不小。

下面这几天保证一天至少做一套题目就行，看看比较重要的代码，再编几遍重要的东西，比如说平衡树什么的；每天晚上可以看看小说放松自己，尽量午休，千万别把自己累着了；基本上没什么新东西需要学了。

这两天里又学了好几个新的算法，做了好几套题目，还是蛮充实的呢。

Hungary算法现在已经可以熟练快速地一次写对了，对它的理解也有更深入哦。

RMQ问题掌握了线段树和ST算法两种方法，应该是够用啦，不过ST还没到能够一次写对的程度。

KMP算法虽然早就知道是第一次写，呵呵，还抄袭了libg++。反正就那几行，大不了打印了背下来嘛。

LCA问题的Tarjan算法基本上掌握了，不过还是要找时间再看看。

图的割顶与桥已经理解的比较深刻了，其实只要记住Low的定义以及充要条件就好了啊。

又做了好几套题了，有必要总结一下。

写了浙江2006二试。题真的很难呢，得了200左右/400。kaj不用说，xn就不多研究了，polygon和gen（特别是前者）有空还是争取能写满分。

写了好几套USACO月赛。jan07gold里面的lineupg就是RMQ；psolve是一道较难的DP，有点像多进程，应该用心体会；schul就不研究了……nov06silver里面badhair一次写对的，自己设计的借鉴了最小前缀和的算法，与标准答案不太相同哦；bigsq只要想到了枚举对角线，加上我的无敌的剪枝，还是相当容易的，第一次错了几个，原因是没有考虑到某些两个点是不能作为合法的对角线的；rndnum是组合数学，自己调试了半天，最后还是出了一点点低级错误挂两个点，不过这类题目应该已经比较熟练了。nov06gold里的plank就是一合并果子，太水了一次AC；block是第二最短路，不知道在哪里听来的可以用SPFA解，自己写了一下一次AC了呢，看来我对SPFA的理解已经比较深入了；cowfood初看时不知道怎么做，看了analysis才知道是状态压缩的DP，应该由“放了以后四周就不能放”这个条件联想到，照着标程画瓢了一个程序，还要仔细体会。

接下来几天一是要做真题，二是要做USACO月赛，均摊每天不少于两套嘛。最近没怎么做搜索题好像，要找一两倒做做，特别是广搜。好像想不到什么需要学的新算法了，树状数组是需要再写写的。

自从省选训练的上一阶段（做完及总结USACO）圆满结束之后，又过了几天，有必要把这几天再适当总结一下。

写了平衡树两种——自顶向下Splay以及Treap，感觉对后者理解比较深刻，但前者实在强大，二者是都需要十分熟练地掌握的，在省选前还要写个两三遍。

理解了虚二叉树，但它的可替代性比较大，不需要再练习了。

写了2007天津选拔一试，第一遍得分只有140/400。第一题对了，但一开始没看清题导致浪费了一点时间，要注意通读、精读题目。第二题现在还没完全搞懂。第三题当时对了一半，应该主要是没有预先排序的缘故，没有深刻地理解某些东西。第四题的确是想复杂了，当比分有序之后就变成了最少用几个不下降序列覆盖，这个东西等于最长下降序列的长度，这也是刚刚知道的。总之，注意读题。不过想来真正考试的时候有纸版的卷子勾勾划划应该好些。

写了2006浙江选拔一试，第一遍得分170/360，很有进步。第一题显然需要用两个平衡树来乱搞，根本就没有写，哪天精神状态很好时可以尝试写一下，不过考试时真遇到这样的题估计还是放弃；第二题真是要感谢USACO，和“丑数”原来是一样的，WA一组似乎还是因为没看清本质——质因数个数大于前一个数里面的最小的，多加了一个限制条件就漏了解。第三题核心部分是很简单的DP，但预处理得出所有的路径是一个麻烦事；在得出路径时我剪枝很多——当前可以到达终点的只能往终点之类，而这是错的，这是有权图，而且不一定满足三角形不等式，把这剪枝去掉，再加一个若有多余的点则剪枝的条件就能AC了；第四题树形DP，很简单，一遍AC，yeah（不过分值怎么偏小呢……）！这次给我的启迪是：剪枝条件是一定要仔细思考、耐心检查的部分。

下一步准备打印一些经典的代码，比如treap、splay、flow、hungary，等等……多看多背。

本周每天至少写两套题，写一个新算法。

现在USACO Training还剩5道题，今晚不准备再做了。明天或后天应该可以做完。

下一步就是对一些重要的算法、数据结构之类要进行学习研究。

第一步必须要学的罗列在这里：

平衡树。掌握一种即可，还是优先选择treap或splay。（3）

线段树。要灵活掌握，熟练编程。（4）

图的DFS：割点、桥、强联通子图。都要会写。（5）

树状数组。记住公式。（1）

KMP算法。仔细体会，不妨背下来。 （1）
括号中是需要练习的题数。

研究完每种都要写一篇短文尽量清晰地描述其思想。

I. 需掌握的算法与数据结构：
网络流（最短路增广，写一次最小费用流）
二分匹配（Hungary，可能的话KM）
平衡树（Treap or Splay）
可并堆（斜堆）
Hash表（至少写一次需解决冲突的，用拉链）
扩展的欧几里德
KMP算法
树状数组
后缀树（n^2的当然熟练掌握，其它尽量）
线段树（多练习各种变形）
A*/IDA*搜索（多找几道，练习这个框架）
计算几何（先背下来叉乘那些公式吧，写一次凸包）
动态规划（看论文，多练）
组合数学（学哪些呢？）
图的DFS的高级应用（割点与桥）
块状链表（尽量掌握）
高精度运算（加减乘当然要熟练，除法尽量）

II.需要做的题
USACO Training剩下全部的题。
USACO近几次月赛中Silver的题，尽量作些Gold的题。
能找到数据的所有河南省选题。
尽可能多的做各方面与省选难度接近的题。（在黑书、Ural、NOI、IOI……中选题目）

III.时间安排

前天班主任和教务主任告诉我说，这次考试完以后安排我停上正课、训练奥赛，以备战4月21日的省队选拔。

那就拼搏一次吧。三周的时间，全天在机房里，无尽地做题与思考。

我希望进入省队，我希望打开一片新的天地。

明天制定详尽的备战计划，不过不会发出来。

这一段时间里，我的blog不会更新“程序园”、“军机处”、“诗日记”之外的内容，见谅。