2023-2024年USACO首次月考題目出爐！銅組第一題真題及解析

2023-2024賽季USACO首場月賽已經圓滿結束，晉級賽的最新試題也已經公布。沒能當場晉級的同學們可以耐心等待一周，一周內USACO官方將會公布本次晉級賽成績。如果沒有晉級，12月可以當做一個練手+熟悉賽制的環節，1、2月的月賽持續發力，USACO可以重復挑戰。

今天給大家分享銅級試題和解析，參賽的同學來看看解題思路，沒參賽的同學來看看難度如何？

銅組第一題

INPUT FORMAT（pipe stdin）：

第一行包含N和M。

下一行包含N的初始高度奶牛，每頭都在[1-10^9]范圍內。

下一行包含M的高度糖果手杖，每根在[1-10^9]范圍內。

OUTPUT FORMAT (pipe stdout)：

每個N的最終高度奶牛在不同的線上。

請注意，此問題中涉及的大尺寸整數可能需要使用64位整數數據類型（例如，C/C++中的“long-long”）。

樣本輸入：

3 2

3 2 5

6 1

樣本輸出：

7

2

7

第一根甘蔗是6根單位高。

第一頭牛吃掉第一根甘蔗糖的部分，直到高度3之后，第一根甘蔗糖的剩余部分占據高度[3，6]。

第二頭牛不夠高，吃不下第一根甘蔗糖的任何剩余部分。

第三頭牛多吃兩個單位的第一根甘蔗糖。第一根甘蔗糖的剩余部分，占據高度[5,6]，不吃。

接下來，每頭奶牛的生長量與它的進食量相等，因此奶牛的高度變為[3+3，2+0，5+2]=[6,2,7]。

第二根甘蔗是1根

一個單位高，第一頭牛吃掉了所有的。

范圍

輸入2-10：N，M≤10^3

輸入11-14：無其他約束。

試題解析

這個題是個有意思的暴力問題

考慮一個子問題：

一個數初始是1，每一次操作是讓它乘2，要求這個數小于等于n，求最多能操作多少次

這個問題的答案比較顯然是log2n次

那考慮當前的問題，考慮第一頭牛，如果牛比甘蔗矮，那么它吃完甘蔗后高度乘22；如果牛比甘蔗高，此輪吃甘蔗結束。

所以這一題直接暴力模擬做到甘蔗被吃完復雜度就是對的。

時間復雜度：O(nlog2n)

知識點：暴力，時間復雜度分析

核心代碼如下：

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賬號，即可開始考試