USACO美國(guó)信息學(xué)奧賽

2024-25賽季3月公開(kāi)賽已落幕

同學(xué)們都“打怪升級(jí)”成功了嘛？

為幫助同學(xué)們高效復(fù)盤，翰林衛(wèi)老師照例為大家?guī)?lái)3月公開(kāi)賽的考情分析，快來(lái)和小林一起了解詳情吧！

USACO 3月公開(kāi)賽分析——銅級(jí)篇

01、近年分?jǐn)?shù)線

25年3月的分?jǐn)?shù)線是700，這個(gè)賽季銅級(jí)全部是700分。只需要2題全對(duì)，第3題通過(guò)10%的測(cè)試數(shù)據(jù)就可以。

02、競(jìng)賽難度分析

這次銅級(jí)的難度，從官方給定的700分?jǐn)?shù)線推斷，應(yīng)該定位在一個(gè)平均偏上的位置（750是一個(gè)平均難度）。值得關(guān)注的是，這次open賽的難度并沒(méi)有比前三場(chǎng)大，晉級(jí)可能比前面的場(chǎng)次還容易點(diǎn)（考慮到多了1個(gè)小時(shí)的比賽時(shí)間）。

03、考點(diǎn)分析

第一題【Ad Hoc】

這道題需要應(yīng)用到一些【排列組合】的知識(shí)，計(jì)算會(huì)輸?shù)姆桨笖?shù)會(huì)更容易。每次只需要計(jì)算出同時(shí)能贏s1和s2的個(gè)數(shù)，那么只要方案里面沒(méi)有這些，就肯定會(huì)輸。相比于這個(gè)賽季出現(xiàn)過(guò)的【Ad Hoc】，難度并沒(méi)有加大，還是比較容易想到的。

第二題【Greedy】

需要大家去觀察，找到貪心思路的一道題。多嘗試點(diǎn)例子，就可以發(fā)現(xiàn)，從大到小第一個(gè)出現(xiàn)頻率大于等于1的數(shù)，就可以作為中間那個(gè)元素。后面只要出現(xiàn)個(gè)數(shù)大于等于2的，都可以算2個(gè)進(jìn)去。和這個(gè)賽季之前的【Greedy】相比，思維難度更小，而且代碼實(shí)現(xiàn)也很容易。

第三題

【Complete Search + Prefix Sum + Binary Search】

三道題中最難的一題。如果前兩題全對(duì)，這道題直接最暴力的做法，答對(duì)前2個(gè)test case，就可以晉級(jí)了。

想要拿滿分，需要用【Prefix Sum】快速找到第一個(gè)不是該字母的位置，用【Binary Search】找到最后一個(gè)該字母的位置。中間的位置，需要結(jié)合數(shù)學(xué)知識(shí)，推理出來(lái)就是最接近兩者中間的位置。

總體而言，銅級(jí)的考點(diǎn)分布比較均衡，也都是我們平時(shí)強(qiáng)調(diào)的重點(diǎn)。而且此次open賽的難度相比于去年明顯降低，和常規(guī)賽差別不大。同時(shí)給的時(shí)間多了1個(gè)小時(shí)，所以相對(duì)更容易晉級(jí)。不過(guò)想要拿滿分，需要有一些銀級(jí)的知識(shí)儲(chǔ)備，同時(shí)善于結(jié)合數(shù)學(xué)分析。

USACO3月公開(kāi)賽分析——銀級(jí)篇

01、近年分?jǐn)?shù)線

25年3月的分?jǐn)?shù)線是750，這個(gè)賽季前面都是700，這場(chǎng)達(dá)到750分，和去年的常規(guī)賽一致。所以大家為了確保自己晉級(jí)，最好還是要達(dá)到750分以上。

02、競(jìng)賽難度分析

這次銀級(jí)的難度，從官方給定的750分?jǐn)?shù)線推斷，也是定位在一個(gè)平均的位置。這次的銀級(jí)，同樣也是需要大家具備一定的分析能力，沒(méi)有太過(guò)套路的題目。和前面的場(chǎng)次一樣，邏輯和算法的考察都有，想要晉級(jí)兩方面能力缺一不可。

03、考點(diǎn)分析

第一題【Greedy】

是一個(gè)帶貪心的構(gòu)造題，突破口在于發(fā)現(xiàn)popcount比總和更難湊出來(lái)，所以構(gòu)造出滿足popcount總和是k，數(shù)值總和最小的解。這樣的好處，就是后面可以在不影響popcount的基礎(chǔ)下，去湊總和。

具體又要分情況討論，比如總和已經(jīng)大于m、總和差是偶數(shù)、相差大于3、相差1等，每一種都需要自己去結(jié)合具體實(shí)例分析，對(duì)大家的邏輯要求比較高。這道題關(guān)鍵在于選對(duì)方面，如果大方向錯(cuò)了，基本上不太可能對(duì)。

第二題【Graph + Greedy】

最終可以轉(zhuǎn)換成一個(gè)Graph的模型，和23年1月份的【Find and Replace】有點(diǎn)類似。可能形成多個(gè)component，每個(gè)是一個(gè)純鏈、帶環(huán)（只有一個(gè)元素）的鏈、環(huán)（只有一個(gè)元素）。

