NBUT-ACMer学习地图

什么是算法竞赛？

顾名思义，算法竞赛，指的是以算法（和数据结构）为核心主题的编程竞赛。选手需要在规定的时间内用编程的性质完成若干道题目，题目往往涉及各种算法和数据结构的应用。

那么算法竞赛的题到底是什么样的？比如下图就是一道非常经典的入门题目a+b：

题目要求输入两个数a，b，你的程序要输出a+b的值，输入输出样例为题目给的示例，程序通过了样例不代表通过了题目，只有通过了该题所有的测试数据才算通过

一道题会有若干组数据以及对应的答案，当你把代码提交上去后，评测机会把这些数据输入到你的程序中，如果你的输出和预期的答案一样，且运行时间和空间在规定范围内，那么恭喜你！你通过（Accepted，AC）了该题

反之，评测机会把你程序产生的各种错误返回给你，如答案错误（Wrong Answer，WA）、时间超限（Time Limited Exceed TLE）、空间超限（Memory Limited Exceed MLE）等

这种能够在线提交题目进行评测的网站平台就叫做在线评测系统（OJ，Online Judge），竞赛平时的训练也是依靠各大OJ来进行的

各类赛制介绍

在介绍各类比赛前先来介绍三种赛制：ACM，OI，IOI

OI赛制：

选手提交每道题之后没有任何反馈，每道题目不限制提交次数，最终分数以最后一次提交为准，每道题设置部分分，赛后统一评测，就类似初高中的各类考试。

什么是部分分？就比如说一道题有20个数据评测点，而我的代码只能通过其中10个数据评测点，那么我在这题里我就只能得到50%的分数

使用该赛制的比赛：蓝桥杯

IOI赛制：

和OI赛制唯一不同的点就是提交后能立刻就能看到评测结果且不限制提交次数，其它部分和OI赛制完全一样，算是最“良心”的赛制

使用该赛制的比赛：团体程序设计天梯赛，CAIP

ACM赛制：

选手提交每道题之后能立刻看到评测结果，每道题目不限制提交次数，没有部分分，需要完全通过一道题的所有测试点才算通过该题，提交错误一次往往会有20分钟的罚时（只计算通过了的题的罚时），最后排名先看通过题数，通过题数越多，排名越靠前，通过题数相同的情况下看总耗时，耗时越少，排名越靠前（每道题的耗时为：第一次通过该题的时间+罚时次数×20）。在 ICPC 相关赛事中，选手允许带一定量的纸质资料。

使用该赛制的比赛：ZCPC，ICPC，码蹄杯，百度之星

各大知名比赛介绍

ICPC亚洲区域赛（官网 北京总部官网 ）：（英文：International Collegiate Programming Contest，中文：国际大学生程序设计竞赛）由 ICPC 基金会举办，是最具影响力的大学生计算机竞赛。由于以前 ACM 赞助这个竞赛，也有很多人习惯叫它 ACM 竞赛。

通常在每年的9到12月举办5到7场亚洲区域赛，参赛名额通常由上半年的各种邀请赛/省赛以及下半年的网络赛来选拔。同一个人一年最多能参加两场区域赛，比赛前60%获奖，金银铜比例为1:2:3，在区域赛中银牌及以上的队伍可以获得参加12月中旬举办的EC-Final（东亚决赛）的名额。

团体程序设计天梯赛（官网）：线上赛，十人团队赛，说是团队赛但其实还是各做各的，评奖分个人奖和团队奖，总分300，175分以上按1:3:6分为一、二、三等奖，由于是每年固定分数线获奖+IOI赛制+赛题难度不高，算是所有算法竞赛中最容易获得国奖的比赛之一

蓝桥杯（官网）：线下赛，所有算法竞赛中参赛人数最多的一个，分为省赛和国赛，其中省一等奖选手（全省前10%）可以进入到国赛，浙江省算竞水平总体较高，省一等奖没有网上很多人说的那么好拿。总的来说难度适中，由于是OI赛制，需要有一定的赛时策略

各大ICPC邀请赛：线下赛，一般用于筛选下半年对应的区域赛名额，获奖比例赛制等均等同ICPC，难度的话大概是2/3个区域赛的样子

浙江省大学生程序设计竞赛（ZCPC）：线下赛，对标ICPC的浙江省赛，获奖比例赛制等均等同ICPC，难度近似ICPC邀请赛，获奖后可得到下半年ICPC杭州区域赛的入围名额

RAICOM CAIP编程技能赛：线上赛，分省赛和国赛，晋级规则同等蓝桥杯，难度接近天梯赛，涉及到的算法可能会比天梯赛更多一点，国赛获奖比例非常高，基本上去了就有

ICPC网络赛：用于选拔下半年各大区域赛的参赛名额，每个学校的排名取决于该校排名最高的队伍。

码蹄杯和百度之星目前暂时不在我校的竞赛名单中，这里就不详细展开了

我该如何学习算法竞赛？

