美国计算机奥林匹克竞赛-USACO

什么是USACO

USACO，全称为 United States of America Computing Olympiad（美国计算机奥林匹克竞赛）是针对美国中学生的计算机编程在线竞赛。

USACO根据难度分为四个赛段：青铜、银、金和白金，分别于每年12月、1月、2月和3月举办。
每次竞赛都会带来三到四个问题，参与者可以下载问题并在线提交解决方案。每个问题都需要编写一个程序来计算出一系列测试用例的正确答案。只有等于或高于入围成绩才能进入下一等级的比赛（满分或接近满分者直接进入下一轮，无需等待入围成绩的公布）。

USACO是一次“算法”竞赛，这意味着它需要提出创造性的、系统的方法来分析信息，而不仅仅是将程序的描述直接转换为代码。

比赛内容
参赛者可以在比赛窗口开放的任意时间段内参与，时长为连续3-4个小时。

USACO各个赛段的各个问题都允许以C、C ++、Java、Pascal和Python形式提交，选择其一即可。

问题本质上是算法问题，分数是根据程序在允许的时间和内存范围内正确计算的测试用例的数量计算的。（对于C，C ++和Pascal，每输入案例2秒；对于Java和Python，每输入案例4秒。每个赛段或问题可能有略微不同的限制）

需要灵巧的算法与数据结构才能正确地在时限内解决所有测试用例。

(1) 青铜

青铜级别的问题通常可以使用数组（有时是二维数组）或使用ArrayLists及其他基本编程常识即可解决。此赛段的主要任务是适应USACO问题的复杂性以及熟悉解决问题的格式，只要求会至少一种算法语言。
通过USACO青铜赛段的学生需要非常熟悉以下概念：
变数
循环
有条件的
功能/方法
列表/数组
套装
字典/哈希图
2020 USACO - bronze 题目

(2) 银
在解决问题和简单算法（算法、资料结构等）的基础上，还要确保我们的程序在每个测试用例的时间和内存范围内运行。代码效率是USACO的关键得分因素。因此，第二阶段的时间和内存复杂性分析更为重要。

通过USACO银级赛段的学生需要非常熟悉以下概念：

图和树

堆栈，队列和优先级队列

二进制搜索

深度优先搜索和宽度优先搜索

充水

滑动窗口

前缀和

2020 USACO - silver 题目

(3) 金，白金
第三、四阶段需要运用到抽象的方法（最短路径、动态规划等）自行对编程数据结构。该阶段中，解决问题的办法不止一个，要选择最优的方式。
这两个赛段是USACO中最难的，能够通过USACO黄金级认证的学生通常都具有计算机科学算法的高级本科水平。
通过USACO黄金级赛段的学生需要非常熟悉以下概念：
动态编程
最短路径算法
最小生成树
不相交集
字符串算法
几何算法
Dijkstra，Prim和Kruskal的算法
二叉索引树

USACO参赛价值

直白地讲，USACO的参赛经历与奖项对于申请美国大学有很大的竞争力，尤其是对于美本申请工程学科的学生来说。因为该考试涵盖了学生通常在计算机科学学士学位的前两年学习的高级材料。USACO四个赛段的难度依次递增，所展示的计算机能力足以吸引大学招生官。
而且USACO具有一定的威望，表现优异的选手有机会在国际信息学奥林匹克（IOI)中代表美国。

几点建议
(1) 重视审题

USACO的问题具有一定的复杂性。即使毫无头绪，也要仔细阅读问题，以确保理解问题所在。
建议反复朗读问题，并用自己的话解释，以检查对关键细节的理解。

(2) 仔细思考案例
每个问题总是提供一个样本输入案例及其相应的输出解决方案。在这些案例中，输入数据可能看起来与你最初想像的不一样。借助案例可以找到解决方法，最简单的方式是动手解答案例，了解其方法与模式。

(3) 规划算法与数据结构
揣摩原有的事例案例后，思考可以采取哪些步骤。概括，逐一记下解决问题的方法，并计划出如何储存所需要的数据。

例题讲解：

首先，理解题目意思：此问题为我们提供了两个不同矩形的左下角和右上角的坐标。我们想绘制最小的正方形，这些正方形覆盖了这些区域仍然包含两个矩形，我们要输出这个正方形必须的面积。

接着，理解案例：在正方形牧场的情况下，我们在网格上绘制了两个矩形，并且看到如果我们绘制包围两个内部矩形的外部矩形，则一侧的长度为4，而另一侧的长度为7。因此，由于最终字段具有要是一个正方形并覆盖整个区域，它必须具有7 * 7 = 49的面积。

可见，案例采用的方法是：确定周围矩形的边长。一旦我们有了边长，就很容易找到正方形的面积。再深入一层，我们可以看到边长之一只是给定的最小和最大x坐标之间的差，另一个是给定的最小和最大y坐标之间的差。

但是：方形牧场是相当有限的，因为输入数据始终包含8个数字，并且数字限制在0到10之间。思考：如果其中一些数字相同，会发生什么？如果输入量足够大，会发生什么情况？

参考案例后，解决案例中的局限性: 还要在最大可能的输入大小上近似估算这种方法的算法运行时间，以确保它在范围之内。

计划如何存储所需的数据，方形牧场的步骤可能如下所示：

a.以对列表的形式读取坐标

b.查找并存储最小和最大x和y坐标

c. 查找并存储外部矩形的宽度和高度

d.输出答案：宽度或高度较大者，平方

把每个步骤规划好后，便可以准确地编写程序。

常见的Q&A
Q1: 有规定哪些学生才有USACO参赛资格吗？

A1：USACO没有参赛门槛，任何具有编程语言中级知识的学生都可以参加比赛。

Q2: 我要到哪里参加比赛？

A2: 比赛全程在线进行。任何拥有互联网连接和编程软件的任何地方（通常是在家中）均可。登录网站 www.usaco.org 即可开始在任何地方进行。

Q3: 我要在什么时候参加比赛？

A3: 访问 www.usaco.org 可以查询的日期 ，通常是在周末进行。学生可以选择任何时间启动该比赛周末的个人计时器。

Q4: USACO的报名费是多少？
A4: USACO是完全免费的！只需注册一个帐户并进行一些练习，就可以开始了。

Q5: 可以以团队形式参赛吗？

A5:不可以。你必须以个人选手的身份参加比赛，并且不允许在比赛期间与其他人合作。但是，您可以和志同道合的人一起学习并做好准备！

Q6: 在新一轮比赛中失利，会“降级”吗？
A6: 不会。你通过了哪一个等级的比赛，就能获得该等级对应的荣誉。

Q7: 什么是“训练营”和“ IOI”？
A7: 参加白金赛的前16名学生将应邀参加了美国国家队的训练营。训练营中，将选拔出国际信息学奥林匹克（IOI）的美国队代表。

想要了解更多资讯欢迎来电咨询！