关于USACO美国信息学奥赛的一篇保姆级攻略

Published by jsjjyuxi on

关于USACO美国信息学奥赛的一篇保姆级攻略

国际奥林匹克竞赛是一系列赫赫有名的赛事,代表着全世界中学生学术方面的最高成就:其中数学叫IMO,物理叫IPhO,化学叫IChO,生物学叫IBO,计算机学科的就叫IOI。也许是由于计算机类奥赛所具有的“高科技”特性,从国际到包括我们中国的各个国家,五大国际奥赛中信息学都是参与人数最少、因而获奖相对容易的。 针对IOI信息学奥林匹克体系的竞赛,各国青少年都有相应的学习和选拨体系,就像每个国家都会为了奥运会挑选有天赋、肯吃苦的体育健儿加以培养一样。

中国的培养选拨体系是从前NOIP全国青少年信息学奥林匹克联赛(最近改成了CSP-S/J)(省赛)和NOI全国青少年信息学奥林匹克竞赛(国赛);美国呢,则是USA Computing Olympiad (USACO, 美国计算机奥林匹克竞赛)。 今天,小优老师想介绍USACO给我们中国学子认识一下。

海纳百川,有容乃大,一起来看看USACO有什么能够帮助到我们的地方。也许USACO会是座桥,助我们走向梦想中的星辰大海。

Part 1历史源起

登陆USACO网站,熟悉题目的时候,小优老师心底一直有个疑问:——为啥USACO题目里面全是牛?农场、奶牛、牛奶、牛排……

再看下去,仿佛进入了一个童话世界……在这些试题里,我们认识了一位名叫约翰的农夫,他拥有一家传承数代的家族经营的奶牛厂,并以拥有世界上最健康的奶牛为傲,为此他请我们大家编程替他计算每种饲料里包含的维多命含量;还为了奶牛们建造了一个游泳池,以助它们放松身心(没有自己的游泳池的人类表示扎心了)……约翰的妻子名叫贝茜,她和奶牛们都很喜欢巧克力,她还筹划过一场奶牛博览会,在这个博览会上奶牛们可以充分展示它们的智商和情商……奶牛们的日常也很温情,它们享受和约翰互发电子邮件的快乐,还喜欢疯狂地玩西洋跳棋…… ——OMG,被暖到了! 然而接下来,我又看到了一道题目:奶牛们要从农场逃跑,为此,它们设定了一组密码通讯系统……

???奶牛们在农场里好好的,为什么要逃跑?说好的相亲相爱一起白头,你却偷偷焗了油? USACO的官网网址是:http://www.usaco.org/,这个很容易Google到。他们官网的标志是……左边戴红帽子那位。

——Hi!很高兴又见到你,我就知道你不是真的想要逃跑。

官网有介绍:1992年,密斯康星大学Parkside分校数学教授Don Piele博士听说了IOI,并成立了USACO,以便将一支来自美国的团队带到活动中。

(密斯康星州是美国五十州之一,其名称来自古印第安语,意为“草地”。全州农场之中,有80%是畜牧奶牛的农场,每年出产的牛奶、牛油及Cheese,列居美国第一)

是因为这样吗?从此便有了“学编程,问奶牛”的传统?后来,由于USACO题库的影响力,别的国家,包括咱们中国引进/改编原题的大有人在,或许出于保持原著风格的考虑……直至如今,你永远能在各式各样的编程题目中,看到一头又一头的奶牛,呼啸而过。

Part 2注册报名&考试时间

