算法竞赛简介

算法竞赛,指的是以算法(和数据结构)为核心主题的编程竞赛。算法竞赛一般要求在规定时间内做若干道题目,并以编程的方式解决问题,可以使用 C/C++/Pascal/Java 等语言(视比赛要求而定)。竞赛规则

算法竞赛胜利的目标不尽相同,但是,如果你能在规定时间内正确解答所有题目,那么你肯定是赢家。

线下竞赛

NOI 系列(中学生)

NOI 系列比赛是初中生和高中生参加的比赛。高中五大学科竞赛分别是数学、物理、化学、生物、信息学,其中信息学就是这个系列的比赛。

最底的比赛是分区联赛(NOIP)。NOIP 分普及组和提高组,普及组是初中生参加的,提高组是高中生参加的。NOIP 分初赛(笔试)和复赛(上机)。初赛晋级之后进入复赛。

关心竞赛的,初赛一般都能过。所以不需要担心什么了。

复赛的一些比赛情况(这里是 2014 年的情况):

  • 个人赛
  • 时间和题量:一般是 11 月的第三个周末。NOIP 复赛分两天进行,每天三道题。每道题 100 分,故总分 600 分。
  • 编程语言:使用 C/C++/Pascal 语言。因为是算法竞赛,所以不需要学习类和类库的用法。
  • 编程要求:每道题会有题目要求、输入输出格式和范例。你需要根据题目要求编程,严格按要求从文件中读取数据,进行处理,并严格按照要求输出答案。你需要按照要求将程序代码保存到电脑的指定路径。
  • 反馈:比赛结束之前不会有任何反馈。
  • 测评:比赛全部结束之后,程序会交到指定单位进行统一测评。每道题一般有 10 个固定的数据点,每个数据 10 分(有的题目是 20 个数据,每个数据 5 分)。测评系统会让你的程序读入这些数据,并检查你程序输出的结果是否与答案一致。
  • 测评结果:对于每个数据,存在以下几种状态。只有数据通过才能得分,错了不会额外扣分。假如一道题 10 个数据点你的程序通过了 6 个,那么这道题得 60 分。
    • 通过:你的程序输出的结果与答案一致,该数据点得分。
    • 编译错误:程序无法通过编译。由于有些省份不采用标准环境,所以很有可能在头文件上出问题。
    • 答案错误:答案错误,或者你的程序没有严格按照要求来输入输出数据。
    • 超时:你的程序没有在规定时间之内结束。不能得分。
    • 运行时错误:你的程序崩溃,同样不能得分。
  • 成绩:你最后知道的是通过的数据点累计的总分。分数越高越好。获得国家级一等奖之后有机会晋级,参加省队,从而继续参加更高级的比赛。最高级别是世界奥林匹克。
    • 因为现在参加奥赛不加分不保送,所以参加人数减少。只要你不生在变态的省份,拿一等奖其实不难。
  • 其他:
    • 不能携带参考资料。
    • 因为是黑盒测试,所以骗分合法。例如某题不会做,但是题目中有一句“如果无解,请输出-1”,那么你直接让程序输出 -1 也有可能得分。

ACM/ICPC 系列(大学生)

ACM/ICPC 本是美国的编程比赛。现在全世界都流行了(没错,朝鲜人也参加)。

ACM 比赛是大学生参加的比赛。与 NOIP 相比,ACM 的线下比赛比较多(学校举办的、省里举办的、某个学校的邀请赛……)。

ACM 比赛的情况:

  • 团体赛:三人共用一台电脑。
  • 时间和题量:5 个小时,10 道题左右。题量很大。
  • 编程语言:使用 C/C++/Java 语言。因为是算法竞赛,所以不需要学习类和类库的用法。
  • 编程要求:一般情况下题目是全英文的。每道题会有题目要求、输入输出格式和范例。你需要根据题目要求编程,严格按要求读取数据,进行处理,并严格按照要求输出答案。完成编程之后,可以立即提交代码并获得反馈信息。
  • 反馈:在提交代码之后立刻得到反馈。比赛期间可随时查看其他队伍的完成情况。最后一小时封榜(状态不再更新)。
  • 测评:提交代码之后立刻测评。一般情况下,测评系统会让你的程序读入一些标准数据,并检查你程序输出的结果是否与答案一致。
  • 测评结果:一般情况下,每道题会有以下几种状态。只有完全通过(Accepted)的题目才算完成。
    • 通过(Accepted):你的程序通过了所有的数据点,和答案全部一致。(和 NOIP 不同)
    • 编译错误(Compile Error)
    • 答案错误(Wrong Answer):答案错误,或者你的程序没有严格按照要求来输入输出数据。
    • 超时(Time Limit Exceeded):你的程序没有在规定时间之内结束。不能得分。
    • 运行时错误(Runtime Error):你的程序崩溃,同样不能得分。
  • 成绩:完成的题目越多,排名越靠前。完成题目同样多的话,总用时越少的排名越靠前。
    • 总用时是所有已完成题目的用时之和。每个题目的用时为实际用时加罚时。有一次不通过的提交,罚时就加 20 分钟。假如 A 题前三次提交不通过,第四次提交才通过,此时距离比赛开始已经 40 分钟,那么此题用时是 40+20x3=100 分钟。
    • 未通过的题目不计入总用时。
  • 其他:
    • 可以携带不限数量的纸质资料,不能带电子资料。因此许多参赛队伍会提前把一些常用的算法和数据结构的代码打印出来以节省编程时间。
    • 三个人只有一台电脑,团队之间要配合好。此外,在正式比赛中可通过打印服务打印代码。
    • 校外比赛一般都是校队的才有机会参加。

