ACMRoad

ACMRoad

May 28, 2017
ACM

作为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. 等…

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

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