后面就是貪心的思路，優(yōu)先從鏈那頭出發(fā)讓相鄰去匹配，最后環(huán)中剩余的自己相互匹配。是一道需要建模的題，同時(shí)自己也要去思考會(huì)出現(xiàn)的情況，找到正確答案。

第三題【Tree + Binary Search】

構(gòu)造出一個(gè)以1為root的tree。最核心的部分是計(jì)算，每個(gè)node在每個(gè)勇氣值下，能回到1的最小技巧值。這個(gè)可以通過(guò)dfs中維護(hù)一些信息完成，也就是從1到該node的路徑中最大的11個(gè)數(shù)值。得到這個(gè)信息以后，再按照勇氣值歸類，后面查詢用二分就可以。

這道題的代碼細(xì)節(jié)有點(diǎn)多，也要注意超空間的問(wèn)題，相比于前兩道題，這道題的邏輯要求沒(méi)有那么高，比較常規(guī)。

總體而言，銀級(jí)的有偏思維也有偏算法的題，特別是前兩道都需要Greedy，會(huì)比較難想。想要達(dá)到750分，基本上每道題都得有一個(gè)比較正確的方向，難度會(huì)比之前的場(chǎng)次大一點(diǎn)。

USACO 3月公開(kāi)賽分析——金級(jí)篇

01近年分?jǐn)?shù)線

25年3月的分?jǐn)?shù)線是850，相比于整個(gè)賽季之前的700分，有了非常大的提升，甚至也是近4個(gè)賽季中的最高分。這就提醒大家，有時(shí)候800分也不太保險(xiǎn)，850才是一個(gè)比較穩(wěn)妥的分?jǐn)?shù)。

02、競(jìng)賽難度分析

這次金級(jí)的難度，從官方給定的850分?jǐn)?shù)線推斷，也是定位在一個(gè)平均往下的位置。比之前的場(chǎng)次分?jǐn)?shù)線大幅提升，但其實(shí)這場(chǎng)的難度也不算低。可能大部分同學(xué)完成得都不錯(cuò)，導(dǎo)致了分?jǐn)?shù)線的提升。

03、考點(diǎn)分析

第一題【Math】

一道很偏數(shù)學(xué)的題目。可以考慮單個(gè)字符串內(nèi)部的方案數(shù)，如果是m的話，答案就是m^L。單個(gè)字符串內(nèi)，又可以通過(guò)從后往前遍歷的方式，遇到O進(jìn)行累加，遇到M從還剩余的O中選擇K個(gè)，看有多少種方案，這是一個(gè)組合問(wèn)題。

代碼實(shí)現(xiàn)層面，要用到【Modular Arithmetic】、【Combinatorics】等內(nèi)容。可以先作為一道數(shù)學(xué)題去思考，對(duì)大家的數(shù)學(xué)邏輯思維要求比較高。

第二題【Square Root Decomposition】

這個(gè)賽季第二次考到了鉑金的這個(gè)考點(diǎn)。關(guān)鍵需要發(fā)現(xiàn)，兩個(gè)牛要作為leader，必須它們的票數(shù)總和大于等于最高票數(shù)。直接暴力枚舉會(huì)O(N^2)，可以從票數(shù)種類出發(fā)枚舉，這樣就可以縮減至sqrt(N)級(jí)別。大家可以考慮學(xué)一些鉑金的重點(diǎn)算法，在金級(jí)的比賽中，也是會(huì)有幫助的。

第三題【Ad Hoc + Binary Search + Segment Tree】

首先也是策略的考察，前者會(huì)把最大的A個(gè)加1，后者會(huì)把最大的B個(gè)減1，其實(shí)受影響的只有中間A-B個(gè)。直接模擬會(huì)超時(shí)，可以先全部考慮加1操作，用Binary Search去二分找到所有大于等于mid的減到mid或者減去D 次，是否可行。

還有一種方式是使用【Segment Tree】，考慮怎么去合并區(qū)間，這個(gè)對(duì)代碼的要求更高。

總體而言，金級(jí)的考點(diǎn)不算是很常規(guī)，邏輯題有點(diǎn)多。除了第一題比較常規(guī)以外，剩下的兩道題都是有思維難度的。分?jǐn)?shù)線是850分，對(duì)大家的要求很高，特別是又出現(xiàn)了鉑金的考點(diǎn)。

24到25賽季，已經(jīng)全部結(jié)束。除了open賽，每個(gè)級(jí)別的分?jǐn)?shù)線，都是700分（open賽金級(jí)分?jǐn)?shù)比較反常）。這次open賽沒(méi)有之前那么難，特別是銅級(jí)，甚至比之前還簡(jiǎn)單。所以大家下個(gè)賽季也可以多多關(guān)注open，也是一次比較好的機(jī)會(huì)。

