犀牛國際教育旗下指定官方網(wǎng)站~

課程咨詢熱線 400-656-1680

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

發(fā)布時間:2024-01-12 10:36:21

編輯:橙子來源:犀牛國際教育瀏覽:

USACO第一次月賽已落下帷幕,這次銀組的題目與往年差別比較大,往年??缄P(guān)于圖的題目今年就沒有,銀組今年前兩道題是找規(guī)律,第三道題目是枚舉算法,我們已將12月月賽題目解析整理完畢。

 

12月USACO月賽銀組
圖片
解析代碼
圖片

銀組第1題代碼

圖片銀組第2題代碼

圖片

圖片
 

圖片
銀組第一題解析

圖片

 

1、知識點(diǎn):貪心,排序

 

2、題意:

 

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

 

3、題解:

 

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

 

考慮加入塔中的過程,每一次我們都把這個數(shù)加入到之前塔頂數(shù)最小的位置,如果此時不能插入,說明這個數(shù)沒法繼續(xù)插入了。

 

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

 

圖片
銀組第二題解析

圖片

 

1、知識點(diǎn):環(huán),計(jì)數(shù)

 

2、題意:

 

給定n個谷倉,和兩個k個大小的環(huán)(1-n),每個環(huán)上相鄰的兩個點(diǎn)有邊相連。現(xiàn)要給1-n的每個谷倉編號,問在滿足兩個環(huán)上相連狀態(tài),最多能有幾個谷倉編號是一樣的?

 

3、題解:

 

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

 

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

 

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

 

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

 

圖片
銀組第三題解析

圖片

 

1、知識點(diǎn):思維難題

 

2、題意:

 

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

 

3、題解: 

 

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

 

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

 

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

 

i從左往右固定過程中,如果這一位是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擊中過它,現(xiàn)在應(yīng)該i已經(jīng)固定,它一定會被這一次射擊擊中。所以把-2 -1 +1 +2以后的p位置的hit數(shù)都清0,change對應(yīng)更新。

 

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


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

 

 

2023-2024賽季USACO參賽時間表
圖片

 

USACO競賽中國孩子可以參加4場,分為三場月賽+一場公開賽,賽事時間詳細(xì)安排如下:

 

圖片

USACO競賽報(bào)名,僅需要在官網(wǎng)注冊賬號即可,免費(fèi)注冊,注冊即為青銅級別。USACO官網(wǎng):http://www.usaco.org/

 

圖片
USACO競賽沖銀沖金培訓(xùn)課程
圖片
圖片

USACO競賽接下來還有2次月賽和1次公開賽,分別在1月,2月和3月,同學(xué)們還有三次沖獎機(jī)會,針對銅級想要提升銀級、金級、和鉑金級別,開設(shè)有一對一提升課程,以及小班課。

 

USACO授課內(nèi)容

 

圖片

 

USACO銅升銀沖刺課大綱:

圖片

USACO銀升金沖刺課大綱:

圖片

相關(guān)標(biāo)簽:

相關(guān)文章推薦/ARTICLE RECOMMENDED

TOP