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

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

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

✔ 銅

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

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

主要考點(diǎn)

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

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

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

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

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

✔ 銀

難度等級(jí)：需要基本的問(wèn)題解決能力和簡(jiǎn)單算法（例如：貪心算法，遞歸搜索和遞推等），還需了解基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)。從白銀級(jí)開(kāi)始，選手需要尋找更好的算法才能使程序在規(guī)定時(shí)間內(nèi)跑完。主要考察知識(shí)點(diǎn)和需要解決的問(wè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)是一種簡(jiǎn)單的圖遍歷技術(shù)。該算法從一個(gè)起始節(jié)點(diǎn)開(kāi)始，然后使用圖的邊繼續(xù)到從起始節(jié)點(diǎn)可達(dá)的所有其他節(jié)點(diǎn)。只要找到新的節(jié)點(diǎn)，深度優(yōu)先搜索總是沿著圖中的一條路徑進(jìn)行。在此之后，它返回到以前的節(jié)點(diǎn)，并開(kāi)始探索圖的其他部分。該算法跟蹤訪問(wèn)的節(jié)點(diǎn)，使每個(gè)節(jié)點(diǎn)只處理一次。

Greedy algorithm（貪心算法）：通常，當(dāng)使用貪心算法時(shí)，有一個(gè)價(jià)值函數(shù)來(lái)決定哪個(gè)選擇是最優(yōu)的。例如，我們經(jīng)常想要最大化或最小化某個(gè)量，所以我們?cè)谙乱徊饺】赡艿淖畲蠡蜃钚≈怠＿@里，我們將重點(diǎn)討論涉及排序步驟的問(wèn)題。

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

✔ 金

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

推薦學(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)是一種重要的算法。通過(guò)將整個(gè)任務(wù)分解成子問(wèn)題，DP避免了蠻力解的冗余計(jì)算。雖然掌握DP背后的一般想法并不太難，但該方法可以用于各種各樣的問(wèn)題，是USACO金牌學(xué)員必須掌握的內(nèi)容。

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

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

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

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

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

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

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

✔ 鉑金

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

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

翰林USACO課程體系流程圖