简介
入门大致分为三步,先学习 C 语言的语法,于刷题中熟练,最后学习一些基础算法。
接下来我将介绍一些入门资料。
算法竞赛怎么比
算法竞赛有多种赛制,不同赛制在资料携带、评测方式上有一定不同,但大都是在一定时限内解决算法问题。
为了评判代码的正确性,题目会准备若干数量的测试数据,你的代码只有在规定的内存、时间限制下结束并返回正确结果,才会被认为是正确的。
题目都会公开少量数据用于理解题意,称之样例。大部分题目都会隐藏后续的测试数据。因此你很有可能通过了样例,但无法通过全部的数据,所以被判为不通过。
从上面可以看出,算法竞赛对代码能力要求极高,因此在学习算法的过程中一定要重视刷题。
学习平台
通常来说,算法竞赛很少通过书籍来学习,因为网上到处是公开的资料。
互联网上有很多的 OJ(Online Judge,在线评测系统),有数万道各种难度的题目。我们只需在 OJ 上进行提交,会立即返回评测结果。
为了防止套取数据,从而写了一大堆 if-else
过题,大部分网站会对下载数据的频率做一定限制。部分 OJ 会随机打乱评测顺序。
一般来说,返回结果有如下几种类型:
- Accepted(AC),程序通过了所有数据,是正确的。
- Wrong Answer(WA),程序返回了错误的答案。
- Presentation Error(PE),程序输出含有格式错误。
- Time Limited Exceeded(TLE),程序未在规定的时间返回答案。
- Memory Limited Exceeded(MLE),程序使用了超出限制的内存。
- Runtime Error(RTE 或 RE),程序未能正常结束。
- Compile Error(CE),程序未能通过编译,无法运行。
ACM 比赛考啥
算法竞赛一般全称程序设计竞赛,考察如何设计算法以解决题目,重点是解决问题的能力。
高中也有算法竞赛,NOI 全国青少年信息学奥林匹克竞赛,五大竞赛之一,NOI 金牌可以获得清北的保送资格。很多高中参与过 OI 的学生大学会继续参加 ACM,因此差距会非常巨大,当你还为
for/if
等语法烦恼时,OIer 可能已经有 10 年代码经验了,刚入学便能够摘金夺银。但是也不必焦虑,只要努力,我们都有机会摘金夺银!
网上很少有总结 ACM 到底是啥,就一句写题。这里谈谈我的理解。
常见误区
很多不了解的人对算法竞赛有所误解,认为 ACM 类似知识竞赛,只要“博览”常见算法就能取得一个不错的成绩;也有人认为 ACM 只是对着一堆算法模版去照着敲,没多少创新,比的都是理解题目的能力。
“会的算法多”不代表“竞赛能力强”。如果把算法比作轮子的话,算法比赛比的就是谁能拿轮子造出优秀的汽车。在刚学新算法时,题目要求你造的只是一辆独轮车,而比赛时选手需要造的有可能是一辆坦克。一味的增加轮子的种类数而不去训练造车的方法,是无法在比赛中拿到好成绩的。“算法竞赛”不是“算法数量大赛”。[1]
重点是做题方法与思考能力,也就是常说的思维,而不是知识清单。这类似无招胜有招的道理。
算法竞赛更倾向于“设计”与“创造”。简而言之,你需要创造算法,而不是使用算法。
算法竞赛有点研究的气质,可能与大家接触的工程相关画风很不一致。事实也确实如此,算法竞赛和学术界的联系比较紧密。
竞赛界目前远落后于学术界,经常有选手研读并引入的论文里的算法。但在部分问题上,竞赛界也有一些领先,OI 国家集训队每年都会出一本 论文集,部分优秀论文可以发 SOSA Paper。也有很多算法选手会往计算机的理论方向发展,如 TCS(Theoretical computer science)和 PLT(Programming language theory)。