USACO 2021-2022赛季考点及考频透析

✔ 铜

难度等级：铜级考试只要基本编程常识（例如：基础数组，多重循环，复合判断，枚举算法等），会至少一种编程语言。

主要考察知识点和需要解决的问题相较而言比较少，推荐学习时间：50小时编程练习。

Basic complete search（暴力完全搜索）：在许多问题中，检查数据范围中的所有可能情况，无论是所有元素，所有元素对，还是所有子集，或所有排列。这被称为完全搜索(或暴力搜索)，因为它完全搜索整个数据范围。

Introduction to Graphs（图论）：对于铜牌来说，图表只是一种帮助思考数据结构的方法。下面的所有图论的问题至少属于以下两类问题之一：

1.图的结构是特殊的(它是一个树，路径或循环)，通过这个线索求解。

2.可以通过遍历搜索每个的二维临接数组的节点求解

✔ 银

难度等级：需要基本的问题解决能力和简单算法（例如：贪心算法，递归搜索和递推等），还需了解基础数据结构。从白银级开始，选手需要寻找更好的算法才能使程序在规定时间内跑完。

主要考察知识点和需要解决的问题增加，推荐学习时间：75小时的知识学习+150小时左右的算法练习。

DFS（深度优先搜索）：深度优先搜索(DFS)是一种简单的图遍历技术。该算法从一个起始节点开始，然后使用图的边继续到从起始节点可达的所有其他节点。只要找到新的节点，深度优先搜索总是沿着图中的一条路径进行。在此之后，它返回到以前的节点，并开始探索图的其他部分。该算法跟踪访问的节点，使每个节点只处理一次。

Greedy algorithm（贪心算法）：通常，当使用贪心算法时，有一个价值函数来决定哪个选择是最优的。例如，我们经常想要最大化或最小化某个量，所以我们在下一步取可能的最大或最小值。这里，我们将重点讨论涉及排序步骤的问题。

Binary search（二分法）：当我们对答案进行二分算法优化搜索时，我们从大小N的搜索空间开始进行每次除以2的方法进行切分。此时空间每次都会减小为前一个搜索空间的一半，所以算法时间复杂度会降低到 log N。这种方法比从头开始搜索到结尾的暴力搜索方法会快很多。

✔ 金

难度等级：需要有一定的算法基础，理解一些抽象的方法（例：堆，栈，树，链表等高级数据结构，动态规划等高级算法，算法时间和空间复杂度），并且对数据结构有比较深的了解。

难度升级，推荐学习时间：80小时的知识学习+160小时左右的算法练习。

Disjoint set union （并查集）：Disjoint Set Union (DSU)数据结构允许您向一个初始为空的图添加边，并测试图的两个顶点是否连接由于实现非常简单，可以使用它代替DFS来计算通路连接。

Shortest Paths with Non-Negative Edge Weights（非负边权最短路）：图论中求解最短路径的问题，几乎所有的金牌题目最短路径问题都涉及dijkstra algorithm。先学习bellman-ford和floyd-warshall会对解题有很大的帮助，因为他们更简单。

Point Update Range Sum：主要知识点介绍了线段树、二叉索引树和C++顺序统计树。大多数金牌题目Point Update Range Sum问题需要在时间复杂度(log N)的情况下去对大小为N的数组上实现以下内容:

1.在单个位置(点)更新元素

2.查询某个连续子数组的和

线段树和二叉索引树都可以做到这一点。

除此之外，线段树允许你在时间复杂度logN中对任何关联操作进行点更新和范围查询，而不仅仅是单纯求和。

✔ 铂金

难度等级：需要有很高的编程基础，对算法有深入的了解，特别是各类高级的数据结构，尤其需要注意算法的时间和空间复杂度。部分比赛问题最后的优化方案，可能不只一个，得出的答案也不只一个。铂金组一般是针对有美国绿卡或者身份的同学，冲击美国信息学奥赛国家集训营的考试。