这个比喝牛奶还简单。打开USACO官网首页(http://www.usaco.org/),就能看到在哪里注册报名,以及赛季时间:

红箭头指的地方,可以注册新帐号;注册的时候他们会问你的一些个人资料,如果你准备用这个帐号参赛的话,尽量耐心细致地填写你的真实情况。绿框的地方,是赛季时间表,目前放的还是2018-2019赛季的,后面会更新成2019-2020赛季的,第一场月赛近几年都在12月份。免费,免费,免费。重要的事情说三遍,USACO欢迎来自世界任何国家的选手来学习和参赛,也不需要任何资格的认定。只要你有一台能够上网的电脑,就足够。而且你一注册,就会成为Bronze青铜级别,随着你参加每一次月赛,过关斩将,级别会上升。真好,毕竟打个游戏还得充值,而且一般得刷怪刷到一两千积分,才能成为青铜战士吧。

Part 3超赞的在线学习题库

那么我就注册一下,免费成为青铜战士了,然后关机睡大觉,坐等12月的首次月赛吗?不对哦。如果你这样,就是身入宝山而空返了。USACO的赛制是不是世界最好且不论,但USACO官网提供的一个在线题库,却是全世界知名的。一旦你注册了,就能在首页上找到“训练”页面,里面有数百小时的免费教学和练习,循序渐进地提升你编程和解决问题的能力。

题库共六章,为六档难度的试题,一章比一章难,多么鲜明而又科学的结构,方便初学者逐步提高水平,避免偏颇。 每一章又分为4-5小节,每一小节集中介绍某个知识点、或者某一类型的试题,在每一个小节的开头,一般会有一篇算法介绍,然后是4-5道题,这个套路也和我们中国的课堂差不多,老师讲完知识点,再加推演验算一黑板后,炯炯有神的目光从眼镜片后面锁定你:“同学们,现在开始是我们的做题时间了!”

但是USACO还有一个设计,非常利于我们学习关于奶牛……哦不,是关于编程的知识:它的每道试题都可以提交至USACO服务器评测,且每道题都附有详细题解。你可以方便地查看测试数据和运行结果,便于调试、发现错误并改正。 而且,参考了众多深受青少年欢迎的网游设计(别问我怎么知道?猜的),UASCO还在他们的练习中加入了关卡模式,你必须将前一个小节的中所有试题正确解答后,才能解锁下一个小节的算法和题目。这训练了信息学竞赛选手的挫商,和面对复杂问题坚持不懈的品质,但也在一定程度上滋生了选手们的偏执心态和“走火入魔”的风险性,对社会的安定团结有一定副作用哈。估计是没有好好学过社会主义核心价值观。

六大章的试题共约100道,据某位已打通关的竞赛选手说:当你完成所有6大章的训练之后,还可以向USACO总教练申请开放副本……哦,不是,是申请开放额外的训练页面,进行精英级的训练。据说通关六大章的选手,保守估计,至少能在月赛里打到黄金级别,再往上的铂金级别,会涉及到更多的复杂问题、开放性问题,考的就不再仅仅是对于知识点的掌握,更多的则是要求你对算法有深入了解、熟练应用;以及考验你用编程语言解决问题的能力。还有一点想提醒各位:USACO极为重视对算法的优化和时间效率的考察,很多试题必须不断地优化算法,以达成最高效率,才能过关。

Part 4考试和晋级

你注册也注册了,学习也学过了,下一步就该考试了。(不一定要等打通关了才去考试,我们的口号是“以考代练、深入研究”)高中生、初中生和小学生注册后都可以参加月赛(第一场通常在每年的12月,以官网公布为准),高中毕业以后也可以参加,但只能以“观察者(observer)”的身份。

USACO的级别分为: Bronze 青铜级Silver 白银级Glod 黄金级Platinum 铂金级 除了新注册的选手免费获赠Bronze青铜级之外,接下来的级别,都需要你在月赛里自己打,胜出者可以进入下一级别。青铜级获胜进入白银级,白银级获胜进入黄金级,黄金级获胜进入铂金级……竞赛选手可以在每一轮月赛指定的时间范围(通常是4天,含一个周末)中的任何一个时间打开题目,并在规定的时间内完成比赛并提交。如果提交的结果是你得到了相当高的分数(满分或接近满分),系统会提示你直接晋级。恭喜!你可以在这三天内继续挑战下一等级,只要实力足够,原则上一轮月赛就可以升到满级铂金级(比游戏升级快是真的) 大部分选手没拿到满分,那么就得到本轮月赛结束后,再等1-2天,你注册的电子邮箱将收到本轮月赛的程序评测结果,还有你的分数、以及晋级分数线,这时你就知道你有没有成为下一等级的战士了。例如本轮月赛你从青铜战士晋为白银战士,下轮月赛,就直接从白银战士打起。而且这时候USACO官网还会公示测试数据、月赛题解;所有参赛选手的程序代码、成绩总表、排名(中小学生和“观察者”们分开排名);以及对比赛的分析与统计。感觉像开武林大会。USACO表现得颇有大家风范。

每个赛季的公开赛后,根据全年在线比赛和培训的成绩,16-24个中小学生会收到USACO的邀请,参加他们的Training camp集训营(相当于我们国家在清华、北大举办的NOI冬令营)。再从中选拨出4名孩子组成美国信息学国家队,参加一年一度的IOI。

再说一下USACO考试的作弊认定:1、先用一个帐户打开读题,想出解题方案后再用另一个帐户提交被明确定义为作弊;2、先考完试的选手,泄露和发布题目也是作弊;3、除非特别声明,选手必须独立完成试题,接受其他人帮助是作弊;4、选手在参加比赛时可以使用书上、互联网上或者自己曾经写过的代码,但是必须标明出处,否则也是作弊;5、直接输出答案(俗称“打表”)也算一种作弊。 Part 5考纲和难度 USACO无论是训练还是试题都比较中正,严格被包含在 IOI 考试大纲之内,中国曾经的NOIP就不是这样了,超纲比较严重,有些题目沦入偏难怪的圈圈(真诚祈愿CSP-S/J时代,一切会好起来)。这类题目就不算了哈,毕竟如果你让大家猜你前天晚上吃了什么?只要没装监控,即使是被誉为计算机科学之父的图灵本灵,也不一定能回答上来。除去这个因素,难度的比较呢?大概是下面一个排列: 青铜晋白银 ≈ 原NOIP普及组一等奖白银晋黄金 ≈ 原NOIP提高组一等奖黄金晋铂金 ≈ 原NOI一/二等奖铂金+高国际排名 ≈ CCF冬令营 日光之下并无新事,大家训练和选拨人才的机制也都差不多。那么无论你的目标是在USACO全美公开赛中刷个铂金级+高国际排名,或者你只是想考CSP-S/J,借用USACO题库做训练,以及参加他们的月赛以考代练, 那么你可能都想要知道,USACO题库有什么优越之处呢?

首先是从前的NOI和NOIP常常会参考USACO上面的题目,所以你在NOI和NOIP的试题中也会经常看到农夫约翰一家和奶牛们的身影;如果你一上国内考场,就像贾宝玉初见林黛玉那么肯定,“这道题我曾经见过!”——那么恭喜,这回真的是一道送分题了。

USACO赛制的优势:

前面说过,USACO从训练到比赛都采用了IOI赛制,选手都可能直接在比赛时反复提交评测,获得评测结果;所以美国的信息学选手在真正的IOI比赛中,往往比中国选手更加熟稔更快速,对“提交-反馈”机会的利用也强于中国选手——我们可以借用USACO的题库训练,迎头赶上。而且IOI大巨佬罗哲正还曾说过:天资聪慧的选手如果反复提交,有可能凭借一次次反馈拿到题目数据的特点,甚至数据本身……

说了这么半天,难道中国的训练方式就没有值得称道之处了吗?必须有啊!由于美国人口太少了,所以我们中国人如果玩起套路来,就没美国队什么事了。而且中国擅长什么?题海战术!无论美国信息学教练们如何冥思苦想,妙笔生花,出了多么另人拍案叫绝的题……很遗憾,中国真正高层次的选手,在“我生也有涯,而知也无涯”的刷题战术中,都已经——刷过了。

起码是刷过了模型几乎完全相同的题目。 Part 5编程语言 USACO在编程语言,允许有5个选择:C, C++, Pascal, Java和Python。Pascal这种语言几乎唤醒了小优老师的童年回忆哦,而C语言在如今也没多少人在用了……除了真正的技术神犇。剩下C++, Java和Python,如今独占编程语言的大半壁江山。上次听过一位编程机构的“老师”说,没编程经验的选手可选择Python入手,上手快,配合一定强度的练习,就可初步通过第一轮达到白银级别;白银级别以上,再推荐学习使用C++了。我真是一脸黑人问号!先学Python,达到白银级别?再学C++晋更高的级别?这么朝三暮四,请问你想过Python的感受吗?

三种编程语言不存在谁好谁坏的关系,也不是说不能同时学。如果你希望或者需要同时学,都很好,还能彼此促进,加深理解。但是没必要这样换来换去吧,又不是演川剧变脸。相对而言C++更适合信息学奥赛,即用编程的方法来解决数学的难题。而Python的优点是语法更简洁,更容易上手,而且Python是人工智能的前铺语言,未来想要成为人工智能科学家/数据科学家,选Python就没错了。 延伸阅读:三五堂刘振老师的免费公开课:未来已至,人工智能与Python

而Java,用来写网页代码,非常有优势。 Part 6中国考生参加USACO考试有没有含金量?
如果你未来想要申请美国高中/大学,那么在USACO中获得好成绩(尤其是黄金、铂金级)无疑会成为你课外活动&文书中的一大亮点;

有些年份在美国高中就读/当交换生的中国籍学生甚至能被选入USACO的夏令营和最终入选美国国家队。如2015年原杭州第二中学选手郭文景、2017年原安徽师大附中选手罗哲正通过USACO最终入选美国国家队,分别被哈佛大学、麻省理工学院录取。不过看官网上的公示,去年赛季中国选手只能到参加到公开赛为止,进夏令营和入选美国国家队的选手必须具有美国国籍或绿卡。

可以成为你参加大型科创奖赛:如TOP级别、申请藤校大杀器的Regeneron学者奖(美高学生可参加)、ISEF英特尔科学与工程大赛(面向全球学生)、GSF谷歌科学竞赛高中组(面向全球学生)的最佳计算机技术基本功训练,以及热身准备。

即使你未来还不一定非要出国留学,英语总是要学。既刷了信息学题目,又加持了英语,怎么想都是很合算。

尤其是信息学竞赛选手,将来出战IOI,也是必须用英语的。USACO的页面上有时会出现其他语言版本,他们是由已经参加学习/比赛的选手进行翻译的。但USACO官方明确表示:他们不对除英语外其他版本的题目正确性负责。 Part 6怎么学USACO 可是,USACO网站上全部都是英语题目,连一个中文字也没有(这句话好像是废话了),就算想刷,也不一定能刷得了啊!讲解算法的每篇文章,往往长篇大论,生僻词汇连篇,对于一般中国青少年学员来说,实在是太费眼又烧脑了练习中,如果学员根本读不懂题目;或者是仅能勉勉强强读题、可是却不能保证Get到了出题者的真实意图,往往无法顺利做题,假如连练习题都做不了,将来又怎么打比赛晋级、怎么冲黄金级铂金级呢?有些学员的未来人生蓝图中还有进击其它全球中学生顶级科创大奖的计划,可是有计算机、信息技术方面的专业生僻词汇拦路,差不多和南极的企鹅一样南了……

Categories: 其他