《OI 教育漫谈》系列目录：
OI 教育漫谈（一）：为什么学习信息学竞赛
OI 教育漫谈（二）：信息学竞赛算法自学指南
OI 教育漫谈（三）：如何教好基础算法
序言：OI 培训有何意义？
本文是《OI 教育漫谈》系列的第二篇，主要为想要自学算法竞赛的选手提供指导。笔者自执教 OI 以来，面对的绝大部分选手都是「弱省、弱校、缺专业教练」。这类选手一部分选择参加线上或线下的各种培训，另一部分则全程自学。在文章的最开头，笔者讲两个观点：算法知识应该靠自学来掌握；OI 培训的主要意义不在教授算法，而在其他方面。
首先说第一点，为何算法知识应当靠自学而非老师讲授。绝大部分 OI 讲师的教课能力颇有限，即使是业内拥有良好声誉的培训机构，其讲师的表达能力也难以保证。另外，笔者注意到，一个讲师的讲课能力，与其本人获了多大的奖几乎没有关联；一味寻求优秀的 OI 选手去讲课，除了给培训机构妆点门面、在家长面前更能夸口之外，是没有意义的。普及组的算法本身便很简单，若认为一个 NOI 金牌选手必定比一个提高组一等奖选手讲得更好，那没有道理：他们本身的水平都远远溢出了普及组教学所需。在此情境下，教师的表达能力便成为了最重要的因素；遗憾的是，以大部分 OI 教师的表达能力，其传播知识的效率甚至不如学生自己在网上搜寻博客文章。
即使寻到了好的 OI 教师，能把知识清晰地传递给学生、能启发学生的思考、还能带领学生培养代码能力，我们仍然反对过度依赖教师。自学能力是计算机从业者最为核心的能力。离了自学能力，在计算机世界寸步难行。算法竞赛本来是培养自学能力的极好机会，若依赖于老师讲课，等于白白浪费了这一机遇。诚然，在一个好教师的带领下学习 OI 的效率比自学更高；但原本能在自学过程中锻炼的各种能力便被忽视。对算法竞赛教育从业者而言，「传递知识与培养学生自学能力」的权衡是一项很精细的工作，笔者将在后续的「如何教好算法竞赛」文章中详述。
应当指出一个现实：高水平的 OIer，他的自学时间必定大于听课时间。第一，他的教练水平极大概率不如他，没法教他高难度知识；第二，即使参加高难度集训，也是短期内快速教一些主流知识点，还有大量的边缘知识没有覆盖到，这些知识都需要靠自学获得。这群人的自学手段包括：在网上浏览博客；在 OJ 刷题；参加各种在线竞赛；阅读集训队论文；互相讨论等。
那么，既然笔者前文说算法知识主要应当靠自学，为何又要鼓励学生参与一些培训、甚至亲身举办 OI 夏令营呢？这个矛盾的核心，即是上一篇文章所讨论的「OI 学习与算法学习之割裂」。 从「学习算法」的角度，笔者鼓励自学；但如果一个选手准备参与 NOIP 竞赛，纯自学是不够的，因为考场上需要一些算法以外的特殊技术，包括：
- 做题顺序规划
- 造数据、对拍
- 打表或骗分技巧
这类技术难以通过阅读教程去学会，必须去参加一些模拟赛，才能熟练掌握。简要来说，笔者认为 OI 培训的主要意义在于：指导学习方向和节奏；参加模拟赛积累经验。如果一个人只想要学习算法、不打算参与 OI 赛事，那他完全可以不参加 OI 培训。
在这基础之上，我们来讨论一个人应该如何自学算法。这些经验源于笔者亲身参赛时的感受，以及教 OI 途中的思考。有部分观点去年已经发表在洛谷的微信公众号上，可供读者参考；该文中的广告部分敬请忽略。
阮行止算法竞赛需要哪些能力？
笔者将算法竞赛需要的能力分为三种：
- 知识储备。这是算法学习的直接目标，选手学会的各种算法、数据结构，做过的各种题目，都是他的知识储备。
- 代码能力。即选手能否高效、无 bug 地实现他的算法和数据结构。这项能力极为重要，但常常被忽视，笔者将在后续篇幅重点讨论。
- 问题转化能力。即选手将「遇到的原始问题」转化成「可解决问题」的能力。
应当指出，这三种能力是缺一不可的。我们见到过大量非常聪明但学得少的选手（知识储备低，问题转化能力高）；见到过大量学了不少知识但是看到题目仍然没有思路的选手（知识储备高，问题转化能力低）；还见过大量能想出来题目做法，但就是写不出代码的选手（代码水平低）。他们都无法在 OI 中取得好的成绩。接下来，笔者将简要介绍这些能力该如何提升。
学习资源之选择
显然，提升知识储备的直接方法就是去学习新的算法和数据结构。然而，当今的 OIer 面临一个困境：如今的学习资源不是太少了，而是太多了。以至于大部分的资源是无价值的，我们的选手需要耗费额外的精力，去找出有价值的学习资源，再去学习。
不好的教程会带人走弯路。每年笔者教 DP，都会发现有学生把 DP 和递推对立起来、把 DP 和记忆化搜索对立起来，事实上它们和 DP 并非是竞品。递推和记忆化搜索是 DP 的两种实现方式，谈何对立。可见一些错误教材带给人的毒害之深。
在纸质教材中，笔者推荐洛谷的《深入浅出程序设计竞赛（基础篇）》，涵盖了 C++ 编程和基本算法，笔者也参与编著了其中的数据结构和数学部分。《算法竞赛入门经典》和《信息学奥赛一本通》亦有一定价值，但学习效率可能不如网络资源。
网络上可以找出不少的博客和课件，这很依赖于学习者的搜索引擎使用能力。如何使用搜索引擎是一项专门的话题，笔者不能详述，但有几个基本的建议：
- 使用 Google。如果无法使用到 Google，则考虑 Bing。
- 不要输入完整的句子。将自己的问题拆分成关键词。
Github 和知乎上有一些不错的资源。hzwer/shareOI 项目中汇集了许多课件，笔者也把一部分课件上传到了这个项目中，选手可以阅读。洛谷日报的一些文章也有学习价值。
循序渐进
笔者在工作中看到许多「点歪技能树」的选手。这部分选手没有学习完基础算法，但学了一些比较怪异的算法，并引以为能事，深感自豪。笔者反对这样的学习顺序，因为这样的学习是不长效的。如果选手把这部分时间拿去学习其他基础算法，他将有更好的进一步学习高难度算法的潜力。
算法学习是循序渐进的过程。没有办法让选手一下子掌握所有的知识，但有办法让选手从浅入深地一步步掌握知识。
譬如一个普及组的选手想要学主席树（可持久化线段树），那笔者会先建议他掌握线段树，再写一些线段树的题目、学一下权值线段树，建立「用线段树维护序列」的思维。接下来笔者会教他 Trie 树，让他掌握「动态开点」这一个思想。然后教他动态开点线段树，让他能用线段树维护 1e18 级别长度的数据；然后笔者会抛开 OI，跟他讲讲 git （现代最流行的版本管理软件）对文件管理的实现方法，让他建立「版本管理可以复用之前的节点」这样的意识；最后笔者再教主席树，这就是水到渠成的了。
你如果直接教他主席树，他也许可以把代码背下来，甚至可能 AC 掉你教的例题，但他没法解出其他题目，而且过几个月就忘了这套数据结构。这是因为在没有完全掌握基础理论的情况下，去学习高级算法，无异于搭起脚手架在空中建房子，脚手架拆了房子也就塌了。
「点歪技能树」对低年级选手有某种强大的吸引力，甚至在同学中具有一定的传播能力，这是人性使然。但笔者希望 OIer 克制住这样的冲动。
提升问题转化能力
一个人的天赋，即我们说的「聪明」，常常表现在问题转化能力上。当然，后天的训练更加重要。想要提升问题转化能力，至少需注意两件事：
- 学习算法和数据结构时，多进行本质性讨论，并关注不同知识之间的联系。
例如，选手在学习完序列分块和线段树之后，应当考虑这两种算法各自的使用范围、各自的高效之处。 - 多做题，并归纳题目之间的联系。
例如，选手可能发现某题的手段与另一题类似，此时应当把这个「相似性」整理出来。
注重代码能力
我们首先解释一下何谓「代码能力」。笔者将其定义为「得知确切的算法思路之后，选手将其实现的能力」。笔者曾专门写文讨论选手如何提升代码能力，今予摘抄。
阮行止代码能力，这个非常重要的能力，常常被信息学竞赛从业者忽略。我们基本看不到关心学生代码能力的机构；即使是在中学，也很少有教师能指导学生形成科学的代码习惯。在这个环境下，选手提升代码能力如同在黑夜中摸索，全靠熟能生巧了。
信息学竞赛圈有一个流传非常广、危害极其深的误解（甚至很多中学教练都有这样的误解）：「代码能力完全靠刷题，题刷得越多代码能力越强」。这个说法有一定的正确性，但是很不全面。真实情况是：
- 做题 + 反思可以培养选手的代码能力。反思是非常重要的过程，只做题不反思的效率很低。
- 选手可以通过一些手段，降低打出题目所需要的代码能力。
在实践中，选手如果常常出现「看完了题解的详细算法思路，但无法实现代码」的情况，那么可以判断选手的代码能力较弱。传统上，一般认为提升硬核代码能力的唯一途径是多刷题。但是笔者需要在这里指出：反思比刷题本身更重要。
粗浅地讲，如果「把一道题 AC 掉」会花费 10 个单位的时间、得到 10 个单位的代码能力提升，那么反思自己的代码并加以改进，只需要额外花费 2 个单位的时间，却能再得到 15 个单位的代码能力提升。
反思，是给自己已经 AC 题目的代码挑出不优雅的地方，并改写成优雅代码的行为。这要求选手脱离「代码作者」的身份，以客观的视角，去审视代码中设计不合理的细节，并且加以改正，形成更加良好的代码。
怎样的代码是优雅的、怎样的代码是不优雅的？这就需要选手拥有对代码的品味，以及对代码质量的孜孜追求。应当诚实地说，代码是否优雅，没有很统一的标准。工程上有一个「Keep It Simple & Stupid」的原则，笔者认为这很适合信息学竞赛。
代码也并非越短越好。很多选手喜欢写技巧性高的代码，一方面可能是为了时间效率，另一方面可能是 OIer 群体的风气使然。但是应当意识到，通过代码炫技获得的时间效率提升，几乎是微不足道的。复杂的代码难以 debug，最终是一种得不偿失的行为。
贯彻自己的代码风格。每个人喜欢的代码风格不同，但有一点是很重要的：代码风格应当从一而终。不能这道题用这种代码风格、下一道题就用另一种代码风格；也不能在一份代码里面混用多种代码风格。代码风格至少包含缩进风格（例如左花括号换不换行）、命名风格（驼峰还是 snake）、注释的时机等等。选择了一种代码风格之后，应当将它坚持下去。
多想想细节，再开始写代码。即我们常说的「Think twice, code once」。这是一句谁都知道的道理，但是付诸实践确实非常艰难。初学者常常在代码细节还没有想清楚（或者以为想清楚了，但实际上有些东西没有考虑到）的时候就去编码，这样写出来的代码质量是很差的。应当提倡在写代码之前，先在草稿纸上写出自己能考虑到的所有细节和边界情况、每个函数具体要做什么事之类的信息。这有助于检视自己的设计是否合理，也能提升后续实现代码的效率。
减少分类讨论。corner case （边界情况）是大量程序 bug 的源头。一个程序不得不照顾到尽可能多的 corner case，于是欠缺经验的编程者常常陷入无尽的分类讨论中。而海量分类讨论对 debug 效率的打击是致命的。
举一个经典的例子：输入两个形如 yyyy/MM/dd hh:mm 的时间 $A, B$，问它们之间的间隔是多少分钟。如果直接考虑将两个时间按分钟、小时、日期相减，则会陷入大量的细节讨论中。但如果换一个思路，首先写一个「求 0000 年 1 月 1 日 0 时到时间点 $x$ 经过的分钟数」的函数 getPassedMinutes(x)，那么立刻就可以通过初始时刻到 $B$ 经过的分钟数，减去初始时刻到 $A$ 经过的分钟数，得到 $A$ 与 $B$ 之间的间隔。而 getPassedMinutes 是很容易实现的，需要考虑的边界情况也远比「直接把 $B$、$A$ 相减」少。于是我们以更简单的方式解决了问题。
做好封装。对数据结构和算法的封装是很有必要的。有一个著名原则叫 Don't Repeat Yourself，如果很多地方需要用到相同的逻辑，那就应该把这套逻辑提取出来，而不是将它的代码复制粘贴多次。
写博客记录知识
这是一个很重要的活动。选手应当写博客记录自己学到的知识，而且最好以「讲述者」的身份写文章，即把自己学到的东西教给读者。实践表明，写博客的好处至少有二：
第一，帮助选手理清头绪。一个算法或数据结构可能比较复杂，而把这些知识以文字的方式整理出来，相当于梳理了一遍内容，加深认知。
第二，便于日后复习。选手透过阅读自己博客来复习，效率远远高于重新阅读当时的学习教材，并更能抓住一些值得注意的重点。
笔者不建议选手写「题解」类的博客，除非该题目很有启发性，此时选手应该把这些启示记录下来。此外，选手应当以严肃的态度去编写博文，逻辑要通顺，标点符号要准确。
算法之外的竞技技术
笔者最后要再次强调，考场上的竞技技术难以自学，想要参加 OI 系列赛事的选手，应当至少参加一次有大量模拟赛的培训。即使是一个很会算法的选手，如果从来没有 OI 赛制考试的经验，那么他上场之后可能会因为不懂 NOI Linux 的使用、将代码放错文件夹、忘记 freopen 等种种问题而获得零分。
如果选手的学校有此类模拟赛，那是最好的情况；退而求其次，有些线上培训，或专门的线上 NOIP 模拟赛是值得参加的。
欢迎读者来信交流，笔者邮箱是 ruanxingzhi@gmail.com 。