發(fā)布時(shí)間:2024-01-12 10:36:21
編輯:橙子來源:犀牛國(guó)際教育瀏覽:次
USACO第一次月賽已落下帷幕,這次銀組的題目與往年差別比較大,往年??缄P(guān)于圖的題目今年就沒有,銀組今年前兩道題是找規(guī)律,第三道題目是枚舉算法,我們已將12月月賽題目解析整理完畢。
銀組第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之類的變化情況相加。
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)賽接下來還有2次月賽和1次公開賽,分別在1月,2月和3月,同學(xué)們還有三次沖獎(jiǎng)機(jī)會(huì),針對(duì)銅級(jí)想要提升銀級(jí)、金級(jí)、和鉑金級(jí)別,開設(shè)有一對(duì)一提升課程,以及小班課。
USACO授課內(nèi)容
USACO銅升銀沖刺課大綱:
USACO銀升金沖刺課大綱:
微信咨詢
支付二維碼