线上竞赛

Online Judge

很多在线测评网站不仅是题库,而且会不定期地办一些在线比赛。

比赛不一定有奖励,但是按照正式比赛的时间、正式比赛的要求去参加这些在线比赛会对提高比赛水平有很大帮助。

Codeforces

Codeforces(行内简称 CF)是俄罗斯一个著名的 Online Judge 网站,之所以将其单列出来,是因为它有一套独特的比赛规则。

  • 时间和题量:Codeforces 的比赛为 2 小时 5 道题。
    • 由于 Codeforces 采用的时区和中国不同,因此中国人常常需要熬夜(半夜 11 点或 12 点)参加比赛。
  • 分组:一般情况下,每场 Codeforces 比赛有两组(Div 1 和 Div 2),分别供积分(Rating)超过 1700 和不足 1700 的选手参加。新用户的积分是 1500。
    • 如果确实分为了 Div 1 和 Div 2,那么 Div 1 的 ABC 三题和 Div 2 的 CDE 三题是一样的。
    • Room:选择 Div 之后你会被随机分到一个房间(Room)中,一个房间大约 30 人。
  • 编程:同样是按照要求输入输出。可以使用各种主流编程语言 ,如 Python。
  • 测评:比赛期间系统只用前几组标准数据进行测评(实际上数据有几十甚至上百个)。如果这一小部分通过,那么被称作“Pretest Passed”。比赛结束后会使用全部数据进行统一测评,这被称作“System Test”。
  • 计分:如果某题通过,那么得分为当前分数减去 50 x 不成功的提交次数。某道题的分数是由比赛开始时的分数随时间线性减少得到的。最终得分以 System Test 为准。
  • Hack:这是 Codeforces 的特色之一。当某道题 Pretest Passed 之后,你可以选择锁定代码。锁定之后即可查看同房间内其他人的代码,并从中寻找漏洞,构造使其出错的数据。如果你的数据使对手的程序出错,那么就被称作“Successful hacking attempt”,你得 100 分。但是 Hack 失败,你会被扣 50 分。
    • 不管你是否锁定代码,只要其他人锁定了自己的代码,就可以 Hack 你。
    • Hack 成功的数据会被加入到标准数据中。

由于 Codeforces 的比赛模式很新颖,因此已经被 HDU 和 ACdream 等网站学习。题目质量也不错。

商业公司比赛

很多商业公司也会举办有奖竞赛,例如 TopCoder、百度程序之星等。

ACM 社团

想参加 ACM 比赛,当然要参加自己学校的 ACM 社团了,要不然哪里有去校外比赛的资格?

只要坚持到退役,你一定不会感到后悔。

辅导书

经典教材非《算法竞赛入门经典》(刘汝佳,清华大学出版社)莫属。最新版是第二版,封面以紫色为主色调。可从当当网上在线购买。

《算法艺术与信息学竞赛》也是刘汝佳的经典教材,不过难度很大,是给高手看的。

此外还有很多专为算法竞赛编写的竞赛书籍、算法与数据结构书籍,不妨多读一读。

在线测评网站

在线测评网站就是在网上做题、提交程序,然后查看反馈情况。有的够意思的网站会把详细情况告诉你,有的则不会。

很多题目可以到网上搜到题解,在想不出如何解决的情况下可以看一眼。

以下都是经典的在线测评网站。欢迎多刷题:

  • POJ:北京大学 OJ。
  • UVa:《算法竞赛入门经典》、《算法竞赛入门经典-训练指南》的练习题都在这里。网站辅助工具有 uHuntuvatoolkit
  • HDU (杭电ACM):杭州电子科技大学 OJ。刷题时请从第 11 页开始刷。
  • ZOJ:浙江大学 OJ。
  • Codeforces (CF):俄罗斯的网站。可以用 Python 等语言编程。Codeforces 的比赛也很有特色。
  • ACdream:这是一个社区组织的群和 OJ。
  • Virtual Judge:Virtual Judge 不是真正的在线测评,因为它的题目是通过机器人抓过来的,而且提交都是通过机器人到对应的网站去交。网站本身没有数据。Virtual Judge 还有一大特色就是“模拟参加”,也就是原比赛早已结束,但是整个过程看起来就像是你和其他用户“同时”竞技。由于 Virtual Judge 比赛质量差别很大,所以要谨慎对待。
  • USACO Training:美国官方训练教材。循序渐进(必须按顺序做题),并给详细数据和解析。