ACM 的正确入门方式是什么？

作者：数学lover
链接：https://www.zhihu.com/question/51727516/answer/127265733
来源：知乎
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

一般的入门顺序：
0. C语言的基本语法(或者直接开C++也行，当一个java选手可能会更受欢迎，并且以后工作好找，但是难度有点大)，【参考书籍：刘汝佳的《算法竞赛入门经典》，C++入门可以考虑《c++ primer plus》，java选手可以考虑《think in java》or中文版《java编程思想》，请远离谭浩强...】
可以选择切一些特别水的题巩固以及适应一下ACM中常见的输入输出格式...例如杭电著名的100题 Problem Set
1. 一些基本算法和数据结构(队列 栈 树 图 并查集 堆 DFS BFS 最短路 最小生成树 拓扑排序 动态规划 贪心 搜索 KMP 哈希 Trie AC自动机 快速幂 逆元 费马小定理 欧拉函数 素数筛 分解质因数)你可以找两个小伙伴一起分工合作，各自认领专题【参考书籍：刘汝佳《算法竞赛入门经典第二版》or《算法竞赛训练手册》，《算法导论》】这时候可以刷的题就多了，你可以选择一些专题进行突破，学习一下技巧 例如
[kuangbin带你飞]专题一 简单搜索
[kuangbin带你飞]专题四 最短路练习
[kuangbin带你飞]专题五 并查集
[kuangbin带你飞]专题六 最小生成树
[kuangbin带你飞]专题十二 基础DP1
[kuangbin带你飞]专题十四 数论基础
[kuangbin带你飞]专题十六 KMP & 扩展KMP & Manacher
[kuangbin带你飞]专题十七 AC自动机
如果这些你和你的小伙伴都能熟悉掌握，并且能够尽快写出来，那么没有意外的话就可以在网络赛中拿到现场赛的门票（当然还得看出题人的风格...）
2. 一些进阶的算法以及复杂一些的数据结构（树状数组 线段树 平衡树 后缀数组 二分图匹配 网络流 费用流 割点 桥 强联通 双联通 最近公共祖先 四大DP(数位dp 区间dp 状压dp 概率dp) 博弈论SG函数 ）
【参考资料：各种博客......】
[kuangbin带你飞]专题七 线段树
[kuangbin带你飞]专题九 连通图
[kuangbin带你飞]专题十 匹配问题
[kuangbin带你飞]专题十一 网络流
[kuangbin带你飞]专题十五 数位DP
[kuangbin带你飞]专题十八 后缀数组
[kuangbin带你飞]专题二十一 概率&期望
[kuangbin带你飞]专题二十二 区间DP
这些掌握之后在现场赛中拿到牌子应该就没什么问题了，发挥出色还能拿到银牌。。。不过如果遇到比较凶残的赛区...
2.5 这时候如果开始组队了，就可以去刷一些套题了，例如Contests - Virtual Judge
这里每一场比赛都是过去真实发生的录像，你可以clone之后和自己的队友一起实操一下。

3.更高深的技巧，更复杂的数据结构（树链剖分，动态树，可持久化线段树，DLX，后缀自动机，回文树，斜率优化/单调队列优化/四边形优化DP，插头dp，莫比乌斯反演......）
这部分最能体现人与人的差异了...智商碾压一般就在这部分。而要想拿到金牌，一般来说这些知识都要尽可能掌握。
【参考资料：各种论文，解题报告】
这部分的题目比较杂，因此请自行去vjudge上查找....

3.5 同2.5，并且中国国内的比赛如果已经满足不了你，你可以去https://icpcarchive.ecs.baylor.edu/index.php 或者Gym - Codeforces上找到全世界的区域赛的题目，不过题解就不怎么保证了...

也许你会觉得性价比很低，学这么多东西，才"有可能”拿到牌子，但是收获的不一定是物质的牌子，还有学习过程的苦辣酸甜的经历（例如各种WA TLE RE MLE 之后的一次AC），还有和基友一起并肩作战切套题的同甘共苦，而且还锻炼了自己的学习能力（善用百度，谷歌，维基百科）。
所以
Good Luck and Have Fun.
===============我是WA和AC之间的分割线===============

一言不合就过百赞了，好开心啊~
再补充一下：
这些算法都是说着容易，但是灵活搭配用起来难，然后还能在一定时间内写出来，并顺利通过数据测试拿到AC更难。
由于大家手上的模板越来越强大，区域赛一般都不会出现裸的模板题了，一旦出现，肯定就是被大家骂回家的存在。所以在综合训练的过程中，尽量选择需要动脑的题目，不要一昧追求直接贴一个模板上来AC走人特别爽的题目。
一般比较需要动脑的题目类型：贪心，动态规划（最好需要加上优化的），组合数学（推组合数公式，各种等价变换），图论（网络流，最短路，匹配）的各种建图过程。。。
虽然说年轻人要少水群，多做题，才能进Finals——kuangbin
但是一直闭门单刷也不是一件好事，还是要和大家多多交流心得，这样才能避免自己陷入一个瓶颈。

 

