美國信息學奧林匹克競賽USACO題型分析？

USACO（美國信息學奧林匹克競賽）初次舉(ju) 辦於(yu) 1992年，其官網是美國一個(ge) 著名在線題庫，更是美國中學生的官方競賽網站。

開設目的是為(wei) 每年夏季舉(ju) 辦的國際信息學奧林匹克競賽（IOI）選拔美國隊隊員，同時也是國內(nei) 學生申請美國大學提升背景的利器。

USACO題型分析 

首先說 Bronze。我們(men) 對過去三年的題目做一個(ge) 大致分析，題目有三種。

1. simulation

考生隻需要用 algorithm 和 coding 實現一個(ge) process就可以。

2. greedy algorithm

這類題目相對有一點tricky，需要孩子有更多的 observation 以及 analysis 方麵的訓練。

3. search

這也就是我們(men) 俗話說的暴力法，就是要能用一種枚舉(ju) 的思路來思考問題。

Bronze 級別，掌握了這三種基本題型的解題方法，在知識角度就沒有太大問題，剩下的主要在編程能力方麵，是否能夠把這三種題目的 algorithm 轉化為(wei) coding，並且能夠正確的通過 test case。

Bronze 總共三道題。很多時候 USACO 可能認為(wei) 把第一道題放在最簡單的一個(ge) 位置，但其實從(cong) 結果來反推並不是這樣，有時候最後一道題反而是最簡單的，所以推薦孩子上來不要看了第一題之後就立刻去寫(xie) ，而是先把三道題都看一遍。

我們(men) 應該努力把簡單和中等難度兩(liang) 道題目拿滿分。總共滿分是1000分，Bronze 分數線在 700-750，兩(liang) 道題差不多是666分左右，也就是說我們(men) 並不需要最難的第三道題目完全做出來，隻要能拿到一部分分數超出分數線，就能夠通過 Bronze 考試。

● Simulation題注意點

Simulation 這種題目推薦孩子掌握一個(ge) 比較穩固的編程基礎，另外讀題目一定要小心，有時候讀錯一道題的話，可能花了更多的時間在思考上麵，最後突然發現題目讀錯，那就損失比較大。

● Greedy Algorithm題注意點

Greedy Algorithm最重要的其實不是編程，編程部分通常來講都非常的容易，更加難的一點是什麽(me) ？是判斷這道題是否能夠用 greedy algorithm 來解決(jue) ，這反而是最難的。

這裏有很重要的一點：我們(men) 很多時候不需要去證明 Greedy 的性質，因為(wei) 證明有的時候會(hui) 更加複雜更加難，很多時候是需要做一個(ge) 假設，然後再找找看有沒有反例能夠推翻。如果沒有發現很明顯的反例，其實就可以試一試，因為(wei) Greedy Algorithm 在寫(xie) 程序的時候往往簡單，通過幾個(ge) 循環就能解決(jue) 掉。所以我們(men) 一直告訴孩子，在遇到 Greedy Algorithm 的時候該怎麽(me) 做。同時，Greedy 的算法因為(wei) 複雜度較低，所以通常它的數字非常大，就是題目所出的數據範圍會(hui) 非常的大。

● search題注意點

search 題目主要是 dfs 和 bfs，然後需要孩子對 complexity 有一定的了解。這種題型有一種偏幾何的題目，往往是跟矩形的邊界判定，或者是坐標係有一定關(guan) 係，但還沒有難到計算幾何的難度，所以這個(ge) 地方隻要把往年的一些幾何題過一過，也就夠了。

對於(yu) 比較難的問題，我們(men) 不是特別推薦在 Bronze 級別做專(zhuan) 門的準備，更需要的是什麽(me) ？更需要的是孩子往更高的知識點學習(xi) ，去學習(xi) Silver 知識點，或者更高級的知識點。那麽(me) 等到某一天回過頭來，其實就已經形成了一個(ge) 降維打擊。

來到 Silver級別，很明顯就多了很多 topics，比如除了剛才的 simulation 以及 search 之外，增加了graph 還有DP，DP就是 dynamic programming 動態規劃，還有 counting 和 data structure。其中 dynamic programming 這種題型是 21年新出現的，以前從(cong) 來沒有在 Silver 出現過，都是在 Gold 出現。本賽季 Silver 級別考試 Graph 出現的也越來越多，這樣 Silver 也會(hui) 比以前更加有挑戰性。

 USACO五大問題答疑 

