USACO競賽銅/銀/金/鉑金不同級別需要掌握的算法有哪些？附USACO培訓(xùn)課程

發(fā)布時(shí)間：2023-05-31 09:34:58 編輯：犀牛牛來源：犀牛國際教育

USACO計(jì)算機(jī)編程競賽主要考察學(xué)生算法和運(yùn)用兩大方面的技能，旨在鍛煉學(xué)生用計(jì)算機(jī)編程解決問題的能力。在USACO競賽中達(dá)到金級、白金級的選手對于申請美國大學(xué)本科（尤其是計(jì)算機(jī)專業(yè)）的學(xué)生有很大助力，歷屆頂尖選手備受牛校鐘愛。那么，USACO不同級別的比賽需要掌握哪些算法？我們來看看。

圖為四位美國信息學(xué)奧賽國家隊(duì)選手，將代表美國隊(duì)參加去年國際信息學(xué)奧林匹克競賽（圖片來自：USACO.org）

USACO銅級

銅級主要考察兩種東西，一種是simulation，第二種就是 brute force，然后另外加上一些observation。Bronze 這個(gè)級別要求學(xué)生掌握基本的 brute force 一些算法，比如說深度優(yōu)先搜索和廣度優(yōu)先搜索，再加上對于代碼有基本的調(diào)試能力，此外，還有孩子比較容易忽視的閱讀理解能力。USACO 題目有的時(shí)候是很長的，看上去整整一頁，像在講一個(gè)故事，在這個(gè)故事講完之后，孩子去做的事情，其實(shí)是把這個(gè)故事抽象成一個(gè)帶有條件的解決問題

Bronze（銅級）：適合于剛學(xué)會編程的學(xué)生，考察的算法主要有：窮舉算法（Complete Search）、模擬算法（Simulation）、貪心算法（Greedy algorithm）、全排列（Permutation）、雜類題目（Ad-hoc）、遞歸（Recursion）；

USACO銀級

銀級通常有4個(gè)比較重要的 topics，第一個(gè)是叫 two pointer，第二個(gè)就是 sweep line，第三個(gè)是binary search on answer。第四個(gè)是 prefix sum + graph + simple dp。

去年我們發(fā)現(xiàn)，以前只會在黃金級里面出現(xiàn)的問題，開始出現(xiàn)在銀級考試中，會有一些 graph題目以及簡單的 DP， DP 就是動態(tài)程序設(shè)計(jì)。銀級這個(gè)級別，會發(fā)現(xiàn)算法已經(jīng)不再是簡單的代碼了，它需要學(xué)生能夠?qū)?0~100行的代碼，甚至可能超過100行，也對于孩子的代碼能力和調(diào)試代碼的能力提出了更高的要求，同時(shí)對孩子的建模能力也提出了進(jìn)一步的要求。

Silver（銀級）：面向開始學(xué)習(xí)基本問題解決算法，考察的算法主要有：排序（Sorting）、二分查找（Binary Search）、遞歸搜索（Recursion）、圖的遍歷（DFS&BFS）、FLoodfill算法、前綴和（Prefix Sum）、掃描線算法（Line Sweep）；

USACO金級

黃金級別考的是幾個(gè)比較大的 Topic，一個(gè)是 graph theory，第二是 math，第三個(gè)是DP，第四個(gè) range query，第五還有 misc，string 以及偏 data structure 的內(nèi)容比如 tree。但通常來講是結(jié)合前 4 個(gè) topic 在考，這4個(gè)topic都是非常廣闊的領(lǐng)域，比如說 graph，雖然是一個(gè)單詞，但包含著至少十幾個(gè)小的 sub topic。

DP 僅基本的類型就有將近10個(gè)，每個(gè)類型下面，根據(jù)不同的問題結(jié)構(gòu)，它展可以展開的問題就更多了。這些 Topics 有什么特點(diǎn)呢？就是變化特別多，基本上沒有一種方法可以窮舉完，或者說光靠漫無目的的刷題是很難的。此外，這兩年的 Gold 競賽變得特別難。難到什么程度？最近兩年每一場考試，Gold 通過人數(shù)大概是 20 多人，個(gè)別考試像 US Open 可能會稍微多一點(diǎn)，那么像12月，一月二月這些 Gold 考試，一場只有20多個(gè)人通過，分到美國50個(gè)州的話，相當(dāng)于是2個(gè)州分一個(gè)人。

USACO鉑金

Platinum 相對來講是跟gold的 topic 基本吻合的，基本上是 Gold 有什么東西 Platinum 就有什么東西，但 Platinum 每一個(gè) topic 里面有更深層次的要求。比如 DP 的話，Gold 級別把 DP 公式推出來，一般來講也就做出題目了，很少需要做很高級的一些優(yōu)化。在 Platinum 不做優(yōu)化程序就會超時(shí)，這就要求就需要孩子有更進(jìn)一步的能力。

在這里也為大家整理了《usaco算法書》，這本是是備考USACO競賽一站式指南，為USACO比賽的銅牌到銀組、金組，再到鉑金，提供了一系列有價(jià)值的參考資料。0基礎(chǔ)開始學(xué)習(xí)USACO必備書籍。

教材領(lǐng)取在線咨詢客服回復(fù)USACO教材

普通編程課程，更多是學(xué)一些計(jì)算機(jī)通識問題，比較寬泛。自學(xué)是一個(gè)很艱難和緩慢的過程，計(jì)算機(jī)學(xué)習(xí)中涉及到大量的軟硬件問題，同時(shí)也會有很多的發(fā)展方向，如果是沒有經(jīng)驗(yàn)的人，會將大量時(shí)間浪費(fèi)在這些問題上，又或者在某些細(xì)節(jié)上迷失，偏移整個(gè)學(xué)習(xí)路線，從而事倍功半，中途而廢。USACO競賽備考不建議自學(xué)。

如何入門USACO競賽斬金奪銀！犀牛教育根據(jù)孩子不同基礎(chǔ)開設(shè)不同版型，可供每一位計(jì)算機(jī)愛好者選擇！

USACO入門課程

USACO強(qiáng)化課程

USACO金牌班

(犀牛 USACO培訓(xùn)有：精品小班、一對一等多種班型可供選擇，線下+線上同步授課，上海、北京、南京、蘇州、無錫、深圳、重慶、杭州等地都設(shè)有校區(qū)，詳細(xì)課程內(nèi)容可在線咨詢客服了解)

USACO培訓(xùn)課程大綱

銅牌沖刺課大綱

銀牌沖刺課大綱

犀牛USACO培訓(xùn)師資

犀?的USACO?師們都是身經(jīng)百戰(zhàn)，國內(nèi)外?流名校畢業(yè)?師來對學(xué)?進(jìn)行精準(zhǔn)輔導(dǎo)。致?培養(yǎng)下?代計(jì)算機(jī)科學(xué)家。?多數(shù)?師是海歸背景，適合美?或者 ?陸外籍國際學(xué)校的同學(xué)，這些同學(xué)平時(shí)學(xué)習(xí)都是全英?環(huán)境，我們的?師可以? 全英?授課，幫助同學(xué)?障礙地理解USACO的課程內(nèi)容。