2023年12月USACO銀組試題解析，附USACO課程培訓(xùn)輔導(dǎo)

1、知識(shí)點(diǎn)：貪心，排序

2、題意：

給定n種牛的數(shù)據(jù)，包含每種牛的重量（不重復(fù)）和數(shù)量，可以選擇m組牛，每組可以選擇任意種牛，需滿足任兩頭牛重量之差>=k，求m組最多一共選擇了多少頭牛？ 

3、題解：

考慮從前往后貪心，首先假設(shè)每個(gè)塔最下面的數(shù)都是負(fù)無(wú)窮，然后從小到大把每一個(gè)數(shù)加入塔中。

考慮加入塔中的過(guò)程，每一次我們都把這個(gè)數(shù)加入到之前塔頂數(shù)最小的位置，如果此時(shí)不能插入，說(shuō)明這個(gè)數(shù)沒(méi)法繼續(xù)插入了。

由于每種數(shù)有很多個(gè)，一個(gè)個(gè)插入時(shí)間復(fù)雜度會(huì)過(guò)大，考慮將每種數(shù)作為一個(gè)整體插入。在當(dāng)前這種數(shù)插入在另一種數(shù)的上方的時(shí)候，要么另一種數(shù)完全覆蓋，要么當(dāng)前這種數(shù)被用完，所以每種數(shù)最多被考慮一次。

1、知識(shí)點(diǎn)：環(huán)，計(jì)數(shù)

2、題意：

給定n個(gè)谷倉(cāng)，和兩個(gè)k個(gè)大小的環(huán)(1-n)，每個(gè)環(huán)上相鄰的兩個(gè)點(diǎn)有邊相連?，F(xiàn)要給1-n的每個(gè)谷倉(cāng)編號(hào)，問(wèn)在滿足兩個(gè)環(huán)上相連狀態(tài)，最多能有幾個(gè)谷倉(cāng)編號(hào)是一樣的?

3、題解：

A與B最多有多少元素相同其實(shí)就是看兩個(gè)環(huán)最多能有多少個(gè)位置能匹配。

匹配的定義是：環(huán)A和環(huán)B按某種順序按位匹配后相同數(shù)字最多是多少個(gè)。

我們可以考慮讓A環(huán)不動(dòng)，B環(huán)循環(huán)右移，對(duì)于每一種字符計(jì)算出需要將環(huán)循環(huán)右移多少步得到，最終查詢哪個(gè)步數(shù)出現(xiàn)次數(shù)最多即可。

注意我們還要考慮環(huán)外點(diǎn)最多有多少匹配：這個(gè)比較簡(jiǎn)單，我們只需要統(tǒng)計(jì)剩下元素里有多少種類A與B是相同的即可。

1、知識(shí)點(diǎn)：思維難題

2、題意：

給定一些目標(biāo)靶的位置，和一串字符串表示牛的操作順序，L代表向左移動(dòng)一個(gè)位置，R代表向右移動(dòng)一個(gè)位置，F(xiàn)代表射擊當(dāng)前位置。牛的初始位置是0，牛最多可以改變一個(gè)位置的操作，求最多能射擊到多少個(gè)靶子？

3、題解： 

先求所有的步驟整體平移-2,-1,0,+1,+2時(shí)可以擊中多少個(gè)目標(biāo)。答案在change[1]-change[5]。再用hit[1-5][位置]記錄每個(gè)位置被擊中了多少次。

然后i從左往右一位位求i之前已經(jīng)固定，i改變以后，能擊中多少次；

這樣求完以后只需要把第i位固定帶來(lái)的影響，更新到change和hit里就可以了。

i從左往右固定過(guò)程中，如果這一位是L和R只影響位置p；

但如果這一位是F，那么固定以后，就要更新hit里的次數(shù)。因?yàn)樗?2 -1 +1 +2都不可能發(fā)生了。

所以更新了兩部分內(nèi)容。

1. 當(dāng)前位置p，如果之后的F因?yàn)?2 -1 +1 +2擊中過(guò)它，現(xiàn)在應(yīng)該i已經(jīng)固定，它一定會(huì)被這一次射擊擊中。所以把-2 -1 +1 +2以后的p位置的hit數(shù)都清0，change對(duì)應(yīng)更新。

2. 當(dāng)前位置p，-2 -1 +1 +2以后的位置的hit數(shù)減少1次，如果減到0就更新change

最終就是，確定會(huì)擊中的數(shù)量cnt，和change數(shù)組維護(hù)的i之后的-2 -1 +1 +2以后的4種不同擊中數(shù)量，根據(jù)L->R R->L之類的變化情況相加。