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

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

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

銅組第二題

INPUT FORMAT（pipe stdin）：

第一行包含N，農夫約翰的奶牛數量。下一行包含一個N只有1的字符位字符串s和0

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

輸出格式（pipe stdout）：

輸出一個整數：可能開始生病的奶牛的最小數量。

樣本輸入：

5

11111

樣本輸出：

1

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

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

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

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

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

->。。。

在兩個或多個晚上之后，奶牛的最終狀態看起來就像輸入。還有許多其他初始狀態和夜晚數可能會產生輸入狀態，例如：

0晚：10001

1晚：->11011

2晚：->11111

或者：

0晚：01001

1晚：->11111

或者：

0晚：01000

1晚：->11100

2晚：->11110

3晚：->11

111

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

樣本輸入：

6

011101

樣本輸出：

4

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

評分：

輸入3-7：N≤1000

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

試題解析

首先我們可以根據輸入計算出1的擴散時間最長是多少（時間越長需要的初始點就越少）

注意邊界和中間的計算方式不同，中間擴散的結果是1,3,5,...,2*n-1，而邊界是1,2,3,...,n$因為邊界可以放在最角落開始）

計算出最長擴散時間max_time后我們就可以對每一段連續為1計算初始最少需要放幾個1 : len = 2*max_time+1 (len代表連續1個數)

最終將答案相加即可

時間復雜度：O(n)

知識點：貪心，邊界條件判斷

核心代碼如下：

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