如何准备信息学算法竞赛？ ——我是如何赢得美国信息学奥林匹克竞赛3届金牌的

如何准备信息学算法竞赛？
我是如何赢得美国信息学奥林匹克竞赛3届金牌的

作者：Andrei Margeloiu，2017 Google HashCode竞赛金牌获得者

高中第一年，我从0开始学习了C++。一开始我对编程、算法和数据结构一无所知，几个月之后我才开始写代码，当时计算机信息学奥林匹克竞赛来了，正好我可以试试我的学习方法是否有效。

经过2天的比赛，我赢得了金牌。

我很震惊，因为我超过了有5年经验的参赛人员，我知道我很努力，但是这个成绩超出了我的期望。这个比赛很适合我，我也因此全心参与其中。

我知道是什么让我如此成功，现在也在此将经验分享与你。

我需要学习什么语言？

C++ 强烈推荐，非常快，由于可以使用STL，可以很方便的实现不同的算法。任何比赛都支持C++，我一开始就是使用这个语言。

C语言 —— 如果你懂得C，你也可以使用C++。

Java —— 比较慢，但是Java有大整数，不过只有少数题目需要使用。如果题目的时间卡的比较紧，容易造成time limit exceeded。一般比赛都没有Java。

你能去哪里练习？

推荐SPOJ，上面有大量优质题目，并且有解答。也有对应的支持网站SPOJ.pl。

首先，你需要掌握基础知识

当你学会基础语法后，你就可以开始解题了。从简单的题目开始，在这个阶段，你的目标是锻炼自己的代码风格。你可能喜欢写代码的时候用很多空格，或者喜欢将大括号放在if的同一行。

你需要找到你自己的风格，因为这是你的。

在提高你的编码风格时记住如下两点

1、实现简单。你应该习惯于对你自己的解题思路，为啥？因为比赛的时候，你最不想发生的事情是迷失在自己的代码中。多思考5分钟，比动手写10分钟要有效的多。

2、简单易读。这意味着调试简单。必须承认的是，bugs总是经常出现，你知道当你只有10分钟的时候你却不知道bug在哪里的感受？相信你肯定印象深刻。为了解决这个问题，代码必须易读，这样容易跟踪和调试。

如果提高实现的速度？

练习、练习还是练习。我建议你先练习SPOJ上解决最多的前250个题目。逐个顺序的解决这些问题，并且思考一个小时以上。

不要说“这个问题对我来说太困难了，我想试试下一题。”这是失败者的思维习惯。拿一支笔和一张纸，然后开始思考。这样，你才有可能找到答案，也因此你才能够提高算法思维，如果你思考超过了一个小时，你可以查看参考答案。

这个方法的结果是：你能够快速实现算法代码，并且能够学会经典的题目和算法问题。

第二点：你必须熟练掌握算法和数据结构

通过循序渐进的方式前进。如果不会走路你觉得你会跑步？当然不现实。如果地基不好，你能在上面建造摩天楼吗？当然也不现实。

这意味着你不能够把步子跨大了，如果你这样做，你会漏掉很多细节，随着时间的推移会造成越来越大的知识缺口。

从基础算法和数据结构开始

开始的时候很困难，因为你不知道要怎样开始，我创建了一个算法和数据结构的视频课程，这个课程是按照我的想法来设计的，结果在开始的一个月，竟然有超过来自100多个国家的3000+的学生加入这个课程。

如果你只做简单题，你永远也得不到进步。

有效的解决你不懂的问题的唯一办法是找到这些题目然后解决掉。我就是这么做的。通过选择解决一些难题，我学会了很多我从没听过的新技术。

你每解决3个新问题，就能学会一些新的知识。如果没有，那么更慎重的选择题目吧，一定要选择难的题目。

当你完成了SPOJ上的250道题，你会对算法竞赛有一个大致的了解，通过对基础算法的深入理解，高难度的算法题也会变得更加容易理解，以此你能够快速的运用你的知识。

现在开始在各个算法专题上更加深入的学习吧。

SPOJ上有很多资源，每个主题都有Top 10的算法和数据结构。除了那250道题，你可以从列表中获得更多题目。也有一些你从没听过的题目，从简单的题目开始学习。

如果你不强化你的知识，你就会忘记它。

