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

課程咨詢熱線 400-656-1680

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

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

編輯:橙子來源:犀牛國(guó)際教育瀏覽:

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

 

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

銀組第1題代碼

圖片銀組第2題代碼

圖片

圖片
 

圖片
銀組第一題解析

圖片

 

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

 

2、題意:

 

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

 

3、題解:

 

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

 

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

 

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

 

圖片
銀組第二題解析

圖片

 

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

 

2、題意:

 

給定n個(gè)谷倉,和兩個(gè)k個(gè)大小的環(huán)(1-n),每個(gè)環(huán)上相鄰的兩個(gè)點(diǎn)有邊相連?,F(xiàn)要給1-n的每個(gè)谷倉編號(hào),問在滿足兩個(gè)環(huán)上相連狀態(tài),最多能有幾個(gè)谷倉編號(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位固定帶來的影響,更新到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)固定,它一定會(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之類的變化情況相加。

 

 

2023-2024賽季USACO參賽時(shí)間表
圖片

 

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

 

圖片

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

 

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

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

 

USACO授課內(nèi)容

 

圖片

 

USACO銅升銀沖刺課大綱:

圖片

USACO銀升金沖刺課大綱:

圖片

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

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

TOP