如何入门

前辈经验助你零基础找到全新技术领域学习方向

如何入门算法竞赛

18/07/7 17:26

朋友,你听说过算法竞赛吗?对对对!就那个一堆人对着电脑噼里啪啦敲的?不不不,那叫电子竞技!嗯嗯嗯,就是人比较多的,在体育场里的,做不出题在挠头的!嗯,这就是算法竞赛。

ACM-ICPC 2018 一场典型的算法竞赛。我校选手在照片拍摄地点的对面

ACM-ICPC 2018 一场典型的算法竞赛。我校选手在照片拍摄地点的对面

ACM-ICPC 2018 一场典型的算法竞赛。我校选手在照片拍摄地点的对面

那么究竟什么是算法竞赛呢?

著名算法竞赛选手、教练刘汝佳曾说过,算法竞赛是一种【思维的体操】。有人说了,不就是写算法吗!有什么大不了的,我平常调库百度算法写的好着呢!平常,我们写程序,写算法,都是在一种比较放松的环境下进行的。而算法竞赛会人为制造压力,例如限制编写程序的时间,禁止选手访问网络,以及利用特殊的比赛规则(如ACM竞赛中的封榜),这都给我们套上了一层无形的枷锁,让我们只能通过冷静的思考完成算法的编写。所以,我个人认为,算法竞赛是带着镣铐的【思维体操】。

那算法竞赛是怎么进行的呢?

许多竞赛都是在OJ上进行的。OJ(online judge)是指在线评测系统。首先我们需要在特定的时间和地点编写针对特定问题的算法,写出符合要求的程序,并且进行调试。完成后,会有相应的评测程序,自动编译运行你的程序,对你的程序输入不同的测试数据,进行一番【魔鬼测试】,根据测试结果给出你不同的分数。

能不能透露一些比赛的细节?

举个例子,我曾经参与过一次比赛的出题与组织工作(HBCPC2018),比赛规则为ACM赛制。比赛的过程大概是这样的:

  1. 比赛前一天选手报道,每三人为一队。有一次热身赛。热身赛赛题很简单,主要让大家熟悉比赛环境。
  2. 第二天比赛开始。选手们可以使用C/C++以及JAVA(不同比赛可用的语言不同,现在似乎Python也逐渐被算法竞赛所接受),编写12道题的程序。当你写好一道题,你可以通过题目中给的样例测试你的程序大概对不对。如果确认无误,就可以通过网页提交给评测系统。评测系统会告诉你测试结果:如答案正确(AC),答案错误(WA),运行时错误(RE),超时(TLE),输出格式错误(PE)等。
  3. 当你获得一次AC时,才算通过了这道题。系统会根据你的提交时间以及之前提交程序的次数计算你的罚时。通过题目多且罚时少的队伍排名靠前。比赛前4个小时,队伍排名会实时显示。最后一小时,队伍排名榜单会冻结,俗称“封榜“,给比赛带来一些刺激性。

不同的比赛的规则不同,常见的赛制有ACM赛制,OI赛制,Codeforces赛制。

我开发能力很强,是不是可以完虐算法竞赛了?

开发能力和算法竞赛的能力几乎不在一棵科技树上 …… 算法竞赛主要考验的是思维,而不是考验框架的熟练使用和各种库的调用。在赛场上,对数据结构和算法的掌握程度几乎成了制胜的关键。另外,竞赛当中,为了代码的快速构建,不写注释,变量名写 a,b,c,d,乱开数组,#define int long long 等等情况经常发生。这些都与开发相去甚远。

当然,如果你是一名熟练的开发人员,意味着你的代码能力很强,经过一段时间的训练,有可能成为很强的竞赛选手哦!

那,算法竞赛都有那些呢?

中小学阶段:

  • OI系列赛事。OI全称Olympiad in Informatics,信息学竞赛。在我国国内的比赛又分为NOI(National Olympiad in Informatics)和NOIP(National Olympiad in Informatics in Provinces)以及各省的省选。难度省选>国赛>省赛。每年中国会从NOI的金牌选手中选出国家集训队,最终派出强劲的zhejiang选手参加国际比赛IOI(这些比赛均是单人比赛,且有部分得分)。
  • CTSC与APIO,这两个比赛是连着的。CSTC是IOI中国国家队的选拔赛,因为集训队人太少比赛起来不好看,所以叫上全国选手陪练,难度与IOI相当。APIO是世界信息学奥林匹克亚洲赛区比赛,也是全国选手都去,最后选前6名作为中国队的成绩,难度与IOI相当。

大学阶段:

  • ACM-ICPC。这是一个由国际计算机学会举办的大型算法竞赛,也是最正规,规模最大的一个。比赛分为区域赛,区域决赛,世界总决赛,难度依次递增。比赛过程中,每个队伍可以有三个选手和一台电脑,可以互相讨论。这个比赛的一些规则使得赛事极具观赏性。
  • CCCC与CCPC。CCCC是一个单人手速赛,全靠手速和乱搞。CCPC是简单版ICPC,难度较低。
  • 蓝桥杯。比较水的比赛,我们学校好像不参加。
  • BUPT校内赛。作为北邮的学生,当然要提一下我们的校赛啦!校赛在每年的春季举行,规则与ICPC一致,欢迎各位踊跃参加!

除此之外,各大OJ和各种企业组织的比赛我们也可以去参加。列举几个有名的:codeforces、codechef、百度之星、UOJ等等。

搞算法竞赛好玩吗?我能得到啥?

