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

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

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青铜赛段的学生需要非常熟悉以下概念：

• 变数
• 循环
• 有条件的
• 功能/方法
• 列表/数组
• 套装
• 字典/哈希图

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

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

• 图和树
• 堆栈，队列和优先级队列
• 二进制搜索
• 深度优先搜索和宽度优先搜索
• 充水
• 滑动窗口
• 前缀和

第三、四阶段需要运用到抽象的方法（最短路径、动态规划等）自行对编程数据结构。该阶段中，解决问题的办法不止一个，要选择最优的方式。

这两个赛段是USACO中最难的，能够通过USACO黄金级认证的学生通常都具有计算机科学算法的高级本科水平。

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

• 动态编程
• 最短路径算法
• 最小生成树
• 不相交集
• 字符串算法
• ·几何算法
• Dijkstra，Prim和Kruskal的算法
• 二叉索引树