距離下個(gè)賽季還有8個(gè)月的時(shí)間，大家可以利用這段時(shí)間，多多學(xué)習(xí)算法知識(shí)，練習(xí)題目做積累。USACO是一個(gè)需要花費(fèi)時(shí)間的比賽，循序漸進(jìn)，充實(shí)提高自己的能力，我們下個(gè)賽季見(jiàn)。

🔼 以上內(nèi)容由翰林計(jì)算機(jī)衛(wèi)老師提供

翰林計(jì)算機(jī)衛(wèi)老師

清華大學(xué)軟件工程碩士

南京大學(xué)軟件工程學(xué)士

◾ 畢業(yè)后在一家上市視頻監(jiān)控公司，從事軟件開(kāi)發(fā)工作，負(fù)責(zé)核心流媒體中臺(tái)項(xiàng)目，擔(dān)當(dāng)公司最新技術(shù)的探索和轉(zhuǎn)化職責(zé)。

◾ 教學(xué)方面，對(duì)待學(xué)生耐心負(fù)責(zé)，講解知識(shí)深入淺出，在有限知識(shí)內(nèi)最大化地實(shí)現(xiàn)教學(xué)目標(biāo)。

◾執(zhí)教戰(zhàn)績(jī)（部分）：

-2024-2025 NZOI賽季，輔導(dǎo)1名學(xué)生入選新西蘭國(guó)家隊(duì)，參加國(guó)際信息學(xué)奧賽IOI；

-2024-2025 USACO賽季，輔導(dǎo)2名學(xué)生晉級(jí)鉑金，15名學(xué)生晉級(jí)金，16名學(xué)生晉級(jí)銀；

-2023-2024 USACO賽季，輔導(dǎo)3名學(xué)生晉級(jí)鉑金，9名學(xué)生晉級(jí)金，14名學(xué)生晉級(jí)銀；

-2022-2023 USACO賽季，輔導(dǎo)5名學(xué)生晉級(jí)金，11名學(xué)生晉級(jí)銀。

了解USACO信息學(xué)奧賽詳情

可掃碼添加顧問(wèn)咨詢

我要領(lǐng)取！

USACO 2024-25賽季圓滿收官在翰林導(dǎo)師與學(xué)員的攜手拼搏下

我們交出了一份亮眼的成績(jī)單！

12月月賽：1鉑金 7金 17銀

1月月賽：9金 9銀

2月月賽：3鉑金 7金 10銀

3月公開(kāi)賽：1鉑金 2金 2銀

共5位鉑金級(jí)別、25位金級(jí)和38位銀級(jí)選手！

USACO 2023-2024賽季完美收官！

2024-25賽季USACO戰(zhàn)績(jī)

USACO 12月月賽

晉級(jí)鉑金：1人來(lái)自北京第十一中學(xué)

晉級(jí)金級(jí)：7人來(lái)自深國(guó)交，美高，German Swiss International School，杭州外國(guó)語(yǔ)學(xué)校等

晉級(jí)銀級(jí)：17人來(lái)自上海星河灣，包玉剛，香港哈羅，杭州惠立，Mecleans College，WLSA上海，成外，加高，英國(guó)私立高中等學(xué)校

USACO 1月月賽

晉級(jí)金級(jí)：9人來(lái)自美亞學(xué)校，成外，星河灣，杭州外國(guó)語(yǔ)學(xué)校，包玉剛杭州惠立，Mecleans College等

晉級(jí)銀級(jí)：9人來(lái)自清瀾山，美高，成都美視學(xué)校，成都高中，星河灣，貝賽思等

USACO 2月月賽

晉級(jí)鉑金：3人來(lái)自美高、深國(guó)交等

晉級(jí)金級(jí)：7人來(lái)自人大附、WLSA、美高等

晉級(jí)銀級(jí)：10人來(lái)自上海星河灣、北京21世紀(jì)、貝賽思、美高等學(xué)校

USACO 3月公開(kāi)賽

晉級(jí)鉑金：1人來(lái)自英國(guó)私立高中

晉級(jí)金級(jí)：2人來(lái)自上海星河灣，馬尼拉國(guó)際學(xué)校

晉級(jí)銀級(jí)：2人來(lái)自多哈高中，IGB

正如翰林衛(wèi)老師所說(shuō)的，計(jì)劃參加USACO信息學(xué)奧賽新賽季的同學(xué)可以趁這段時(shí)間系統(tǒng)學(xué)習(xí)算法知識(shí)，通過(guò)刷題夯實(shí)基礎(chǔ)。

為了幫助大家高效備考，翰林推出了USACO各級(jí)別班課。由哥大和清華學(xué)姐帶隊(duì)！為參賽者提供專業(yè)的指導(dǎo)和實(shí)戰(zhàn)經(jīng)驗(yàn)分享。

了解USACO課程更多內(nèi)容

可掃碼1v1咨詢顧問(wèn)老師哦~

我要咨詢！

本期福利

2024-25賽季USACO

3月公開(kāi)賽真題

添加顧問(wèn)老師免費(fèi)領(lǐng)取

往期文章閱讀推薦：
AMC10競(jìng)賽難不難？如何備考AMC10競(jìng)賽？
AMC12競(jìng)賽難不難？如何更好備考AMC12？