好玩啊!刚开始学超有意思的!到后面成绩不行,只能靠退役之后出一出题,写一写《如何入门》之类的文章维持一下生活这样的(雾)。

说实话,学算法是一个枯燥的过程,打竞赛是一个压力很大的过程。如果你选择了这条路,可能面临假期回不了家,周六日全部报销,成绩不好整夜睡不着觉等一系列身心摧残。不过,也会得到很多别的同学得不到的东西:比如,在研究某题许久之后,一个灵光一现的思路让你成功AC的喜悦。比如,你和你的队友在奋战5小时后拿到AU,队长上台领奖时开心的微笑。比如,在你面对电脑绞尽脑汁时,场下小迷妹花痴的眼神。更多的,则是坚持于某一件事的专注,这种专注的感觉,难以形容。

当然,如果你的成绩很好,参加竞赛可以给你带来保研的加分。当你在国际大赛上获奖时,各大公司将会被你吸引,向你投出橄榄枝。在去年毕业的某位北邮ACM校队成员,就拿到了微软亚洲研究院的offer。当然,搞一年竞赛,你的代码能力和算法能力也会变得很强!

所以,想成为大佬吗?签订契约吧!

要想成为大佬,应该怎么入门呢?

首先,善用搜索引擎,当你看完这篇文章之后,你可以再去谷歌搜索如何入门,百度搜索如何入门,知乎提问如何入门。要学会自己获取信息。

然后,你需要几本合适的入门书。如果你C/C++还没学好(C++面向对象的思想在算法竞赛中不作为重点,可以只做了解),推荐你去看《C++ Primer》。如果你已经大概会写C语言了,你可以去看刘汝佳的紫书《算法竞赛入门经典》。如果你感觉刘汝佳的这本紫书太容易,那么我推荐他的姊妹篇《算法竞赛入门经典(训练指南)》和黑书《算法竞赛与信息学艺术》。我不推荐看《算法导论》,这本书太过理论化,也太难了太厚了,不适合入门。

此外,算法竞赛作为一种比赛,练习是十分重要的。举个栗子:我因为期中考试一周没做题,紧接着就被我队友虐了。然后练了两周,某场网络赛发挥就很好。然后因为期末半个月没做题,现在已经不会写tarjan算法了。

只有你接触到的题目类型够多,你才可能举一反三。从入门题库开始,一点一点的去看题,选择合适的算法去解决这道题。在这里按难度推荐一些题库:

入门水平:

  • Joy oj:原经典入门题库tyvj,被清北学堂收购后一蹶不振,前100题题目质量高。
  • 洛谷OJ:盈利性OJ,有许多入门题。
  • CodeVS:同洛谷OJ。
  • Vijos:曾经与tyvj比肩的OJ,题目难度适中,收录了大量NOIP题目。

基础水平:

  • POJ:老牌OJ,现在已经无人维护,经常无法访问。优势是题目质量高,各种题目类型齐全。
  • HDU oj:杭电OJ,有不少经典问题,并且目前有人维护。
  • 51nod:题目从简单到容易都有,贴心的分出了题目等级,可以按照等级刷题。
  • Codeforces(CF):著名的算法竞赛平台,经常有各种比赛。在CF上你可以与世界上的顶尖选手同台竞技,题目质量较高,主要考察思维能力。
  • Uva:刘汝佳推荐的题库,建议配合紫书使用。

进阶水平:

  • BZOJ(hysbz或lydsy大视野在线测评):老牌盈利OJ,一些难题需要购买VIP账号才可以看。题目主要是各省省选题,质量参差不齐,但是有很多好题。
  • UOJ:一群高中选手搞的OJ,题目比较有趣,收录了许多国家队集训题目。
  • Codechef:与codeforces类似,题目难度较高。

宇宙无敌:

  • Vjudge:一个利用爬虫等技术建立的OJ,本身没有评测机和题库,但是在上面可以提交几乎所有OJ的题目,相当于是一个OJ的聚合库。

超拽炫酷无敌吊炸天:

  • 10.105.242.83:北邮自己的OJ,是校内比赛的主要场所,也收录了许多校内赛的题目。

在刷题时,建议大家仔细思考,不要轻易看题解。如果对题解产生依赖,请多参加各种比赛,在比赛中提高自己。

最后,要有良好的心态。算法竞赛是一个需要投入大量时间的竞赛,不一定能够带来等价的回报。在做题时,也许一道题要WA好多好多遍,这时一定要心平气和,不要砸键盘,也不要摔门而去,深呼吸,也许就解出来了。

补充一点,如果参加的是ACM-ICPC,与队友的配合也是非常重要的,你可以寻找一批志同道合的小伙伴,一同做题,甚至互相出题,一起制定学习计划。这是很有趣的一件事!

北邮会对我学习算法竞赛提供哪些帮助?

在每年的春天,学校都会有归队赛、新生赛、校赛,筛选一批优秀选手进入ACM集训队。在集训队中,会有去过world final的大佬带着我们训练,每年暑假的集中训练是提升个人水平的最好机会!相比其他学校,北邮的编程气息浓厚,几乎所有人都会写代码,这也会对你的学习有帮助。

最后祝您,身体健康

最后祝您,身体健康,再见

欢迎你成为一名算法竞赛选手!愿你在退役时,抱着各种奖杯各种奖牌,还有美丽动人的女朋友!不要被水淹没

This site uses Akismet to reduce spam. Learn how your comment data is processed.