美国USACO计算机竞赛深度剖析

申请全球TOP大学无论是美国藤校还是英国G5都需要通过层层选拔，在众多学生的申请资料中，如何才能脱颖而出？每当到赛季来临之时学霸们都在夜以继日奋力刷题磨炼自己，憧憬的名校就在眼前，如果能在竞赛中拿到好的奖项名次，无疑是如虎添翼。

对计算机、编程、数学建模等理科专业方向感兴趣的同学注意咯，今天我们请剑桥大学 计算机科学专业导师深度剖析 美国USACO计算机竞赛 情况～ 

PART ONE

--竞赛介绍--

01 USACO计算机竞赛的简介

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

02 USACO计算机竞赛含金量

USACO初次举办于1992年，其官网是美国一个著名在线题库，更是美国中学生的官方竞赛网站，开设目的是为每年夏季举办的国际信息学奥林匹克竞赛（IOI）选拔美国队队员。

USACO适合国内高一高二在读学生，高三学生也可以参加12月的第一场比赛，如果实力突出，可以在12月中，RD常规申请前获得白金级奖项，不失为申请前最后一波强势的背景提升机会。

03 关于LOL国际信息学奥赛

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

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

03 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程序使用的时间是C++的两倍。使用Java应该不会出现无法在合理时间内完成的问题。建议使用一种适合学习的语言。对于学习美国AP课程的学生来说，这种语言通常是Java。其他比赛可能有不同的设置，可能需要使用其他语言。真正的知识在于算法，而不是语言。学习C++是一个很棒的推荐，如果您有时间和动力，鼓励您这样尝试。

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

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

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

PART TWO

--竞赛备战指南--

01 USACO计算机竞赛的报考指南美国

适合学生

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

何时参加比赛

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

每年赛季时间会有微调，但是大致差距不大，以21年赛季为例

如何参加比赛

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

比赛报名费用

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

参赛形式

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

竞赛奖项

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

02 USACO计算机竞赛真题展示 

USACO是一个“algorithmic”算法竞赛，这意味着它需要想出创造性的、系统的方法来分析信息，而不仅仅是直接将程序的描述翻译成代码。例如，“find the position of the largest number in a list”是一个非常简单的算法问题，但“write down the commands to draw a circle and then a square”就不是了。您可以查看过去的竞赛问题以获取一些示例。

以下是一些USACO真题展示

03 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,etc

AP CS A 会涵盖50%的主题项目

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