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，農(nóng)夫約翰的奶牛數(shù)量。下一行包含一個(gè)N只有1的字符位字符串s和0

s其中1表示受感染的奶牛和0表示經(jīng)過一些夜晚后未受感染的奶牛。

輸出格式（pipe stdout）：

輸出一個(gè)整數(shù)：可能開始生病的奶牛的最小數(shù)量。

樣本輸入：

5

11111

樣本輸出：

1

假設(shè)中間的奶牛是唯一一頭開始被感染的奶牛。然后奶牛會(huì)按照以下順序被感染：

0晚：00100（第三頭奶牛最初被感染）

1晚：->01110（第二頭和第四頭奶牛現(xiàn)在被感染）

2晚：->11111（第一頭和第五頭奶牛現(xiàn)在被感染）

3晚：->11111（所有奶牛都已被感染，因此沒有其他奶牛被感染）

->。。。

在兩個(gè)或多個(gè)晚上之后，奶牛的最終狀態(tài)看起來就像輸入。還有許多其他初始狀態(tài)和夜晚數(shù)可能會(huì)產(chǎn)生輸入狀態(tài)，例如：

0晚：10001

1晚：->11011

2晚：->11111

或者：

0晚：01001

1晚：->11111

或者：

0晚：01000

1晚：->11100

2晚：->11110

3晚：->11

111

所有這些初始狀態(tài)都包含至少一頭受感染的奶牛。

樣本輸入：

6

011101

樣本輸出：

4

唯一可能導(dǎo)致這種最終狀態(tài)的初始狀態(tài)和夜晚數(shù)是，如果沒有夜晚過去，輸入的四頭受感染的奶牛中的每一頭都開始生病。

評(píng)分：

輸入3-7：N≤1000

輸入8-12：無其他約束。

試題解析

首先我們可以根據(jù)輸入計(jì)算出1的擴(kuò)散時(shí)間最長(zhǎng)是多少（時(shí)間越長(zhǎng)需要的初始點(diǎn)就越少）

注意邊界和中間的計(jì)算方式不同，中間擴(kuò)散的結(jié)果是1,3,5,...,2*n-1，而邊界是1,2,3,...,n$因?yàn)檫吔缈梢苑旁谧罱锹溟_始）

計(jì)算出最長(zhǎng)擴(kuò)散時(shí)間max_time后我們就可以對(duì)每一段連續(xù)為1計(jì)算初始最少需要放幾個(gè)1 : len = 2*max_time+1 (len代表連續(xù)1個(gè)數(shù))

最終將答案相加即可

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

知識(shí)點(diǎn)：貪心，邊界條件判斷

核心代碼如下：

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)營：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)獲取更多信息。

往期文章閱讀推薦：

【組隊(duì)招募】經(jīng)濟(jì)/數(shù)模競(jìng)賽CNEC/IEO/SIC/HiMCM…組隊(duì)報(bào)名！

NOAI人工智能奧賽 2026-2027 活動(dòng)章程出爐：新規(guī)則必看！