国际信奥冠军收割者——金策的超干货技巧总结

金策：麻省理工理论计算机在读博士，本科毕业于清华大学姚班

高三获国际信奥竞赛金牌冠军

高一获数独世界金牌冠军

亚洲信奥满分金牌冠军

全国信奥决赛金牌冠军

全国信奥冬令营全场第一

如何提升信奥的综合能力

这个问题很大，信奥的综合能力包含很多方面。

首先我们知道，信息学比赛比的是编程，它有两部分的能力要求。一是实现算法的能力，如何把脑子里的算法转换成代码；二是设计算法的能力，拿到题目后怎么去设计一个算法来快速解题，这部分更重要。

其中实现算法的能力，是最基本的一方面。不同的阶段对选手写代码的能力要求也是不一样的。

初学阶段，一开始主要是学习语言的一些基本语法，这个过程一般都比较快速，尤其是对于能力较强的学生而言。

而到后期，一般比较困难的是在遇到复杂的题目时，如何又快又准确得去把算法实现成代码。提高这个能力并没有太多的捷径，只能多刷题。

NOIP阶段

一般NOIP级别的题目代码都比较短，并没有那么复杂。如果想要在NOIP比赛中不会因为代码能力而吃亏的话，可以着重考虑提高以下几点。

1 ）熟练掌握各种基础算法

NOIP最基础的一些算法有最短路算法、基本的线段树树状数组、图论的BFS、DFS等。虽然对于初学者来说，它们的代码可能有点长，但其实理解后还是非常容易记住的。

熟练掌握后，大家在比赛中如果遇到这类型的题目，就可以快速地用基本算法的模板去写正确。

2）充分掌握STL

一般大家都用C++来写代码，而C++有一些STL，就是内置的已经实现好的数据结构，比如set、map及其他相关数据结构。

因为这些数据结构如果不用STL，在考场上手写会比较耽误时间，而且大部分情况下，一般题目也不需要特别复杂的一些数据结构的功能，STL已经能胜任比赛的要求，尤其是对于NOIP级别的题目。

所以充分掌握STL能够帮助大家在NOIP级别的比赛中提升写代码的速度及准确性。

3 ）分类讨论及分析边界情况

分类讨论是指能够有清晰的思路把一道题的多种情况都分析清楚，尤其是对一些比较复杂的题目。

分析边界情况的能力是代码能力中非常重要的一项能力，就是如何能写出可以覆盖到所有边界情况且完全正确的代码。

4 ）总结常见错误

在平时训练过程中，大家需要总结一些常见的错误。

比如大家在平时刷题时经常会出现交到OJ上，它返回Wrong Answer或者tle的问题。有时这些错误是一些比较低级的错误，比如数组大小开小了或者函数忘记return了。说实话，这些错误我一开始也是经常会犯，即使到现在，偶尔也会犯。

所以大家如果要提高自己的代码能力，很重要的一点就是减少这类低级错误的发生频率，这样可以大大减少调试的时间，从而省出更多的时间来攻克更难的题。

5 ）调试能力

调试能力是指怎么从一个错误的代码里快速得找出错误的点。

调试一般有两种策略，一是使用一些调试器，比如GDB；二是用输出调试的方法，就是把程序中间的这些数组，还有一些变量的值全都打印出来，然后用手算的结果去对比。这里面其实有很多的技巧，比如可以用类似二分查找的方法去定位程序中的错误所在。

这样的能力需要在平时去不断地培养，这对于比赛时的代码能力还是很有帮助的。

想要达到以上几点要求，需要多刷题

以我自己为例，在高一参加NOIP备考时感觉自己的代码能力不太行，就去刷了BZOJ一整夜，大概有100道左右USACO的Super级别题目（比较适合NOIP的难度）。

这里面有很多的extra、单调队列、线段树之类的题，我就反复操练这些基本算法，尽量保证自己能够又快又准确得把题目写出来。

刷完后感觉自己的代码能力获得了很大的提升，后来我获得了NOIP2013满分的成绩。

NOI及以上阶段

到了NOIP后面更高级的阶段，对代码能力的要求会越来越高。如何去写非常长的代码主要有两方面要注意的。

1 ）保证长代码中没有错误

比如说到了省选阶段，可能会有非常长的数据结构题，可能要实现一两百行的数据结构，如何去保证里面没有错误是一件非常需要水平的事。

大家可能平时会容易忽视，那就是“化繁为简”，意思是我们需要去想办法把一个复杂的题目用尽量简洁的实现方法去把代码写出来。因为代码写得越长就越容易出错，对比赛的发挥也越不利，所以能写简单的代码就不要去写复杂的实现方法。

