21-22年USACO计算机竞赛全解

申请全球TOP大学无论是美国藤校还是英国G5都需要通过层层选拔，在众多学生的申请资料中，如何才能脱颖而出？获得全球重量级学术活动金奖或者优异排名，帮助你成为闪亮的那颗星。而国际学术活动的作用还不止于此，在学术活动的过程中拓展相关领域的学术知识，让参赛同学感受到学科的乐趣, 激发主动求学的好奇心，并能与全球出类拔萃的学子们以公平的方式同台竞技，以赛代学为未来打下扎实基础的同时升华学术背景。

如今进入一所你梦寐以求的顶尖大学的竞争程度比以往任何时候都要激烈。对于国际TOP大学看重的不仅仅是一份漂亮的履历、优异的常规成绩或高GPA。招生官同时希望看到你的学术成就和丰富的课外活动。这些活动可以包括优秀的暑期项目、学术比赛、志愿者项目和在你感兴趣的领域的实习。USACO可以提升你申请任何一所大学的背景。那么今天就来全面剖析一下这项重量级赛事吧！

PART ONE --学术活动介绍--

01 USACO计算机学术活动的简介

美国计算机奥林匹克(The United States of America Computing Olympiad)是为美国中学生举办的计算机编程比赛。USACO在学年期间为学生提供四个越来越难的水平的比赛:铜、银、金和白金。USACO的参与者提交五种语言之一的程序:C、c++、Java、Pascal和Python。参与者通过在当前部门表现良好而晋级。为期一周的夏季训练营将从24名决赛选手中选出4名代表美国参加国际奥林匹克信息学学术活动(IOI)。

02 USACO计算机学术活动的历史

IOI国际信息学奥林匹克学术活动是最负盛名的国际高中计算机学术活动，由联合国教育、科学及文化组织(教科文组织)于1989年发起，是根据其他几个著名的国际高中奥林匹克学术活动的精神设计的。1992年，威斯康星大学帕克赛德分校(University Of Wisconsin Parkside)的数学教授唐·皮勒(Don Piele)博士听说了IOI，并成立了USACO，以便从美国带来一个团队来参加这次活动。参加1992年IOI的第一支美国队是由国际计算机问题解决大赛的顶尖个人组成的。

在最初的20年里，USACO由Don、主教练Rob Kolstad博士和一支敬业的志愿者团队领导，他们中的许多人都是过去IOI的前美国队成员。唐和罗布从管理USACO退休后，该组织目前由克莱姆森大学(Clemson University)计算机科学教授布莱恩·迪恩(Brian Dean)博士领导，并已经在USACO工作了20多年。

03 关于IOI国际信息学奥赛

The International Olympiad in Informatics (IOI)国际信息学奥林匹克学术活动是一项年度学术活动项目，也是面向中学生的国际科学奥林匹克学术活动之一。这是继国际数学奥林匹克之后的第二大科学奥林匹克学术活动，参与国家数量众多。1989年在保加利亚普拉维茨举行了第一次IOI。2021年的国际信息学奥赛则在新加坡举行。

比赛包括两天的计算机编程/编码和解决算法性质的问题。要处理涉及大量数据的问题，不仅需要程序员，还需要有创造性的程序员，他们可以想出程序员需要告诉计算机做什么。最难的部分不是编程，而是背后的数学。IOI的学生以个人为基础进行比赛，每个参赛国最多有4名学生参赛。

PART TWO  --学术活动深度解析--

04 USACO计算机学术活动的考试形式及计分方式

考试形式：

USACO有四个学术活动 Divisions级别，Bronze, Silver, Gold,和Platinum。所有参赛者都是从铜级赛区开始的。在每个比赛赛周之后，如果参赛者有足够高的分数就会被“promoted”到下一个级别--通常是600-800分(满分1000分)。你还可以在contest weekend中所有问题获得满分直接获得晋升。每一组都比前一组困难得多。这通常需要相当多的学习、训练，试图提升到一个新的水平需要耗费的时间，每一个等级长达一年或更长时间。USACO在2015年增加了Platinum级别。在此之前，每一个division的难度都比现在大，大约相当于今天的division“one step up”。例如，一般来说，“old Bronze”问题最接近“modern Silver”问题的难度。

计分方式：

提交的3-4个程序中的每一个都要对10个或更多的“test cases”进行测试——用已知的结果输入程序中的数据集。您可以为每个给出正确结果的测试用例获得学分。在一个contest weekend的比赛中，一个组别的所有问题总共有1000分。如果您的程序运行时间太长，占用太多内存，或者崩溃，那么您将在测试用例中失去分数，因此代码的效率是一个因素!这在Silver及以上级别的赛组中尤其突出。

05 USACO计算机学术活动的考试计时形式

比赛的计时形式是什么？

在赛周的任何时候，进入网站并点击按钮启动你的个人比赛计时器，时间为3-5个小时。出发前你会被告知确切的时间限制，通常是4小时。然后，选手将获得学术活动问题的访问权限。

可以休息或提前停止，但一旦你在那个周末点击了“开始”按钮，你的时间就会一直在滴答作响，直到到期--不允许暂停。如果你只是想检查一下题目，那么你可以随意花时间尝试它，想花多少时间就花多少时间。如果你的目标是做好，试着提前计划一整段时间，这样你就可以不分心地工作了。

比赛开始后会发生什么？

