2022年12月USACO銅級真題——Feeding The Cow解析

今天我們(men) 要給大家講解的是一道 2022 年 12 月的銅級真題——Feeding The Cow。

英文好的小夥(huo) 伴推薦看英文原版題目↓

覺得英文理解起來麻煩的同學也可以看翻譯好的中文題：

解題分析：

題目要求得種植的草的數目要求最小，那麽(me) 就意味所種植的草能夠盡可能大的覆蓋更多的?。

那麽(me) 問題來了，草種在哪裏才會(hui) 被更多的?吃到呢？

我們(men) 現在假設有多頭同品種的牛，願意移動的最大步數為(wei) 2，那麽(me) 如下圖選擇草的位置能夠保證之中的草的數量是最少的。

如上圖所示，當從(cong) 編號為(wei) i的牛開始考慮種草的位置時，我們(men) 可以將草種在第i+k的位置，這就意味距離location為(wei) i+k的草的距離小於(yu) k的牛都能夠有草吃。

如果我們(men) 定草的位置為(wei) patch，牛的位置為(wei) cow，那麽(me) 當滿足cow-patch<=k時， 則無需考慮新種草；

反之，當 cow-patch>k，如上圖編號為(wei) 6的牛正好無法吃到，那麽(me) 就需要確定下一個(ge) 草的位置；

由上圖可以看出，第二顆草的位置應該為(wei) 6+k，即patch = 8；

同理，第三顆草的位置應該是編號11的牛的位置11+k，但是此時你可能已經注意到11+2已經超出了總共的牛的數量，那麽(me) 此時我們(men) 隻要將草種在編號為(wei) 11的牛的腳下，即patch = 11，這樣剩下的牛肯定都能被覆蓋。

剛剛我們(men) 分析是基於(yu) 所有的牛都是同品種的假設，那麽(me) 如果是不同品種，分析過程會(hui) 有變化麽(me) ？

我們(men) 以題目中給出的測試案例來分析：

n=5；且牛的品種順序為(wei) GHHGG

k=1；

由於(yu) 第一頭牛是G型牛，那麽(me) 應該在patch_G= 2 的位置種G型草；

由於(yu) 第二頭牛的位置雖然被第一顆草的位置覆蓋，但是由於(yu) 品類不同，需要在patch_H= 3的位置種H型草；

第三頭牛被patch_H=2 的草覆蓋，所以不用考慮；

第四頭牛是G型，且沒有被任何草覆蓋，因此需要在patch_G = 5的位置種值G型草；

第五頭牛被patch_G = 5的草覆蓋，所以不用考慮。

分析總結：

按順序考慮 1…N 中的每頭奶牛 i，判斷是否需要種草。

如果當前的奶牛已經被覆蓋，那麽(me) 我們(men) 就不需要再種草了，我們(men) 可以繼續判斷下一頭牛。

如果沒有被覆蓋，我們(men) 需要為(wei) 這頭牛種草，那麽(me) 我們(men) 應該把它放在哪裏呢？

為(wei) 了每棵草能覆蓋更多的牛，那麽(me) 應該將其種在i+K 的位置。不僅(jin) 奶牛 i 會(hui) 被覆蓋，而且在該草的 K 距離內(nei) 的所有奶牛也將被覆蓋。

當判斷到最後幾頭奶牛時，可能會(hui) 遇到一種情況：奶牛 i 需要喂食並且 i+K>N，我們(men) 可以將草種在位置 i，因為(wei) i−1+K≥N，這個(ge) 補丁覆蓋了與(yu) 奶牛 i 同品種的從(cong) i 到 N 的所有奶牛。

當牛的品種大於(yu) 等於(yu) 2，會(hui) 存在一種極端情況： 如果我們(men) 嚐試在位置 i 種草，但那裏已經有一個(ge) 草（如下圖）。在這種情況下，我們(men) 可以將草種在 i-1 處，因為(wei) i-1處和 i 處不可能已經有對應類型的草。

該解決(jue) 方案的運行時間為(wei) O(N)，因為(wei) 我們(men) 隻是對 N 頭奶牛進行單次傳(chuan) 遞。

USACO計算機競賽

USACO(United States of America Computing Olypiad)，即美國計算機奧林匹克競賽，是針對美國中學生乃至全球學生的計算機編程在線競賽。

編程作為(wei) 一門使用技能會(hui) 讓學理工科的學生受益終生。即便是文商科的同學，編程訓練本身帶來的思維優(you) 勢也可以極大地促進學習(xi) 。

參賽語言：C、C++、Java、Python

晉級路徑：青銅級→白銀級→黃金級→鉑金級，難度逐級遞增。新注冊(ce) 的參賽選手需要從(cong) 最低組別開始打起。

為(wei) 了便於(yu) 大家理解，我們(men) 把 USACO 與(yu) AMC 競賽的難度做了簡單的對比，參考如下?

鉑金組≈AIME

黃金組≈AMC12

白銀組≈AMC10

青銅組≈AMC 8

如果想要申請美國院校，USACO 一定是十分適合的選擇。

USACO計算機暑期班火熱招生

機構計算機教研組以 USACO 組織推薦的官方網站 USACO guide 上的知識點為(wei) 主，對各組別算法進行了整理和更新，並創作了 500+的模擬真題，助力學生衝(chong) 擊 USACO 金銀成績！

USACO 課程體(ti) 係設置

常規+衝(chong) 刺

常規：知識講解，夯實基礎

衝(chong) 刺：真題演練，高效備考

我們(men) 采用 Lecture + Lab 的授課形式。這是目前美國很多主流大學都在用的教育體(ti) 係，我們(men) 經過改良優(you) 化後，利用該體(ti) 係來高效備戰 USACO 考試。

Lecture：2-6 人的Lecture幫助學生快速了解知識點內(nei) 容；

Lab：1v1 形式的研討和交流，旨在幫助學生深化對知識的理解以及激發學生的思維潛力。