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

2023-2024賽季USACO首場(chǎng)月賽已經(jīng)圓滿結(jié)束，晉級(jí)賽的最新試題也已經(jīng)公布。沒能當(dāng)場(chǎng)晉級(jí)的同學(xué)們可以耐心等待一周，一周內(nèi)USACO官方將會(huì)公布本次晉級(jí)賽成績(jī)。如果沒有晉級(jí)，12月可以當(dāng)做一個(gè)練手+熟悉賽制的環(huán)節(jié)，1、2月的月賽持續(xù)發(fā)力，USACO可以重復(fù)挑戰(zhàn)。

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

銅組第一題

INPUT FORMAT（pipe stdin）：

第一行包含N和M。

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

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

OUTPUT FORMAT (pipe stdout)：

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

請(qǐng)注意，此問題中涉及的大尺寸整數(shù)可能需要使用64位整數(shù)數(shù)據(jù)類型（例如，C/C++中的“l(fā)ong-long”）。

樣本輸入：

3 2

3 2 5

6 1

樣本輸出：

7

2

7

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

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

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

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

接下來，每頭奶牛的生長(zhǎng)量與它的進(jìn)食量相等，因此奶牛的高度變?yōu)閇3+3，2+0，5+2]=[6,2,7]。

第二根甘蔗是1根

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

范圍

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

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

試題解析

這個(gè)題是個(gè)有意思的暴力問題

考慮一個(gè)子問題：

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

這個(gè)問題的答案比較顯然是log2n次

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

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

時(shí)間復(fù)雜度：O(nlog2n)

知識(shí)點(diǎn)：暴力，時(shí)間復(fù)雜度分析

核心代碼如下：

USACO歷年真題及參考書，掃碼領(lǐng)?。　竞擦痔峁﹫?bào)名指導(dǎo)服務(wù)】USACO歷年真題及參考書

2023-2024年USACO活動(dòng)時(shí)間

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

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

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

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

（中國學(xué)生只能參加到公開賽）

集訓(xùn)營(yíng)：2024年5月23日-6月1日

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

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

報(bào)名方式：參賽者可隨時(shí)在官網(wǎng)注冊(cè)賬號(hào)，注冊(cè)。報(bào)名，只需在活動(dòng)時(shí)間登陸完成答題即可。

官網(wǎng)地址：usaco.org

提交之后，官網(wǎng)會(huì)發(fā)送一份郵件到您郵箱，郵件中有賬號(hào)密碼

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

以上就是關(guān)于【2023-2024年USACO首次月考題目出爐！銅組第一題真題及解析】的解答，如需了解學(xué)校/賽事/課程動(dòng)態(tài)，可至翰林教育官網(wǎng)獲取更多信息。

往期文章閱讀推薦：

AI奧賽2026國家隊(duì)名單公布！?新賽季翰林助力直通IOAI全球總決賽！

2026五大奧賽中國隊(duì)斬獲四個(gè)世界第一，全員金牌收官！