在启动计时器后，会被允许回答3-4个问题(通常是3个)，选手必须在个人时间窗口中解决。每一个都将提供一个背景问题，必须编写一个程序进行分析。在选手的时间窗口内的任何时候，都可以通过网站提交您的程序进行测试。选手可以在的时间窗口内自由切换或返回到任何问题，并继续提交解决方案，直到的时间截止或者选手觉得已经全部完美为止。可以选择在同一周末的任何时间使用新的计时器开始新部门的比赛。

06 如何选择USACO计算机学术活动的语言

USACO接受多种语言主要包括Java、C++和Python。Java和Python提交的时间限制是C++的两倍，因为它们的运行时间更长。然而，USACO官方描述并不推荐使用Python，因为它的运行速度往往比Java慢，而且在某些情况下，即使是问题的最佳解决方案也可能无法在时间限制内完成。发布在USACO网站上的解决方案供学生学习如何使用C++来解决包括大多数“training problems”在内的老问题，但随着时间的推移，Java已经变得越来越流行。所以在为USACO编程时，有什么特殊的Java注意事项是我应该知道的吗？您可以导入与Java 8一起安装的任何标准库，例如java.util.*和java.io.*。您的Java文件必须使用“default package”；源代码中不应该有“包”行。完成问题需要读写文本文件。

关于Division specific topics:

青铜级别除法问题通常可以使用数组(有时是二维数组，有时也可以使用类或ArrayList)来解决。白银组竞争者应该熟悉java.util包中的标准数据结构，如List/ArrayList、Set/HashSet/TreeSet、Map/HashMap/Treemap、Deque/ArrayDeque和PriorityQueue，以及比较器/可比接口。黄金组的竞争对手往往不得不对自己的数据结构进行编程。C++的运行速度确实比Java快，但USACO允许Java程序使用的时间是Java的两倍。使用Java应该不会出现无法在合理时间内完成的问题。建议使用一种适合学习的语言。对于学习美国AP课程的学生来说，这种语言通常是Java。其他比赛可能有不同的设置，可能需要使用其他语言。真正的知识在于算法，而不是语言。学习C++是一个很棒的推荐，如果您有时间和动力，鼓励您这样尝试。

Java程序的内存和时间限制是什么？

对于Java，每个输入测试用例都被给予“大约”4秒的时间，尽管这在不同的问题或测试用例中可能有所不同。通常，对于最坏的输入场景，粗略估计您的程序需要10亿次或更多的“operations”会花费太长时间，而1亿次或更少通常是可以的。介于两者之间的任何地方取决于细节。

每个输入案例都有“大约256MB”的内存可供运行。100万个整数的数组仅占用4MB内存(4字节*100万)。假设有一种合理的数据存储方法，时间限制几乎总是内存限制之前的限制因素。

PART THREE --学术活动备赛指南--

07 USACO计算机学术活动的报考指南

适合学生：

任何对编程语言有中级知识的学生都可以参加比赛。可能学生会觉得很难，但尝试挑战不会有什么坏处，可以按照自己的程度不断挑战提高！当参加比赛时，可能会学到比你以前知道的更多的东西，从而在下一轮比赛中取得更好的成绩。无论你的成绩如何，你仍然可以在你的履历或大学申请资料中体现而超越竞争对手。

何时参加比赛：

USACO 每年有 4 个周末举办主要比赛。在从周五到周一的这些周末期间，学生可以选择任何时间为该赛周启动他们的个人计时器。每个学生每个周末的时间通常是 4 小时，但有时是 3 或 5 小时。
每年赛季时间会有微调，但是大致差距不大，以21年赛季为例

如何参加比赛：

事先在www.usaco.org网站上注册一个免费账户。你不需要提前注册一个具体的比赛日期！一旦您拥有帐户，您就可以参与竞争，还可以通过您自己的门户访问所有培训课程和资源。在网站上创建帐户后，请登录您的帐户。如果是比赛周末，你会在首页看到一个开始按钮！

比赛报名费用：

USACO 是完全免费的，对任何人开放。只需注册一个帐户并进行一些练习，就可以开始了。

参赛形式：

必须以个人参赛者的身份参加比赛，并且在比赛期间不允许与其他人合作。但是，您可以与喜欢的任何人一起学习和准备！比赛规则详细说明了官方学术诚信准则。

学术活动奖项：

USACO是没有“prizes”的，但学生通过的难度学术活动会获得认可鉴定，这将使您的名字列在您晋级的周末的比赛结果中。这个可以在任何大学申请的履历上体现出来成为公认的成就。

08 USACO计算机学术活动备赛建议

学术活动参考资料：

需要初步认知这个学术活动，建议首先在USACO官网上回顾过去的比赛，该网站提供了一系列学术活动材料。这种比赛风格通常被称为“online judge”系统，你可以通过在线搜索找到许多例子。USACO官方还提供其他链接和资源的列表。

如何开始学术活动：

选择一种熟练的编程语言比如（推荐等级：C++>Java>Python），找寻大量拓展课题内容，持续挑战难题。初期的青铜及白银等级，你需要对这些知识点做好储备。

青铜级：Time Complexity,Basic Data Structures,Basic Complete Search,etc熟悉（Java/AP CS A class）语言项目就足够

白银级：Date Structures,Prefix Sums,Binary Search,Graphs,etcAP CS A 会涵盖50%的主题项目

以上基础准备完毕后就可以开始选择优秀的导师指导，助力层层冲关晋级了。