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

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

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

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

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

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

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

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

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

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

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

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

 

 

USACO入門課程 

 

USACO強(qiáng)化課程 

 

USACO金牌班 

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

 

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

銅牌沖刺課大綱

銀牌沖刺課大綱

 

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

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

 

石軒銘老師

 

 

莫納什大學(xué)計(jì)算機(jī)專業(yè)

教齡 7 年，15000+ 小時(shí)課時(shí)時(shí)長(zhǎng)

 

• 課堂氣氛活躍，教學(xué)質(zhì)量高，深受學(xué)生歡迎

• 教授科目：AP/AL/IB 系列計(jì)算機(jī)、計(jì)算機(jī)系列競(jìng)賽金牌導(dǎo)師

• 中英文流利授課，教授過(guò)中、英、美、加、馬來(lái)、印度、澳、新（加坡）、新（西蘭）、日、韓、荷等多國(guó)學(xué)生學(xué)習(xí)計(jì)算機(jī)算法

 

 

犀?的USACO競(jìng)賽培訓(xùn)課優(yōu)勢(shì)

1. 犀?教育的USACO課程是根據(jù)USACOguide指導(dǎo)?站上的考點(diǎn)需求，由專業(yè)?師設(shè)計(jì)并開發(fā)的。

2. 重點(diǎn)突出了算法考點(diǎn)知識(shí)，全?挖掘?qū)W?的潛?，有助于培養(yǎng)學(xué)?的編程能?和思維能?，更好的幫助學(xué)?通過(guò)?賽。

3. 課程設(shè)置更加有優(yōu)勢(shì)，模仿了美國(guó)?學(xué)的Lecture + Lab的先進(jìn)課程體系模式，即主課+答疑課的課堂形式。

4. 教師均來(lái)?海內(nèi)外名校，并且每位教師有多年授課經(jīng)驗(yàn)，帶出的學(xué)?都取得了優(yōu)異的成績(jī)。

 

USACO競(jìng)賽最新喜報(bào)

 

USACO學(xué)員/家長(zhǎng)反饋（部分）

 

了解USACO課程詳情
在線咨詢課程 點(diǎn)擊客服 了解更多