考試預測丨USACO 2021-2022賽季考點及考頻透析

距離2021-2022賽季的USACO 學術活動只余下半個月的時間了，為了方便參賽的學子能夠好好備賽，翰林usaco教研團隊經過充分的教研，總結了最新的考點及考頻分析，下面就和大家捋一捋其中的重點以及學習方向。

學術活動等級

✔ 銅

難度等級：銅級考試只要基本編程常識（例如：基礎數組，多重循環，復合判斷，枚舉算法等），會至少一種編程語言。主要考察知識點和需要解決的問題相較而言比較少。

推薦學習時間：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中對任何關聯操作進行點更新和范圍查詢，而不僅僅是單純求和。

✔ 鉑金

難度等級：需要有很高的編程基礎，對算法有深入的了解，特別是各類高級的數據結構，尤其需要注意算法的時間和空間復雜度。部分比賽問題最后的優化方案，可能不只一個，得出的答案也不只一個。鉑金組一般是針對有美國綠卡或者身份的同學，沖擊美國信息學奧賽國家集訓營的考試。

緊跟USACO官方發布的2021新的大綱，翰林升級USACO課程，幫助同學們夯實基礎，攻克學術活動核心考點，順利晉級，沖金奪鉑金。掃碼免費領取最新年份學術活動真題，還有不定期的高能講座等你來參加！

翰林USACO課程體系流程圖