作者：王皓皓
链接：https://www.zhihu.com/question/51727516/answer/153850404
来源：知乎
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

刚刚学习ACM的同学往往存在很多困惑，不知道从何入手学习，在这篇文章里，我希望能将自己不多的经验与大家分享，希望对各位有所帮助。

一、语言是最重要的基本功

无论侧重于什么方面，只要是通过计算机程序去最终实现的竞赛，语言都是大家要过的第一道关。亚洲赛区的比赛支持的语言包括C/C++与JAVA。首先说说JAVA，众所周知，作为面向对象的王牌语言，JAVA在大型工程的组织与安全性方面有着自己独特的优势，但是对于信息学比赛的具体场合，JAVA则显得不那么合适，它对于输入输出流的操作相比于C++要繁杂很多，更为重要的是JAVA程序的运行速度要比C++慢10倍以上，而竞赛中对于JAVA程序的运行时限却往往得不到同等比例的放宽，这无疑对算法设计提出了更高的要求，是相当不利的。其实，我并不主张大家在这种场合过多地运用面向对象的程序设计思维，因为对于小程序来说这不旦需要花费更多的时间去编写代码，也会降低程序的执行效率。

接着说C和C++。许多现在参加讲座的同学还在上大一，C的基础知识刚刚学完，还没有接触过C++，其实在赛场上使用纯C的选手还是大有人在的，它们主要是看重了纯C在效率上的优势，所以这部分同学如果时间有限，并不需要急着去学习新的语言，只要提高了自己在算法设计上的造诣，纯C一样能发挥巨大的威力。

而C++相对于C，在输入输出流上的封装大大方便了我们的操作，同时降低了出错的可能性，并且能够很好地实现标准流与文件流的切换，方便了调试的工作。如果有些同学比较在意这点，可以尝试C和C++的混编，毕竟仅仅学习C++的流操作还是不花什么时间的。

C++的另一个支持来源于标准模版库（STL），库中提供的对于基本数据结构的统一接口操作和基本算法的实现可以缩减我们编写代码的长度，这可以节省一些时间。但是，与此相对的，使用STL要在效率上做出一些牺牲，对于输入规模很大的题目，有时候必须放弃STL，这意味着我们不能存在“有了STL就可以不去管基本算法的实现”的想法；另外，熟练和恰当地使用STL必须经过一定时间的积累，准确地了解各种操作的时间复杂度，切忌对STL中不熟悉的部分滥用，因为这其中蕴涵着许多初学者不易发现的陷阱。

现在我们转入第二个方面的讨论，基础学科知识的积累。

二、以数学专业为主的基础知识十分重要

虽然被定性为程序设计竞赛，但是参赛选手所遇到的问题更多的是没有解决问题的思路，而不是有了思路却死活不能实现，这就是平时积累的基础知识不够。竞赛中对于基础学科的涉及主要集中于数学，此外对于物理、电路等等也可能有一定应用，但是不多。因此，大一的同学也不必为自己还没学数据结构而感到不知从何入手提高，把数学捡起来吧！

下面我来谈谈在竞赛中应用的数学的主要分支：

1、离散数学——作为计算机科学专业的基础，离散书序是竞赛中涉及最多的数学分支，其重中之重又在于图论和组合数学，尤其是图论。

图论之所以运用最多是因为它的变化最多，而且可以轻易地结合基本数据结构和许多算法的基本思想，较多用到的知识包括连通性判断、DFS和BFS，关节点和关键路径、欧拉回路、最小生成树、最短路径、二部图匹配和网络流等等。虽然这部分的比重很大，但是往往也是竞赛中的难题所在，如果有初学者对于这部分的某些具体内容暂时感到力不从心，也不必着急，可以慢慢积累。

竞赛中设计的组合计数问题大都需要用组合数学来解决，组合数学中的知识相比于图论要简单一些，很多知识对于小学上过奥校的同学来说已经十分熟悉，但是也有一些部分需要先对代数结构中的群论有初步了解才能进行学习。组合数学在竞赛中很少以难题的形式出现，但是如果积累不够，任何一道这方面的题目却都有可能成为难题。

2、数论——以素数判断和同余为模型构造出来的题目往往需要较多的数论知识来解决，这部分在竞赛中的比重并不大，但只要来上一道，也足以使知识不足的人冥思苦想上一阵时间。素数判断和同余最常见的是在以密码学为背景的题目中出现，在运用密码学常识确定大概的过程之后，核心算法往往要涉及数论的内容。

3、计算几何——计算几何相比于其它部分来说是比较独立的，就是说它和其它的知识点很少有过多的结合，较常用到的部分包括——线段相交的判断、多边形面积的计算、内点外点的判断、凸包等等。计算几何的题目难度不会很大，但也永远不会成为最弱的题。

4、线性代数——对线性代数的应用都是围绕矩阵展开的，一些表面上是模拟的题目往往可以借助于矩阵来找到更好的算法。