前言

先来介绍一些常用的训练网站和教程：

训练网站：

洛谷：国内规模最大的算法竞赛OJ，主要面向初高中的OI选手，但也非常适合ACM的入门学习

codeforces：俄罗斯算法竞赛平台，有非常多的高质量比赛（由于时区不一样，比赛时间会比较阴间）和题目，绝大多数竞赛选手的主要训练网站。codeforces使用指南

atcoder：日本算法竞赛平台，题目质量高，思维性强，每周都会举办各种类型的比赛

牛客竞赛：每周会固定举办若干场比赛，套路题和技巧题较多，适合新手入门练习

vjudge：并不是一个独立的OJ，而是一个远程评测平台，一般仅用于实验室的周赛练习

推荐教程：

OI Wiki：一个持续更新的算法竞赛知识整合站点，可以理解为一个在线的算法竞赛字典。有非常全面的竞赛相关的知识。

董晓算法：一个讲解算法模板和题目非常清晰的老师

刘春英老师：杭州电子科技大学ACM教练

阶段零 「基本语法学习」

推荐时间：一个月

目标：学会C/C++基础语法，能用代码表达自己的想法

这个阶段是学习计算机的开始，也是加入实验室的前置条件。利用开学初的这段时间，找一个C/C++语言教程跟着学，同时在「萌新入门100题」中刷相关的题，建议先把语法部分学完再来做题

有些教程连着把一堆开发相关的知识都教了，算法竞赛不涉及开发相关，尽可能选一些相对入门的教程跟着学

对于绝大部分的浙江的考生，高中应该都是有学习过vb的，相对来说上手会快一点，高中未接触过编程相关的，也不用担心，基础语法相关的内容没什么太大的难度，很快就能学会

需要掌握的能力：

了解程序的基本输入输出，顺序结构，循环结构，各类变量类型，数组，函数与结构体等基础知识

了解如何使用洛谷

了解OJ中的AC，WA，TLE，MLE等各种返回值的含义

能解决大部分的编译错误

另外，虽然实验室的招新条件只要求写满30题，但个人建议如果是零基础码力弱的话有时间能多写点就多写点，尽量写到50+

Q&A：

Q：有没有什么推荐的入门教程？

A：推荐的C/C++入门教程：

OI-wiki 文字教程
竞赛C++语法入门教程 视频教程
《深入浅出程序设计竞赛 – 基础篇》 书籍教程。入门阶段非常推荐跟着这本书学，有配套例题

Q：开学要军训，时间不够怎么办？

A：认真学的话，学完基本语法大概一个星期左右就能做到，暂定截止日期是10月13号，不算上军训也有两个星期的时间，完全够学完基础语法了

Q：C和C++有什么区别？

A：从算法竞赛的角度来说，竞赛中用到的C++其实只能算C with STL，你可以把它当成多了一些额外内容的C语言

阶段一「基本算法学习」

推荐时间：三个月左右（大一上学期）

目标：学习并掌握最基本的算法与数据结构，熟练掌握时间复杂度，空间复杂度的概念

从这里开始就要正式学习算法了，实验室每周都会进行对应知识点的周练周赛以及周讲，简单来讲这个阶段需要做的事情就是多学多练，学习基本算法，锻炼基本的码力，以及养成一定的学习能力。

除了实验室的日常训练内容外也可以试着打打codeforces上的div3/4以及atcoder上的abc，感受下赛时的氛围，注意无论是实验室的周赛还是cf和at上的比赛，打完网络赛后务必记补题，不然跟不打没区别，补题的话补自己掌握的算法范围内的题目就行了，如果题里有还没学过的算法可以先放着

需要掌握的能力：

掌握暴力枚举，二分，位运算，贪心，递推/递归，DFS/BFS，栈，队列，链表，并查集，STL，简单图论等基本算法
了解如何使用各大OJ平台来进行练习
有一定的自学能力

Q&A：

Q：遇到不会做的题要思考多久再去看题解？题解要怎么看？

A：首先对于题目先分为两类：一是各类算法模板，二是练习题，对于算法模板，首先得先理解算法的思路和过程，理解了过程后可以试试自己写一遍，也可以来参考网上或者学长的模板写法，对于练习题，如果15~20分钟后还是没什么思路就可以去看题解了，看题解的话先别去看题解的代码，去看题解的思路，能理解思路的话就先自己写写试试，前期非常有助于锻炼码力，等到实在理解不了思路或者不知道代码要怎么写的时候再去参考题解的代码

Q：网上看到很多人都在写学习博客，写博客有用吗？如果要写博客的话要怎么写？

A：个人认为写博客对整理知识有一定帮助，但并非必需品，更多地是用来记录自己的一个学习过程，而且把自己的学习心得放到网上给别人参考也是蛮有意思的，如果要写个人博客的话，推荐使用博客园，或者用hexo等框架搭建一个个人网站

阶段二「备战算法竞赛」