Q：關(guan) 於(yu) USACO 考試，對於(yu) 最難的那道題，怎麽(me) 樣獲得部分得分？

A：這個(ge) 也要分級別來講。Bronze 和 Sliver 競賽中，通常來講更難級別的簡單題，就是下麵那個(ge) 級別的難題，所以說比較推薦的係統解決(jue) 方案，是學習(xi) 更高級的知識點，然後反向的做降維打擊，這是最好的一個(ge) 方式。

並且學習(xi) 更高級的知識點的話，也不是做無用功，做的努力也不會(hui) 浪費掉。

如果說是馬上就要考的那種情況，比較推薦在 Mock Test 裏嚐試以下做法：這道題哪怕我不會(hui) 做，但是我寫(xie) 一個(ge) 非常簡單的暴力的算法，哪怕我知道這個(ge) 效率不行，但是考試畢竟跟平時寫(xie) 作業(ye) 不一樣，我們(men) 不能追求一個(ge) 完整解決(jue) 方案，而是說能拿多少分就拿多少分。

那麽(me) 在這種情況下的話，多去做這種 mindset training，並且強製自己到了這個(ge) 時間點，就一定不要再去追求一個(ge) 完美解決(jue) 方案，一定要開始寫(xie) 一部分。這更多是一個(ge) 考試經驗這方麵的提升。所以總的來講，長期的解決(jue) 方案就是提升自己的水平，學更高級別的知識點；短期的話就是提升自己考試經驗這方麵的發揮。

Q：USACO 現在有 Bronze，Silver，Gold 和 Platinum 四個(ge) level，以後會(hui) 增加 level 嗎？

A：USACO 從(cong) 兩(liang) 年前到現在的變化：把原來的白金級別的東(dong) 西拿到了黃金級別，然後把黃金級別的東(dong) 西下放到白銀級別，然後同時白銀級別有少量內(nei) 容被放到了 Bronze，所以其實相當於(yu) 是每個(ge) 級別都變得更加有含金量。

最近這一兩(liang) 年這麽(me) 一個(ge) 變化，其實也是變相的在增加級別。會(hui) 不會(hui) 增加一個(ge) 什麽(me) 鑽石或者黑金？是有可能性。原來是沒有白金級別的，白金是在12、13年左右加上去的，此前隻有三個(ge) 級別。如果以後再要加一個(ge) 級別，可能相應的一些機製會(hui) 發生變化，但基本邏輯應該是不會(hui) 有太大的變化。

Q：USACO 到了什麽(me) level，會(hui) 對大學申請有直接幫助？

A：從(cong) 我們(men) 的經驗來看，孩子過了 Silver 進到 Gold Division，寫(xie) 到簡曆上就會(hui) 有一些幫助。現在即使不是頂級的大學，申請計算機方向的競爭(zheng) 也特別激烈，假如你有經驗，特別是 USACO 這樣一個(ge) 大家都公認的、並且含金量越來越高的一個(ge) 競賽成績的話，跟沒有的孩子相比，其他條件一致時，這是一個(ge) 絕對的優(you) 勢。

假如你能進入最高的 Platinum Level，對孩子進入一些藤校已經是會(hui) 有幫助了。有些孩子能夠進入到 USACO US Camp，這時候很多大藤學校都會(hui) 考慮你的。

Q：大學 CS 專(zhuan) 業(ye) 會(hui) 對應學到 USACO 哪個(ge) level？

A：首先 USACO 對學生的考察偏重於(yu) 算法和數據結構這兩(liang) 個(ge) 方麵。

在知識角度來講，大學會(hui) 學到的知識點包括了 Bronze 和 Silver 的知識點，然後是 Gold 的簡單知識點，也就是 dynamic programming 和graph，這兩(liang) 個(ge) 是會(hui) 學到的。但是大學裏學了知識點不太會(hui) 有太多練習(xi) 。

其實很多人到最後隻有要準備去麵試的時候，才會(hui) pick up LeetCode 或者其它算法實現的東(dong) 西。

所以簡單來講，經過 USACO Training 的學生，他們(men) 不光是算法和數據結構這方麵有非常強的理論功底，同時也能夠把他們(men) 給實現出來。在大學裏他們(men) 學習(xi) 算法和數據結構當然就非常簡單了，學習(xi) 其他課程也會(hui) 更加容易。同時他們(men) 可以在低年級就開始找機會(hui) 進入大學lab進行 research。