在平时训练的过程中，大家可以在这方面多考虑，多去做一些对速度要求比较高的比赛。

比如Code Forces之类的，我感觉Code Forces的题目，虽然有时它的代码还是有些长，但是也不会到达特别长的程度，并且它的题目本身有时也比较有意思。

如果要训练写长代码的能力，可以去找一些国内的大数据结构题。其实只要你愿意投入时间，训练代码能力的方法有很多。

2 ）知识储备及思维能力

除代码能力外，大家还需要有一定的知识储备及思维能力，才能够去做出一道题。因为对一道题目而言，实现只是其中一部分，更重要的部分是如何去想出算法，也就是想题的能力。

①学习新算法和知识点

首先最重要的就是，大家至少得学过题目所需要的算法，具备足够的知识储备才能去把题目完成。

虽然每年的各大比赛能出的题目可能有几十道甚至上百道，但其实在信息学竞赛里能够用到的算法也就那么几十种，所以那么多的题目不可能每一道都是全新的算法。

出题人一般要想出一道题，最方便的方法就是找一个以前出现过的模型或一个常见算法，然后去加一些别的元素去进行修改或者推广，甚至也可能会把好几个不同的算法合并成一道题放进比赛中。

所以绝大多数的题，尤其是比赛中简单到中档难度的题，一般情况下只要学过它对应的算法，都是能够通过稍微思考想出来的。这就是我为什么说具有足够的知识储备对比赛的发挥非常重要。

那我们又怎么去学这些知识点呢？首先第一个问题就是，怎样知道哪些知识点是重要的，是需要去学的。

在我们当年，大概七八年前，网络上的资源并没有如今这么丰富。我们获取知识点的渠道一般就是学长学姐帮我们总结，或去看模拟赛难题的题解。如果在题解中遇到一个从没见过的算法，我们就会去百度或者Google上搜索，找到一些相关的教程或博客进行学习。

如今的情况已经不太一样了，首先网上有很多公开的资源，并且知识点都会按难度被分类整理好。

但是这其中存在一个问题，因为大家都可以去贡献这类公开资源，贡献者水平的参差不齐会导致内容的质量无法保证，所以需要同学们自己去仔细甄别并且进行筛选。

另外，有些渠道也能够获得非公开的资源，比如学校内部整理的资料、培训机构有经验的讲师整理的资料、官方发布的比赛大纲等。

官方发布的比赛大纲中规定了很多知识点的难度评分，哪些知识点又一定是会在最高级别的比赛中才会考到，比如fft一定是要到国家队选拔赛的级别才会考。

这对大家还是有一定的参考意义，可以帮助大家在中档的比赛中减轻很多负担。当你明确知道有哪些知识点目前是不会考的，就可以把它们留到以后再去学习。

当知道了要学哪些知识点后，下一步就是如何去学的问题了。

仅仅通过网上搜索教程，然后打一遍代码是远远不够的。因为比赛题目肯定不会只考裸的算法实现，会有一些包装。

举一个简单的例子，比如并查集。并查集的代码很短，可能二三十分钟就能学会。但是会写并查集是远远不够的，因为在题目中遇到并查集的情况是非常丰富多样的，比如对一个图是否是二分图的判断、在序列上的快速处理，都可以用并查集来帮助我们进行一个跳跃的过程，减少实现的复杂度。

虽然知识点只有一个，但是一个知识点的用途可以是多种多样的，所以我们不但要掌握知识点，还要学习并熟悉他的各种应用场景。

这个怎么办呢？我们可以去找围绕同一个知识点所整理好的题单，或者很多网站上会有按算法分类的标签。

比如cf，只要点击其中一个标签，平台就会把该标签下的算法所用到的题目全都罗列出来，我们还可以根据难度评分。

当一道一道题思考下来后，会发现有一些套路或者技巧藏在题目中，这是我们单学算法本身而学不到的东西。在这个过程中，我们并不一定要把每道题都写出来，因为同一个类型的题目可能很多代码都是类似的，重点在于思路的掌握。如果要写代码的话，写三至六道题目就够了，别的题只需要想一想，会做就可以了，这也是节省时间的一个办法。

②思维能力的提升

很多题目的考点不在于某个算法本身，而在于思维能力，去观察并发现题目中的性质来帮助实现算法。

这类题目有很多，比如构造题或者需要我们去猜结论的题目，还有一些非传统的题，比如说交互题或者通信题之类的。

这类题目不一定会有现成的算法，一般只能靠自己想。大家可以去找一些小样例寻找灵感，也可以去尝试一些非常通用的设计算法的思路，比如分治、二分、递推等。对于一些最优化的题目，也可以去观察最优解应该满足什么性质，再从性质入手去设计算法。

