ACMRoad

作为ACM的老队员,最经常被问的不是XXX算法的问题,而是“学长我要玩ACM,我该从哪开始?”。这个问题嘛,有超过3个人问就有必要写成文字来回答,正如但凡一个操作需要两条以上命令就可以写成脚本来做一样。

就不回首往事了,尽管一路走来感慨良多啊。

新人,也有区别。你是没有程序编写基础的还是有一定代码基础的?有Py基础还是C的基础?有没有算法基础?

如果你是一个大一新生,且没有学过程序设计,或正在学,那么我建议你花最多2周,把C语言关于文件操作之前的部分学完(文件操作非必要)。不要说2周太短了,如果你打算在ACM竞赛中获得不凡的成绩,就2周。你可能天赋异秉可以花很少的时间学会C语言,这很好,说明你有个好脑子,且可以在搞好ACM的同时兼顾上课。如果你的脑子不是很棒,但是也喜欢,2周时间就必要的做些调整,课该怎么上就要考虑一下了(事实上就算是脑子很好,也要考虑一下)。

然后你可能要检测一下自己的C语言水平,尤其是在做ACM题目上的水平。此时我建议你去用2周的时间刷掉HDU平台上的第11页的题目,这上面的题目涉及到的算法比较简单,算法对应的C语言程序也比较简单,只是使用到了字符串的处理、数组的使用、结构体的使用等基本语法知识,但是会让你对这些基本知识有翻天覆地的改观,他们很简单,但是可以做出很神奇的动作。这些题目可以让你对C语言的语法更加熟练,甚至到了4岁小朋友说母语的水平一样自然而流畅,同时,当然你因为不会使用高级语法来加快代码编写速度和质量,就像4岁小朋友不会写作文一样。但是仅仅语法熟练只是一方面,同时你会学习到一些更加快速方便的函数,如使用sort()函数来排序而不是自己编写冒泡排序等傻逼的排序函数;你还会接触到强类型语言中变量的数值边界问题、数值精度问题;字符串处理的常见bug;如何编写递归代码等。你还会知道你的电脑一秒钟只能运行大约1e8次的简单数学运算,你会慢慢的学会用计算机的思维方式思考问题的解决办法。同时你还会接触到一些算法,如动态规划等。(此页中有很少的几个题目非常困难,没关系,不要管他们,但你需要完成至少90道题目)

然后你可以小声的对自己说:“我已经看到了ACM-ICPC的影子了!”。

然后你需要入门一下。这个阶段你可能会比较痛苦,因为你要做的就是不断的离开你熟悉的几行代码,转而去学习新的算法,写新的代码。而这一切,应该都没有人会仔细的教你。

到现在为止,你可能都没有学过一个完整的算法。之前做的那些水题都只是思维的开胃菜而已。那么现在你要清楚你必须去认真的、系统的学习一些算法。要能清晰的理出算法的逻辑,快速的编写出高质量且准确的代码,要能眼动查找BUG。不用担心,有人的地方都有路,已经有无数人做过这件事,所以你有章可循。

在介绍下一站之前,我必须告诉你,ACM比赛使用Linux操作系统编写代码。所以,按照我们的一致希望,我们希望你能从现在开始使用Linux并逐步使用Linux来工作,windows只是个好东西,但不是程序员的玩具,你的玩具是Linux操作系统,比赛统一使用Ubuntu操作系统作为平台,如果你对Linux一无所知,你需要去百度一下了。

至于如何安装Ubuntu操作系统和如何使用,请见其他博文或直接来实验室寻找学长的帮助(文章目前还没有整合)。

你需要去Vjudge申请一个帐号,并且开始学习[简单搜索专题]传送门。我们一致建议从这个算法专题开始,因为这里要用到的技能你学习起来会比较快速,因为你的前期技术铺垫已经做好了。其次这里的内容将会在其他的算法中使用到,所以你要从这里开始。这里的学习并没有学习资料,一切资料都在网络上,这里有的只是十几道检验你学习成果的题目,但是,这些题目与你今后比赛中遇到的题目在外形上长的已经很相似了。你大概需要一周多一点的时间来攻克这个专题。当你结束这个专题的时候你应该具备以下几条但不限于此的能力:

  1. 快速编写递归程序。
  2. 看到搜索类问题可以快速反应出解决方式并编写代码解决。
  3. 快速估算自己方案的时间空间复杂度并决定是否可行。
  4. 尝试使用高级一些的语法来编写代码,如C++中的部分内容,包括重载运算符等。
  5. 手动调试代码修改BUG而不需要依靠调试工具。
  6. 初步熟练使用Vim编写代码,并初步熟悉Linux-Ubuntu操作系统,使用简单命令来操作计算机。
  7. 熟练的从网络上寻找资源解决自己的疑问,同时可以快速的看懂别人的相关代码。
  8. 了解一些题库。

接下来你或许就不再需要这篇文章的指导了,但是,你离入门还差的远。

之后的一段时间内,算法还是要继续学习,依旧用这样的专题的形式。同时你也要去接触一下真正的比赛是什么样子,以及,真的强是什么样子。

以下平台会不定期有比赛,可视个人情况参加:

Codeforces(cf)
HihoCoder

以下算法方向需要你在未来两年内有所涉及,但是掌握这些算法并不是保障:

  1. 搜索
  2. 图论(最短路、生成树、二分图、连通图、网络流…)
  3. 动态规划(树形DP、数位DP、区间DP、斜率DP、概率DP…)
  4. 数论
  5. 数据结构(线段树、搜索树、平衡二叉树、KD树、树堆…)
  6. 字符串(KMP、Hash、AC自动机、后缀数组、字典树)
  7. 等…

推荐的书: 刘汝佳竞赛入门经典两本:紫书、大白书,链接不放了。

有些问题,可以先尝试自己回答一下,自己实在回答不了或无法找到答案回答,再提出来。

Talk is not cheap.