發(fā)布時間:2024-01-12 10:36:21
編輯:橙子來源:犀牛國際教育瀏覽:次
USACO第一次月賽已落下帷幕,這次銀組的題目與往年差別比較大,往年??缄P于圖的題目今年就沒有,銀組今年前兩道題是找規(guī)律,第三道題目是枚舉算法,我們已將12月月賽題目解析整理完畢。
銀組第1題代碼
銀組第2題代碼
1、知識點:貪心,排序
2、題意:
給定n種牛的數(shù)據(jù),包含每種牛的重量(不重復)和數(shù)量,可以選擇m組牛,每組可以選擇任意種牛,需滿足任兩頭牛重量之差>=k,求m組最多一共選擇了多少頭牛?
3、題解:
考慮從前往后貪心,首先假設每個塔最下面的數(shù)都是負無窮,然后從小到大把每一個數(shù)加入塔中。
考慮加入塔中的過程,每一次我們都把這個數(shù)加入到之前塔頂數(shù)最小的位置,如果此時不能插入,說明這個數(shù)沒法繼續(xù)插入了。
由于每種數(shù)有很多個,一個個插入時間復雜度會過大,考慮將每種數(shù)作為一個整體插入。在當前這種數(shù)插入在另一種數(shù)的上方的時候,要么另一種數(shù)完全覆蓋,要么當前這種數(shù)被用完,所以每種數(shù)最多被考慮一次。
1、知識點:環(huán),計數(shù)
2、題意:
給定n個谷倉,和兩個k個大小的環(huán)(1-n),每個環(huán)上相鄰的兩個點有邊相連。現(xiàn)要給1-n的每個谷倉編號,問在滿足兩個環(huán)上相連狀態(tài),最多能有幾個谷倉編號是一樣的?
3、題解:
A與B最多有多少元素相同其實就是看兩個環(huán)最多能有多少個位置能匹配。
匹配的定義是:環(huán)A和環(huán)B按某種順序按位匹配后相同數(shù)字最多是多少個。
我們可以考慮讓A環(huán)不動,B環(huán)循環(huán)右移,對于每一種字符計算出需要將環(huán)循環(huán)右移多少步得到,最終查詢哪個步數(shù)出現(xiàn)次數(shù)最多即可。
注意我們還要考慮環(huán)外點最多有多少匹配:這個比較簡單,我們只需要統(tǒng)計剩下元素里有多少種類A與B是相同的即可。
1、知識點:思維難題
2、題意:
給定一些目標靶的位置,和一串字符串表示牛的操作順序,L代表向左移動一個位置,R代表向右移動一個位置,F(xiàn)代表射擊當前位置。牛的初始位置是0,牛最多可以改變一個位置的操作,求最多能射擊到多少個靶子?
3、題解:
先求所有的步驟整體平移-2,-1,0,+1,+2時可以擊中多少個目標。答案在change[1]-change[5]。再用hit[1-5][位置]記錄每個位置被擊中了多少次。
然后i從左往右一位位求i之前已經(jīng)固定,i改變以后,能擊中多少次;
這樣求完以后只需要把第i位固定帶來的影響,更新到change和hit里就可以了。
i從左往右固定過程中,如果這一位是L和R只影響位置p;
但如果這一位是F,那么固定以后,就要更新hit里的次數(shù)。因為它-2 -1 +1 +2都不可能發(fā)生了。
所以更新了兩部分內容。
1. 當前位置p,如果之后的F因為-2 -1 +1 +2擊中過它,現(xiàn)在應該i已經(jīng)固定,它一定會被這一次射擊擊中。所以把-2 -1 +1 +2以后的p位置的hit數(shù)都清0,change對應更新。
2. 當前位置p,-2 -1 +1 +2以后的位置的hit數(shù)減少1次,如果減到0就更新change
最終就是,確定會擊中的數(shù)量cnt,和change數(shù)組維護的i之后的-2 -1 +1 +2以后的4種不同擊中數(shù)量,根據(jù)L->R R->L之類的變化情況相加。
USACO競賽中國孩子可以參加4場,分為三場月賽+一場公開賽,賽事時間詳細安排如下:
USACO競賽報名,僅需要在官網(wǎng)注冊賬號即可,免費注冊,注冊即為青銅級別。USACO官網(wǎng):http://www.usaco.org/
USACO競賽接下來還有2次月賽和1次公開賽,分別在1月,2月和3月,同學們還有三次沖獎機會,針對銅級想要提升銀級、金級、和鉑金級別,開設有一對一提升課程,以及小班課。
USACO授課內容
USACO銅升銀沖刺課大綱:
USACO銀升金沖刺課大綱:
IBDP03-07
小托福04-03
美國留學04-05
微信咨詢
支付二維碼