推荐时间：四到六个月（大一下学期）

目标：学习并熟练掌握所有区域赛铜牌难度及以下的算法与数据结构，有一定的思维能力

可能的收获：蓝桥杯国奖，天梯赛国奖，ZCPC、ICPC邀请赛铜牌，CAIP国奖

这个阶段的算法学习跟前一个阶段差不多，只是难度相对来说会高一点，学完这个阶段的算法基上所有区域赛铜牌及以下难度的题就不会有自己没学过的算法了，比学新算法更重要的是，这个阶段一定要多打网上的训练赛，训练自己的思维能力，比如codeforces上的div2/3/4以及atcoder上的abc，ICPC相关的比赛思维性都很强，很多ICPC的前期题就是纯粹的数学题，不涉及任何算法

同时，4~8月是每年几乎所有算法竞赛（除了区域赛）的举办时间，如果这个阶段学习的还不错的话，就有机会拿到自己的第一个奖项了，对于不同的赛制也要有一定的策略，比如说不要在IOI/OI赛制的比赛中一直死磕一道题/在ACM赛制里对于不确定的代码不加以验证就交上去

这个阶段推荐跟着书籍《算法竞赛进阶指南》来学习，书上很多专题性内容讲的都非常好，有配套例题

需要掌握的能力：

掌握最短路，最小生成树，动态规划，线段树，ST表，树状数组，基本数论，KMP与哈希等区域赛铜牌难度及以下的算法
对一定的比赛策略
有一定的思维能力
达到一定的刷题量
cf的rating能达到1400+或at的rating达到1200+

阶段三「剑指区域赛」

推荐时间：四个月~一年（大一暑假+大二）

目标：有较强的思维能力，队伍能够合理互补配合，codeforce至少达到1600+的水平

可能的收获：ICPC区域赛铜牌及以上，ZCPC、ICPC邀请赛铜牌及以上

从这边开始就是基本都得靠个人/队内自行学习了，相信坚持到这一步的人也有较强的自学能力了，这个阶段没有很固定的训练方法，基本上就是：刷题→遇到不会的技巧或算法→把不会的算法/技巧学会 的循环

这个阶段也是要多打网络赛，提升自己的思维水平，多打打codeforces上的div2和div3atcoder上的abc和arc，这个阶段就不要沉迷学习各种更高级的算法了（除非团队能稳铜牌），绝大多数区域赛铜牌难度以下的题不需要什么高级算法，都是考思维，同时也要注意锻炼一下团队的配合，多去组队训练几场前几年的各大区域赛真题。

需要掌握的能力：

能做出cf上大部分难度位于1600~1900的题

对各个算法有一定的转化能力

合理的团队配合

总结

打算法竞赛的好处

锻炼程序设计能力，可以普通二本里一个打过算竞的学生和一个没打过算竞的学生，如果二者的开发经验差不多，码力差距是很大的
秒杀各类算法笔试题，绝大多数算法笔试题在ICPC区域赛中只能算得上“签到题”
提高思维水平、自学能力、抗压能力、团队合作能力、英语阅读能力等，对未来考研和求职都会有很大帮助。
拓展眼界，挑战自己，在ACM赛场上你能见到来自各种学校的大佬，可以说几乎没有任何一所985211是不参加ACM的，不出去走走永远不知道外面的世界有多大，同时也让普通二三本也有搏杀一本甚至985211等顶级高校的机会，证明自己高考考不过他们不是自己比他们笨，或者比他们懒

算法竞赛和其它竞赛相比的优点和缺点

优点：

门槛低，入门快，不需要学习额外的软件和开发技能

比赛众多，一年至少有10+场大大小小的比赛（有各种公费旅游的机会）

相比起其它一些枯燥的竞赛，过程会更加有趣，比如每次线下赛比完后刺激的滚榜环节（2024ZCPC,2024昆明），还有知名比赛平台codeforces的rating系统，有一种打游戏里的“排位赛”的感觉

绝对客观，完全的个人能力比拼，没有任何强校优势的比赛，即使是专科在比赛中也有超越一本甚至985211的机会，比如今年浙江省acm比赛中，宁波职业技术学院的一队超越了一众浙江省强校

缺点：

需要一定的数理水平
ICPC区域赛相关的比赛有一定难度，需要较多的训练

结语

大学里像ACM这样能有比较纯粹的竞赛体验的比赛并不多，选择打算法竞赛也许不是大学里的最优路线，但一定是一条有意义且有趣的路，如果选择了走这条路，就静下心来，好好把这条路走好，如果不走这条路，也不要浪费大学的四年时光，去做其它有意义的事情，或者去享受生活

__EOF__

本文作者： AnonTokyo 本文链接： https://www.cnblogs.com/AnonTokyo/p/18402328 关于博主： 评论和私信会在第一时间回复。或者直接私信我。 版权声明： 本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！ 声援博主： 如果您觉得文章对您有帮助，可以点击文章右下角【推荐】一下。