当你学习一个新的算法知识点时，在SPOJ上搜索相同tag的题目，用这个算法做2到3题。

理解好DP算法，这是你赢得比赛的必要条件，以我的经验来看，每次比赛至少有一道DP题，许多人会很头疼DP题型。

如果你真的掌握了DP算法，你就离成功不远了。

我很喜欢DP题型，DP的秘诀是:考虑全局优化，而不仅仅是局部优化。你需要将问题分解成简单的子问题，每次解决一个子问题，最好将这些子问题组合起来形成解决方案。与DP相对的是贪心算法，因为这个算法每一步只考虑局部优化，而局部优化可能导致得不到最优解。

当学习新的概念时，可以看一下TopCoder的入门教程，因为这些教程很容易学，我就是看这些才真正弄明白二分索引树的。

努力学习

你听说过哪个奥林匹克冠军是没有经过数年的刻苦训练才赢得比赛的吗？美国信息学算法竞赛每一年的比赛在九月开始次年四月结束。这中间的八个月时间，我每天练习五个小时。

这五个小时我只练习算法题，有些日子我也会花8到10个小时，为什么我能做到这些，主要还是兴趣和热情所在，每天从学校回家我就直接回卧室做题，或者学习这些题里面新的算法。

如果你也想拿奖牌，也必须刻苦起来，做题然后坚持，日常生活中也需要多思考，比如你在去超市的路上，或者开车的时候。

当你睡觉的时候，你的大脑会重新组织你当天所学的，就像将书本按照字母顺序放到书架上一样，基本上你的大脑会思考每一个你遇到的问题。

你可以通过这个特点，在睡觉之前看一道难题，记住这道题需要的知识点，你并不需要解决这道题，然后入睡，你的大脑可以自动开始处理这道题，当你醒了的时候，你会惊奇的发现你已经可以解决这道题了。

试试看，你会发现这像黑魔法一样。

用vlog记录

这一段和竞赛无关，我只是想让你知道，如果你也是20岁左右，你对我看待这个世界的方式比较感兴趣，我在YouTube上有一个vlog，我在这上面发布了我对这个世界、人生和计算机科学的一些看法。

更聪明的工作，这是成功的诀窍，你需要一个目标。

我们都容易产生拖延症，看美剧总比刷DP容易，但是，你得慢慢纠正这种习惯。

如何战胜拖延症？

通过制定目标，你总能找到感兴趣的问题，因此才能学到新的知识（上面有很多资料可以参考）。因为上面推荐的SPOJ题目都是必做的，而不仅仅是看看。

我就是通过制定目标来克服拖延症的，我用一张纸做了一个日历，上面会标注每天要解决的问题。每次都提前设置好2天的问题，这样我就能知道接下来如何安排时间。

通过这种方式，我能够比较积极的完成问题，并且找到新的问题来填充后面的日历，每次完成目标，就会感觉很有成就感，希望你也能喜欢这样。

采用纸质日历，不要使用手机上的checklist之类的app，因为到第二天你可能就忘了app上的事情。

如何有效的debug？

你想变得更加专业？如果是，那么你需要练习通过大脑来debug。

这是到目前为止我所能知道的最有效的debugging技术。这种方式完全不需要调试器。你的大脑需要同时处理多个分支的情况，这样你对代码的运行情况会非常清楚，如果你只是局限在调试器，那么你可能很难掌握算法全局的运行状态。

这有点类似于大师级的棋手，每次都会往前考虑3步。

我把这种技术作为首要调试，最次才会考虑使用调试器。

在大脑中调试这种做法需要你不断地练习，当你提交一个问题报错的时候，不要用调试器，而是去阅读代码，思考这一行到底发生了什么，这个if语句会如何影响程序？如果是在循环中，这个iterator的值会是多少？

这样你一直独立自己去思考，你后面在写代码的时候其实就是在实时调试。

如果你觉得这篇文章对你有帮助，请关注微信公众号《ACM算法日常》。

关于作者

Andrei Margeloiu是一名热血程序员，爱好创业和自然，你可以在LinkedIn上联系他。

个人公众号：ACM算法日常

专注于基础算法的研究工作，深入解析ACM算法题，五分钟阅读，轻松理解每一行源代码。内容涉及算法、C/C++、软件设计等。