省选比赛策略

其实每个人喜欢的比赛策略都不太一样，最通用的一个策略就是比赛开始前先把三个题目都默读一遍，大致感受一下难度。

如果只读了前两题就陷入思考，第三题忘记看的话，万一第三题中有非常容易拿的分没有拿到就很可惜。

1 ）先打暴力分

读完题后，首先应该做的是先把暴力分全都拿到。

先打暴力有很多的好处，一是如果之后要写满分的算法，可以拿之前打的暴力和满分的算法去做对拍，可以保证满分算法的正确性；如果最后写不出满分的算法，也可以将暴力算法交上去拿部分的分数，即使最后写出了满分算法，也可以上交两个程序。

如果对自己的满分算法不太自信，可以用一个if语句进行判断，如果数据方面小了，就交小的暴力程序。但是注意if语句不要写错。

我记得有一年在国家队选拔的一场比赛中，我遇到了一个图论题，暴力是边数比较小的情况，边数大的时候要用更优化的一些算法。我用“while(m--)"方法把边读了进来，读完后m变成了0。

我之后再用m去判断这个数据范围是大还是小，判出来永远都是m等于0，就掉入了暴力的程序，丢了很多分。所以大家在写这个时要小心一些。

先打暴力分的第二个好处是打完暴力后手里有了一定的分数，自己的心态会更稳定，可以更好地去思考后面的难题。

2 ）把控时间，理性选择

因为比赛的时间是有限的，只有5个小时，所以经常会面临一些选择。

比如遇到了两个题目，其中一个题自己知道了该怎么做，但是它的代码非常长，即便写出来了也只能多拿30分；另一题自己大致有了思路但是可能还要继续想很久，如果想出来可以拿到100分。

这个时候就会面临一个选择，去选择写代码长的但是拿分低的算法，还是花时间去思考拿分高的题目。

这个时候首先需要预估一下自己的剩余时间，如果离比赛结束还有4个小时，那就有足够的时间去思考比较难的题目；如果剩下的时间已经很少了，而耗费两小时还没有思考出难题时，一定要保持清醒做出理性的选择。

一定要避免情绪化，不要因为已经想了很久这个题目还是没有想出来，非要死磕到底，这可能会令自己失去一些本可以拿到分数的机会。

3 ）比赛策略的训练

在做完赛前模拟赛后，大家可以去复盘一下自己比赛时的策略，也可以和自己的教练去交流，比如题目的丢分原因或题目没想出来的原因等等。

4 ）考前准备

赛前还有一个需要准备的部分就是去熟练基本的算法，就是常见的图论算法、数学算法的模板等。

如果距离比赛的时间已经比较短了，就不要去学习较难的新算法，把仅剩的时间用在巩固之前学过但有些遗忘的知识点。

考前的最后一两天一定要放松心态，不要再做非常难的题目，做些简单的题帮助自己提升信心就够了。

信奥与文化课学习的关系

1 ）时间上的平衡

对大部分的学生来说，时间都是很宝贵的。如果花太多时间在信奥上，就没有充足的时间去学习文化课。

有一个比较好的方法就是不一心二用，提高学习的效率。在学文化课时就专心地学习文化课，不要一边做作业，一边又思考信奥题。在学信奥时就把自己的所有精力投入到题目上，不要去考虑“自己作业做完了没”等与文化课相关的问题。

我在高一还要学文化课的时候，就是每天把当天作业完成后再去机房刷题。

2 ）信奥学习有助于文化课学习

学习信奥和文化课其实并不是相互冲突的关系，学习信奥对中学的文化课在一定程度上是有帮助的。

因为文化课的考试中也常常会设置陷阱，而信奥可以培养学生缜密的思维，培养学生全面得发现问题、考虑问题的能力。

中学的信奥学习也会对大学的学习有所帮助。比如我大学时学的算法设计课或者数据结构，其中的大部分内容我在中学阶段都已经学过了，这就减少了很多上大学时的负担。

一些曾经没有学过的课，比如编译原理等，其中都蕴含着一些思想和中学时学的算法具有一定的关联，比如动态规划。

另外在大学里，比课程更重要的是科研经历。如果在高中阶段就接触了竞赛，就会有大量的自学的经历、挑战难题的经历，这些经历都对大学的科研有很大的帮助。

寄语

一分耕耘一分收获，成功从没有捷径，而需要我们一点点积累、一步步前行。

祝愿各位同学都能乘风破浪，扬帆远航！

——金策