USACO美國信息學奧賽
2024-25賽季3月公開賽已落幕
同學們都“打怪升級”成功了嘛？
為幫助同學們高效復盤，翰林衛老師照例為大家帶來3月公開賽的考情分析，快來和小林一起了解詳情吧！
USACO 3月公開賽分析——銅級篇
01、近年分數線
25年3月的分數線是700，這個賽季銅級全部是700分。只需要2題全對，第3題通過10%的測試數據就可以。
02、競賽難度分析
這次銅級的難度，從官方給定的700分數線推斷，應該定位在一個平均偏上的位置（750是一個平均難度）。值得關注的是，這次open賽的難度并沒有比前三場大，晉級可能比前面的場次還容易點（考慮到多了1個小時的比賽時間）。
03、考點分析
第一題【Ad Hoc】
這道題需要應用到一些【排列組合】的知識，計算會輸的方案數會更容易。每次只需要計算出同時能贏s1和s2的個數，那么只要方案里面沒有這些，就肯定會輸。相比于這個賽季出現過的【Ad Hoc】，難度并沒有加大，還是比較容易想到的。
第二題【Greedy】
需要大家去觀察，找到貪心思路的一道題。多嘗試點例子，就可以發現，從大到小第一個出現頻率大于等于1的數，就可以作為中間那個元素。后面只要出現個數大于等于2的，都可以算2個進去。和這個賽季之前的【Greedy】相比，思維難度更小，而且代碼實現也很容易。
第三題
【Complete Search + Prefix Sum + Binary Search】
三道題中最難的一題。如果前兩題全對，這道題直接最暴力的做法，答對前2個test case，就可以晉級了。
想要拿滿分，需要用【Prefix Sum】快速找到第一個不是該字母的位置，用【Binary Search】找到最后一個該字母的位置。中間的位置，需要結合數學知識，推理出來就是最接近兩者中間的位置。
總體而言，銅級的考點分布比較均衡，也都是我們平時強調的重點。而且此次open賽的難度相比于去年明顯降低，和常規賽差別不大。同時給的時間多了1個小時，所以相對更容易晉級。不過想要拿滿分，需要有一些銀級的知識儲備，同時善于結合數學分析。
USACO3月公開賽分析——銀級篇
01、近年分數線
25年3月的分數線是750，這個賽季前面都是700，這場達到750分，和去年的常規賽一致。所以大家為了確保自己晉級，最好還是要達到750分以上。
02、競賽難度分析
這次銀級的難度，從官方給定的750分數線推斷，也是定位在一個平均的位置。這次的銀級，同樣也是需要大家具備一定的分析能力，沒有太過套路的題目。和前面的場次一樣，邏輯和算法的考察都有，想要晉級兩方面能力缺一不可。
03、考點分析
第一題【Greedy】
是一個帶貪心的構造題，突破口在于發現popcount比總和更難湊出來，所以構造出滿足popcount總和是k，數值總和最小的解。這樣的好處，就是后面可以在不影響popcount的基礎下，去湊總和。
具體又要分情況討論，比如總和已經大于m、總和差是偶數、相差大于3、相差1等，每一種都需要自己去結合具體實例分析，對大家的邏輯要求比較高。這道題關鍵在于選對方面，如果大方向錯了，基本上不太可能對。
第二題【Graph + Greedy】
最終可以轉換成一個Graph的模型，和23年1月份的【Find and Replace】有點類似。可能形成多個component，每個是一個純鏈、帶環（只有一個元素）的鏈、環（只有一個元素）。
后面就是貪心的思路，優先從鏈那頭出發讓相鄰去匹配，最后環中剩余的自己相互匹配。是一道需要建模的題，同時自己也要去思考會出現的情況，找到正確答案。
第三題【Tree + Binary Search】
構造出一個以1為root的tree。最核心的部分是計算，每個node在每個勇氣值下，能回到1的最小技巧值。這個可以通過dfs中維護一些信息完成，也就是從1到該node的路徑中最大的11個數值。得到這個信息以后，再按照勇氣值歸類，后面查詢用二分就可以。
這道題的代碼細節有點多，也要注意超空間的問題，相比于前兩道題，這道題的邏輯要求沒有那么高，比較常規。
總體而言，銀級的有偏思維也有偏算法的題，特別是前兩道都需要Greedy，會比較難想。想要達到750分，基本上每道題都得有一個比較正確的方向，難度會比之前的場次大一點。
USACO 3月公開賽分析——金級篇
01近年分數線
25年3月的分數線是850，相比于整個賽季之前的700分，有了非常大的提升，甚至也是近4個賽季中的最高分。這就提醒大家，有時候800分也不太保險，850才是一個比較穩妥的分數。
02、競賽難度分析
這次金級的難度，從官方給定的850分數線推斷，也是定位在一個平均往下的位置。比之前的場次分數線大幅提升，但其實這場的難度也不算低。可能大部分同學完成得都不錯，導致了分數線的提升。
03、考點分析
第一題【Math】
一道很偏數學的題目。可以考慮單個字符串內部的方案數，如果是m的話，答案就是m^L。單個字符串內，又可以通過從后往前遍歷的方式，遇到O進行累加，遇到M從還剩余的O中選擇K個，看有多少種方案，這是一個組合問題。
代碼實現層面，要用到【Modular Arithmetic】、【Combinatorics】等內容。可以先作為一道數學題去思考，對大家的數學邏輯思維要求比較高。
第二題【Square Root Decomposition】
這個賽季第二次考到了鉑金的這個考點。關鍵需要發現，兩個牛要作為leader，必須它們的票數總和大于等于最高票數。直接暴力枚舉會O(N^2)，可以從票數種類出發枚舉，這樣就可以縮減至sqrt(N)級別。大家可以考慮學一些鉑金的重點算法，在金級的比賽中，也是會有幫助的。
第三題【Ad Hoc + Binary Search + Segment Tree】
首先也是策略的考察，前者會把最大的A個加1，后者會把最大的B個減1，其實受影響的只有中間A-B個。直接模擬會超時，可以先全部考慮加1操作，用Binary Search去二分找到所有大于等于mid的減到mid或者減去D 次，是否可行。
還有一種方式是使用【Segment Tree】，考慮怎么去合并區間，這個對代碼的要求更高。
總體而言，金級的考點不算是很常規，邏輯題有點多。除了第一題比較常規以外，剩下的兩道題都是有思維難度的。分數線是850分，對大家的要求很高，特別是又出現了鉑金的考點。
24到25賽季，已經全部結束。除了open賽，每個級別的分數線，都是700分（open賽金級分數比較反常）。這次open賽沒有之前那么難，特別是銅級，甚至比之前還簡單。所以大家下個賽季也可以多多關注open，也是一次比較好的機會。
距離下個賽季還有8個月的時間，大家可以利用這段時間，多多學習算法知識，練習題目做積累。USACO是一個需要花費時間的比賽，循序漸進，充實提高自己的能力，我們下個賽季見。
🔼 以上內容由翰林計算機衛老師提供
翰林計算機衛老師
清華大學軟件工程碩士
南京大學軟件工程學士
◾ 畢業后在一家上市視頻監控公司，從事軟件開發工作，負責核心流媒體中臺項目，擔當公司最新技術的探索和轉化職責。
◾ 教學方面，對待學生耐心負責，講解知識深入淺出，在有限知識內最大化地實現教學目標。
◾執教戰績（部分）：
-2024-2025 NZOI賽季，輔導1名學生入選新西蘭國家隊，參加國際信息學奧賽IOI；
-2024-2025 USACO賽季，輔導2名學生晉級鉑金，15名學生晉級金，16名學生晉級銀；
-2023-2024 USACO賽季，輔導3名學生晉級鉑金，9名學生晉級金，14名學生晉級銀；
-2022-2023 USACO賽季，輔導5名學生晉級金，11名學生晉級銀。
了解USACO信息學奧賽詳情
可掃碼添加顧問咨詢
我要領取！
USACO 2024-25賽季圓滿收官在翰林導師與學員的攜手拼搏下
我們交出了一份亮眼的成績單！
12月月賽：1鉑金 7金 17銀
1月月賽：9金 9銀
2月月賽：3鉑金 7金 10銀
3月公開賽：1鉑金 2金 2銀
共5位鉑金級別、25位金級和38位銀級選手！
USACO 2023-2024賽季完美收官！
2024-25賽季USACO戰績
USACO 12月月賽
晉級鉑金：1人來自北京第十一中學
晉級金級：7人來自深國交，美高，German Swiss International School，杭州外國語學校等
晉級銀級：17人來自上海星河灣，包玉剛，香港哈羅，杭州惠立，Mecleans College，WLSA上海，成外，加高，英國私立高中等學校
USACO 1月月賽
晉級金級：9人來自美亞學校，成外，星河灣，杭州外國語學校，包玉剛杭州惠立，Mecleans College等
晉級銀級：9人來自清瀾山，美高，成都美視學校，成都高中，星河灣，貝賽思等
USACO 2月月賽
晉級鉑金：3人來自美高、深國交等
晉級金級：7人來自人大附、WLSA、美高等
晉級銀級：10人來自上海星河灣、北京21世紀、貝賽思、美高等學校
USACO 3月公開賽
晉級鉑金：1人來自英國私立高中
晉級金級：2人來自上海星河灣，馬尼拉國際學校
晉級銀級：2人來自多哈高中，IGB
正如翰林衛老師所說的，計劃參加USACO信息學奧賽新賽季的同學可以趁這段時間系統學習算法知識，通過刷題夯實基礎。
為了幫助大家高效備考，翰林推出了USACO各級別班課。由哥大和清華學姐帶隊！為參賽者提供專業的指導和實戰經驗分享。
了解USACO課程更多內容
可掃碼1v1咨詢顧問老師哦~
我要咨詢！
本期福利
2024-25賽季USACO
3月公開賽真題
添加顧問老師免費領取
