USACO 2021-2022賽季考點及考頻透析

距離2021-2022賽季的USACO 競賽隻餘(yu) 下3個(ge) 月的時間了，為(wei) 了方便參賽的學子能夠好好備賽，經過充分的教研，總結了最新的考點及考頻分析，下麵就和大家捋一捋其中的重點以及學習(xi) 方向。

競賽等級

✔ 銅

難度等級：銅級考試隻要基本編程常識（例如：基礎數組，多重循環，複合判斷，枚舉(ju) 算法等），會(hui) 至少一種編程語言。

主要考察知識點和需要解決(jue) 的問題相較而言比較少，推薦學習(xi) 時間：50小時編程練習(xi) 。 主要考點Simulation（模擬）：由於(yu) 沒有涉及到正式的算法，這個(ge) 問題的目的是評估一個(ge) 人的編程語言選擇和內(nei) 置數據結構知識的能力。當問題陳述說要找到某個(ge) 過程的最終結果，或者找到什麽(me) 時候發生的事情時，通常隻需簡單地模擬該過程就足夠了。將題目中出現的問題模擬成代碼進行求解。 Basic complete search（暴力完全搜索）：在許多問題中，檢查數據範圍中的所有可能情況，無論是所有元素，所有元素對，還是所有子集，或所有排列。這被稱為(wei) 完全搜索(或暴力搜索)，因為(wei) 它完全搜索整個(ge) 數據範圍。 Introduction to Graphs（圖論）：對於(yu) 銅牌來說，圖表隻是一種幫助思考數據結構的方法。下麵的所有圖論的問題至少屬於(yu) 以下兩(liang) 類問題之一：
1.圖的結構是特殊的(它是一個(ge) 樹，路徑或循環)，通過這個(ge) 線索求解。
2.可以通過遍曆搜索每個(ge) 的二維臨(lin) 接數組的節點求解
✔ 銀
難度等級：需要基本的問題解決(jue) 能力和簡單算法（例如：貪心算法，遞歸搜索和遞推等），還需了解基礎數據結構。從(cong) 白銀級開始，選手需要尋找更好的算法才能使程序在規定時間內(nei) 跑完。
主要考察知識點和需要解決(jue) 的問題增加，推薦學習(xi) 時間：75小時的知識學習(xi) +150小時左右的算法練習(xi) 。 主要考點Prefix sum（前綴和）：在固定的一維數組中，在時間複雜度為(wei) 常數的情況下計算搜索範圍總和。 DFS（深度優(you) 先搜索）：深度優(you) 先搜索(DFS)是一種簡單的圖遍曆技術。該算法從(cong) 一個(ge) 起始節點開始，然後使用圖的邊繼續到從(cong) 起始節點可達的所有其他節點。隻要找到新的節點，深度優(you) 先搜索總是沿著圖中的一條路徑進行。在此之後，它返回到以前的節點，並開始探索圖的其他部分。該算法跟蹤訪問的節點，使每個(ge) 節點隻處理一次。 Greedy algorithm（貪心算法）：通常，當使用貪心算法時，有一個(ge) 價(jia) 值函數來決(jue) 定哪個(ge) 選擇是最優(you) 的。例如，我們(men) 經常想要最大化或最小化某個(ge) 量，所以我們(men) 在下一步取可能的最大或最小值。這裏，我們(men) 將重點討論涉及排序步驟的問題。 Binary search（二分法）：當我們(men) 對答案進行二分算法優(you) 化搜索時，我們(men) 從(cong) 大小N的搜索空間開始進行每次除以2的方法進行切分。此時空間每次都會(hui) 減小為(wei) 前一個(ge) 搜索空間的一半，所以算法時間複雜度會(hui) 降低到 log N。這種方法比從(cong) 頭開始搜索到結尾的暴力搜索方法會(hui) 快很多。
✔ 金
難度等級：需要有一定的算法基礎，理解一些抽象的方法（例：堆，棧，樹，鏈表等高級數據結構，動態規劃等高級算法，算法時間和空間複雜度），並且對數據結構有比較深的了解。
難度升級，推薦學習(xi) 時間：80小時的知識學習(xi) +160小時左右的算法練習(xi) 。 主要考點DP (動態規劃)：動態規劃(Dynamic Programming, DP)是一種重要的算法。通過將整個(ge) 任務分解成子問題，DP避免了蠻力解的冗餘(yu) 計算。雖然掌握DP背後的一般想法並不太難，但該方法可以用於(yu) 各種各樣的問題，是USACO金牌學員必須掌握的內(nei) 容。 Disjoint set union （並查集）：Disjoint Set Union (DSU)數據結構允許您向一個(ge) 初始為(wei) 空的圖添加邊，並測試圖的兩(liang) 個(ge) 頂點是否連接由於(yu) 實現非常簡單，可以使用它代替DFS來計算通路連接。 Shortest Paths with Non-Negative Edge Weights（非負邊權最短路）：圖論中求解最短路徑的問題，幾乎所有的金牌題目最短路徑問題都涉及dijkstra algorithm。先學習(xi) bellman-ford和floyd-warshall會(hui) 對解題有很大的幫助，因為(wei) 他們(men) 更簡單。 Point Update Range Sum：主要知識點介紹了線段樹、二叉索引樹和C++順序統計樹。大多數金牌題目Point Update Range Sum問題需要在時間複雜度(log N)的情況下去對大小為(wei) N的數組上實現以下內(nei) 容:
1.在單個(ge) 位置(點)更新元素
2.查詢某個(ge) 連續子數組的和
線段樹和二叉索引樹都可以做到這一點。
除此之外，線段樹允許你在時間複雜度logN中對任何關(guan) 聯操作進行點更新和範圍查詢，而不僅(jin) 僅(jin) 是單純求和。 ✔ 鉑金
難度等級：需要有很高的編程基礎，對算法有深入的了解，特別是各類高級的數據結構，尤其需要注意算法的時間和空間複雜度。部分比賽問題最後的優(you) 化方案，可能不隻一個(ge) ，得出的答案也不隻一個(ge) 。鉑金組一般是針對有美國綠卡或者身份的同學，衝(chong) 擊美國信息學奧賽國家集訓營的考試。

【競賽報名/項目谘詢+微信：mollywei007】