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

發(fā)布時間：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 這個級別要求學(xué)生掌握基本的 brute force 一些算法，比如說深度優(yōu)先搜索和廣度優(yōu)先搜索，再加上對于代碼有基本的調(diào)試能力，此外，還有孩子比較容易忽視的閱讀理解能力。USACO 題目有的時候是很長的，看上去整整一頁，像在講一個故事，在這個故事講完之后，孩子去做的事情，其實(shí)是把這個故事抽象成一個帶有條件的解決問題

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

USACO銀級

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

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

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

USACO金級

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

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

USACO鉑金

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

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

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

普通編程課程，更多是學(xué)一些計(jì)算機(jī)通識問題，比較寬泛。自學(xué)是一個很艱難和緩慢的過程，計(jì)算機(jī)學(xué)習(xí)中涉及到大量的軟硬件問題，同時也會有很多的發(fā)展方向，如果是沒有經(jīng)驗(yàn)的人，會將大量時間浪費(fèi)在這些問題上，又或者在某些細(xì)節(jié)上迷失，偏移整個學(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é)平時學(xué)習(xí)都是全英?環(huán)境，我們的?師可以? 全英?授課，幫助同學(xué)?障礙地理解USACO的課程內(nèi)容。