考試預(yù)測丨USACO 2021-2022賽季考點(diǎn)及考頻透析

距離2021-2022賽季的USACO 學(xué)術(shù)活動(dòng)只余下半個(gè)月的時(shí)間了，為了方便參賽的學(xué)子能夠好好備賽，翰林usaco教研團(tuán)隊(duì)經(jīng)過充分的教研，總結(jié)了最新的考點(diǎn)及考頻分析，下面就和大家捋一捋其中的重點(diǎn)以及學(xué)習(xí)方向。

學(xué)術(shù)活動(dòng)等級

✔ 銅

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

推薦學(xué)習(xí)時(shí)間：50小時(shí)編程練習(xí)。

主要考點(diǎn)

Simulation（模擬）：由于沒有涉及到正式的算法，這個(gè)問題的目的是評估一個(gè)人的編程語言選擇和內(nèi)置數(shù)據(jù)結(jié)構(gòu)知識(shí)的能力。當(dāng)問題陳述說要找到某個(gè)過程的最終結(jié)果，或者找到什么時(shí)候發(fā)生的事情時(shí)，通常只需簡單地模擬該過程就足夠了。將題目中出現(xiàn)的問題模擬成代碼進(jìn)行求解。

Basic complete search（暴力完全搜索）：在許多問題中，檢查數(shù)據(jù)范圍中的所有可能情況，無論是所有元素，所有元素對，還是所有子集，或所有排列。這被稱為完全搜索(或暴力搜索)，因?yàn)樗耆阉髡麄€(gè)數(shù)據(jù)范圍。

Introduction to Graphs（圖論）：對于銅牌來說，圖表只是一種幫助思考數(shù)據(jù)結(jié)構(gòu)的方法。下面的所有圖論的問題至少屬于以下兩類問題之一：

1.圖的結(jié)構(gòu)是特殊的(它是一個(gè)樹，路徑或循環(huán))，通過這個(gè)線索求解。

2.可以通過遍歷搜索每個(gè)的二維臨接數(shù)組的節(jié)點(diǎn)求解

✔ 銀

難度等級：需要基本的問題解決能力和簡單算法（例如：貪心算法，遞歸搜索和遞推等），還需了解基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)。從白銀級開始，選手需要尋找更好的算法才能使程序在規(guī)定時(shí)間內(nèi)跑完。主要考察知識(shí)點(diǎn)和需要解決的問題增加。

推薦學(xué)習(xí)時(shí)間：75小時(shí)的知識(shí)學(xué)習(xí)+150小時(shí)左右的算法練習(xí)。

主要考點(diǎn)

Prefix sum（前綴和）：在固定的一維數(shù)組中，在時(shí)間復(fù)雜度為常數(shù)的情況下計(jì)算搜索范圍總和。

DFS（深度優(yōu)先搜索）：深度優(yōu)先搜索(DFS)是一種簡單的圖遍歷技術(shù)。該算法從一個(gè)起始節(jié)點(diǎn)開始，然后使用圖的邊繼續(xù)到從起始節(jié)點(diǎn)可達(dá)的所有其他節(jié)點(diǎn)。只要找到新的節(jié)點(diǎn)，深度優(yōu)先搜索總是沿著圖中的一條路徑進(jìn)行。在此之后，它返回到以前的節(jié)點(diǎn)，并開始探索圖的其他部分。該算法跟蹤訪問的節(jié)點(diǎn)，使每個(gè)節(jié)點(diǎn)只處理一次。

Greedy algorithm（貪心算法）：通常，當(dāng)使用貪心算法時(shí)，有一個(gè)價(jià)值函數(shù)來決定哪個(gè)選擇是最優(yōu)的。例如，我們經(jīng)常想要最大化或最小化某個(gè)量，所以我們在下一步取可能的最大或最小值。這里，我們將重點(diǎn)討論涉及排序步驟的問題。

Binary search（二分法）：當(dāng)我們對答案進(jìn)行二分算法優(yōu)化搜索時(shí)，我們從大小N的搜索空間開始進(jìn)行每次除以2的方法進(jìn)行切分。此時(shí)空間每次都會(huì)減小為前一個(gè)搜索空間的一半，所以算法時(shí)間復(fù)雜度會(huì)降低到 log N。這種方法比從頭開始搜索到結(jié)尾的暴力搜索方法會(huì)快很多。

✔ 金

難度等級：需要有一定的算法基礎(chǔ)，理解一些抽象的方法（例：堆，棧，樹，鏈表等高級數(shù)據(jù)結(jié)構(gòu)，動(dòng)態(tài)規(guī)劃等高級算法，算法時(shí)間和空間復(fù)雜度），并且對數(shù)據(jù)結(jié)構(gòu)有比較深的了解，難度升級。

推薦學(xué)習(xí)時(shí)間：80小時(shí)的知識(shí)學(xué)習(xí)+160小時(shí)左右的算法練習(xí)。

主要考點(diǎn)

DP (動(dòng)態(tài)規(guī)劃)：動(dòng)態(tài)規(guī)劃(Dynamic Programming, DP)是一種重要的算法。通過將整個(gè)任務(wù)分解成子問題，DP避免了蠻力解的冗余計(jì)算。雖然掌握DP背后的一般想法并不太難，但該方法可以用于各種各樣的問題，是USACO金牌學(xué)員必須掌握的內(nèi)容。

Disjoint set union （并查集）：Disjoint Set Union (DSU)數(shù)據(jù)結(jié)構(gòu)允許您向一個(gè)初始為空的圖添加邊，并測試圖的兩個(gè)頂點(diǎn)是否連接由于實(shí)現(xiàn)非常簡單，可以使用它代替DFS來計(jì)算通路連接。

Shortest Paths with Non-Negative Edge Weights（非負(fù)邊權(quán)最短路）：圖論中求解最短路徑的問題，幾乎所有的金牌題目最短路徑問題都涉及dijkstra algorithm。先學(xué)習(xí)bellman-ford和floyd-warshall會(huì)對解題有很大的幫助，因?yàn)樗麄兏唵巍?/p>

Point Update Range Sum：主要知識(shí)點(diǎn)介紹了線段樹、二叉索引樹和C++順序統(tǒng)計(jì)樹。大多數(shù)金牌題目Point Update Range Sum問題需要在時(shí)間復(fù)雜度(log N)的情況下去對大小為N的數(shù)組上實(shí)現(xiàn)以下內(nèi)容:

1.在單個(gè)位置(點(diǎn))更新元素

2.查詢某個(gè)連續(xù)子數(shù)組的和

線段樹和二叉索引樹都可以做到這一點(diǎn)。

除此之外，線段樹允許你在時(shí)間復(fù)雜度logN中對任何關(guān)聯(lián)操作進(jìn)行點(diǎn)更新和范圍查詢，而不僅僅是單純求和。

✔ 鉑金

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

緊跟USACO官方發(fā)布的2021新的大綱，翰林升級USACO課程，幫助同學(xué)們夯實(shí)基礎(chǔ)，攻克學(xué)術(shù)活動(dòng)核心考點(diǎn)，順利晉級，沖金奪鉑金。掃碼免費(fèi)領(lǐng)取最新年份學(xué)術(shù)活動(dòng)真題，還有不定期的高能講座等你來參加！

翰林USACO課程體系流程圖