2024年USACO1月月考題目出爐！黃金組別考情分析

USACO計算機編程競賽的1月月賽已經完美結束啦，這次沒有晉級到自己心儀級別的同學也不要著急，接下來可以等待2月的月賽！

1月月賽黃金組考了哪些內容？今天整理了1月USACO競賽黃金組別考情分析，希望對同學們接下來的USACO競賽備考有所幫助。

USACO 2024年1月黃金組別考情分析

第1題

考察算法：二分，觀察性質

首先假設當前在x軸朝向上行走，什么時候會轉向到y軸?

我們發現當且僅當當前道路距離下一條道路是奇數距離的時候會轉向

于是我們可以考慮去二分轉向的次數，計算出在當前轉向次數下運動的距離，判斷它是否小于等于題目給出的運動距離

代碼實現較為復雜，需要注意細節

時間復雜度：$O((n+q)*log)

第2題

考察算法：動態規劃

和銀組第一題類似

定義$i$這個位置是前綴最大值當且僅當$a[i]>a[j]$ (for all $1le j

我們會發現對于某個$(a[i],h[i])$相當于要求$[a[i]+1,h[i]-1]$這一段不能是前綴最大值，$h[i]$這個位置必須是前綴最大值

最終我們將相同情況的序列合并在一起，那么就是有最多$3*Q$段的序列(每一段內部要么要求一定是前綴最大值/一定不是前綴最大值/沒有要求)，求最終合法的方案數

定義$dp[i][j]$代表當前考慮到前$i$段數，選的數的最大值是$j$的方案數

假設當前這一段序列長度為$len$

當一定是前綴最大值時：

$dp[i][j]=sum_{k=1}^{j-1} dp[i-1][k]$

當一定不是前綴最大值時：

$dp[i][j]=dp[i-1][j]*j^{len}$

當沒有要求時：

$dp[i][j]=dp[i-1][j]j^{len} + sum_{k=1}^{j-1} dp[i-1][k](j^{len} -(j-1)^{len})$

時間復雜度：$O(qclog)$

第3題

考察算法：二分

注意到分給Bessie自己的數越多答案相應的會越大，但是會越容易滿足題目限制

所以我們考慮去二分分給Bessie的個數$mid$

那么它們分別被加入序列的時間就是$mid, mid + (mid-1) ,... , mid+...+1$

顯然我們比較希望盡量靠后的數能被加入到Bessie的序列中，所以對于每一個加入序列的時間我們可以貪心的去找到第一個大于當前時間且沒有被插入到序列中的數，將它插入到序列中

這個過程可以用類似于雙指針的思想來優化

最終$min(數字最大值,mid*(mid+1)/2)$就是我們的答案

時間復雜度：$O(n*log)$

USACO歷年真題及參考書，掃碼領取！【翰林提供報名指導服務】USACO歷年真題及參考書

2023-2024年USACO活動時間

第一次月賽：2023年12月15日-18日

第二次月賽：2024年1月26日-29日

第三次月賽：2024年2月16日-19日

美國公開賽：2024年3月15日-18日

（中國學生只能參加到公開賽）

集訓營：2024年5月23日-6月1日

EGOI：2024年7月21日-27日（荷蘭）

IOI：2024年9月1日-8日（埃及）

報名方式：參賽者可隨時在官網注冊賬號，注冊。報名，只需在活動時間登陸完成答題即可。

官網地址：usaco.org

提交之后，官網會發送一份郵件到您郵箱，郵件中有賬號密碼

利用已知的賬號于密碼，登錄USACO賬號，即可開始考試