5、概率论——竞赛是以黑箱来判卷的，这就是说你几乎不能动使用概率算法的念头，但这也并不是说概率就没有用。关于这一点，只有通过一定的练习才能体会。

6、初等数学与解析几何——这主要就是中学的知识了，用的不多，但是至少比高等数学多，我觉得熟悉一下数学手册上的相关内容，至少要知道在哪儿能查到，还是必要的。

7、高等数学——纯粹运用高等数学来解决的题目我接触的只有一道，但是一些题目的叙述背景往往需要和这部分有一定联系，掌握得牢固一些总归没有坏处。

以上就是竞赛所涉及的数学领域，可以说范围是相当广的。

三、数据结构与算法是真正的核心

先说说数据结构。掌握队列、堆栈和图的基本表达与操作是必需的，至于树，我个人觉得需要建树的问题有但是并不多。（但是树往往是很重要的分析工具）除此之外，排序和查找并不需要对所有方式都能很熟练的掌握，但你必须保证自己对于各种情况都有一个在时间复杂度上满足最低要求的解决方案。说到时间复杂度，就又该说说哈希表了，竞赛时对时间的限制远远多于对空间的限制，这要求大家尽快掌握“以空间换时间”的原则策略，能用哈希表来存储的数据一定不要到时候再去查找，如果实在不能建哈希表，再看看能否建二叉查找树等等——这都是争取时间的策略，掌握这些技巧需要大家对数据结构尤其是算法复杂度有比较全面的理性和感性认识。

接着说说算法。算法中最基本和常用的是搜索，主要是回溯和分支限界法的使用。这里要说的是，有些初学者在学习这些搜索基本算法是不太注意剪枝，这是十分不可取的，因为所有搜索的题目给你的测试用例都不会有很大的规模，你往往察觉不出程序运行的时间问题，但是真正的测试数据一定能过滤出那些没有剪枝的算法。实际上参赛选手基本上都会使用常用的搜索算法，题目的区分度往往就是建立在诸如剪枝之类的优化上了。

常用算法中的另一类是以“相似或相同子问题”为核心的，包括递推、递归、贪心法和动态规划。这其中比较难于掌握的就是动态规划，如何抽象出重复的子问题是很多题目的难点所在，笔者建议初学者仔细理解图论中一些以动态规划为基本思想所建立起来的基本算法（比如Floyd-Warshall算法），并且多阅读一些定理的证明，这虽然不能有什么直接的帮助，但是长期坚持就会对思维很有帮助。

四、练习、练习、再练习

知识的积累固然重要，但是信息学终究不是看出来的，而是练出来的，这是多少前人最深的一点体会，只有通过具体题目的分析和实践，才能真正掌握数学的使用和算法的应用，并在不断的练习中增加编程经验和技巧，提高对时间复杂度的感性认识，优化时间的分配，加强团队的配合。总之，在这里光有纸上谈兵是绝对不行的，必须要通过实战来锻炼自己。

大家一定要问，我们去哪里找题做，又如何检验程序是否正确呢？这大可不必担心，现在已经有了很多网上做题的站点，这些站点提供了大量的题库并支持在线判卷，你只需要把程序源码提交上去，马上就可以知道自己的程序是否正确，运行所使用的时间以及消耗的内存等等状况。下面我给大家推荐几个站点（多是世界大学排名靠前的学校推出的）：

1、Ural：Ural是中国学生对俄罗斯的Ural州立大学的简称 ，那里设立了一个Ural Online Problem Set，并且支持Online Judge。Ural的不少题目算法性和趣闻性都很强，得到了国内广大学生的厚爱。

2、UVA：UVA代表西班牙Valladolid大学(University de Valladolid)。该大学有一个那里设立了一个PROBLEM SET ARCHIVE with ONLINE JUDGE ，并且支持ONLINE JUDGE，形式和Ural大学的题库类似。不过和Ural不同的是，UVA题目多的多，而且比较杂，而且有些题目的测试数据比较刁钻。这使得刚到那里做题的朋友往往感觉到无所适从，要么难以找到合适的题目，要么Wrong Answer了很多次以后仍然不知道错在那里。 如果说做Ural题目主要是为了训练算法，那么UVA题目可以训练全方位的基本功和一些必要的编程素质。

3、ZOJ：ZOJ是浙江大学建立的ONLINE JUDGE，是中国大学建立的第一个同类站点，也是最好和人气最高的一个，我和许多班里的同学就是在这里练习。ZOJ虽然也定位为一个英文网站，但是这里的中国学生比较多，因此让人觉得很亲切。这里目前有500多道题目，难易分配适中，且涵盖了各大洲的题目类型并配有索引，除此之外，ZOJ的JUDGE系统是几个网站中表现得比较好的一个，很少出现Wrong Answer和Presentation error混淆的情况。这里每月也办有一次网上比赛，只要是注册的用户都可以参加。

4、北京大学的ACM网站

以上

 https://www.zhihu.com/question/51727516/answer/127265733