距离2021-2022赛季的USACO 竞赛只余下3个月的时间了，为了方便参赛的学子能够好好备赛，经过充分的教研，总结了最新的考点及考频分析，下面就和大家捋一捋其中的重点以及学习方向。
竞赛等级
✔ 铜
难度等级：铜级考试只要基本编程常识（例如：基础数组，多重循环，复合判断，枚举算法等），会至少一种编程语言。
主要考察知识点和需要解决的问题相较而言比较少，推荐学习时间：50小时编程练习。 
主要考点Simulation（模拟）：由于没有涉及到正式的算法，这个问题的目的是评估一个人的编程语言选择和内置数据结构知识的能力。当问题陈述说要找到某个过程的最终结果，或者找到什么时候发生的事情时，通常只需简单地模拟该过程就足够了。将题目中出现的问题模拟成代码进行求解。
Basic complete search（暴力完全搜索）：在许多问题中，检查数据范围中的所有可能情况，无论是所有元素，所有元素对，还是所有子集，或所有排列。这被称为完全搜索(或暴力搜索)，因为它完全搜索整个数据范围。 
Introduction to Graphs（图论）：对于铜牌来说，图表只是一种帮助思考数据结构的方法。下面的所有图论的问题至少属于以下两类问题之一：
1.图的结构是特殊的(它是一个树，路径或循环)，通过这个线索求解。
2.可以通过遍历搜索每个的二维临接数组的节点求解 
✔ 银
难度等级：需要基本的问题解决能力和简单算法（例如：贪心算法，递归搜索和递推等），还需了解基础数据结构。从白银级开始，选手需要寻找更好的算法才能使程序在规定时间内跑完。
主要考察知识点和需要解决的问题增加，推荐学习时间：75小时的知识学习+150小时左右的算法练习。 
主要考点Prefix sum（前缀和）：在固定的一维数组中，在时间复杂度为常数的情况下计算搜索范围总和。
DFS（深度优先搜索）：深度优先搜索(DFS)是一种简单的图遍历技术。该算法从一个起始节点开始，然后使用图的边继续到从起始节点可达的所有其他节点。只要找到新的节点，深度优先搜索总是沿着图中的一条路径进行。在此之后，它返回到以前的节点，并开始探索图的其他部分。该算法跟踪访问的节点，使每个节点只处理一次。 
Greedy algorithm（贪心算法）：通常，当使用贪心算法时，有一个价值函数来决定哪个选择是最优的。例如，我们经常想要最大化或最小化某个量，所以我们在下一步取可能的最大或最小值。这里，我们将重点讨论涉及排序步骤的问题。 Binary search（二分法）：当我们对答案进行二分算法优化搜索时，我们从大小N的搜索空间开始进行每次除以2的方法进行切分。此时空间每次都会减小为前一个搜索空间的一半，所以算法时间复杂度会降低到 log N。这种方法比从头开始搜索到结尾的暴力搜索方法会快很多。 
✔ 金
难度等级：需要有一定的算法基础，理解一些抽象的方法（例：堆，栈，树，链表等高级数据结构，动态规划等高级算法，算法时间和空间复杂度），并且对数据结构有比较深的了解。
难度升级，推荐学习时间：80小时的知识学习+160小时左右的算法练习。 
主要考点DP (动态规划)：动态规划(Dynamic Programming, DP)是一种重要的算法。通过将整个任务分解成子问题，DP避免了蛮力解的冗余计算。虽然掌握DP背后的一般想法并不太难，但该方法可以用于各种各样的问题，是USACO金牌学员必须掌握的内容。
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中对任何关联操作进行点更新和范围查询，而不仅仅是单纯求和。 
✔ 铂金
难度等级：需要有很高的编程基础，对算法有深入的了解，特别是各类高级的数据结构，尤其需要注意算法的时间和空间复杂度。部分比赛问题最后的优化方案，可能不只一个，得出的答案也不只一个。铂金组一般是针对有美国绿卡或者身份的同学，冲击美国信息学奥赛国家集训营的考试。
【竞赛报名/项目咨询请加微信：mollywei007】
