USACO1月考題新鮮出爐！白銀組別考情分析

2024年1月USACO月賽已經(jīng)完美落下帷幕，白銀級(jí)別的同學(xué)感覺(jué)考題如何呢？USACO競(jìng)賽除了考察計(jì)算機(jī)語(yǔ)言的熟練運(yùn)用，也考察學(xué)生計(jì)算機(jī)程序的考察，那么USCO競(jìng)賽白銀級(jí)別考題怎么樣？題目難度如何？考察了哪些考點(diǎn)？今天小編老師為大家詳細(xì)介紹USACO競(jìng)賽1月賽，那么同時(shí)，如果發(fā)揮失常的學(xué)生也不要?dú)怵H，一起期待2月考試即可哦~

USACO 2024年1月白銀組別考情分析

第1題

有q對(duì)(x,y)的輸入，每對(duì)表示前1~x個(gè)數(shù)右邊第一個(gè)比它們大的數(shù)必須在下標(biāo)為y的位置，這句話還有一個(gè)隱藏含義就是第x+1到第y-1個(gè)數(shù)必須比前1~x個(gè)數(shù)的最大值要小，即第y個(gè)數(shù)比前y-1個(gè)數(shù)都要大(代碼中稱為前綴最大值)。

用一個(gè)前綴和數(shù)組pre_max[i]表示前i個(gè)數(shù)中的最大值，則a[y]至少為pre_max[y-1]+1。

現(xiàn)在從左往右遍歷a[N]，分類討論每一個(gè)a[i]的情況：

1.a[i]==0且位置i是前綴最大值，令a[i]=pre_max[y-1]+1

2.a[i]==0 且不是前綴最大值，根據(jù)貪心思路令a[i]=1 (字典序最小)

3.a[i]不為0，是第x+1到第y-1個(gè)數(shù)的其中一個(gè)，但是比前x個(gè)數(shù)要大，破壞了前綴最大值的要求，此時(shí)需要把之前的某個(gè)能改的值提高為a[i]

對(duì)全部a[N]修改完畢后，再重新for循環(huán)掃描一遍看看新的a[N]有沒(méi)有沖突，有沖突輸出-1

注意事項(xiàng)：這題有T個(gè)測(cè)試，每個(gè)輸出最后不能帶空格

第2題

以房間1為根節(jié)點(diǎn)的樹(shù)。每次traversal相當(dāng)于從根出發(fā)，沿著父子關(guān)系一直走，一個(gè)traversal的終點(diǎn)一定是一個(gè)葉節(jié)點(diǎn)，因此最小的traversal數(shù)必定為葉節(jié)點(diǎn)數(shù)量，可以用dfs得到，假設(shè)這個(gè)數(shù)量是k。

可以用樹(shù)上DP來(lái)記錄每個(gè)節(jié)點(diǎn)的子樹(shù)擁有的葉節(jié)點(diǎn)數(shù)量，狀態(tài)轉(zhuǎn)移方程為dp[fa] += dp[child],則dp[1]就是整棵樹(shù)擁有的葉節(jié)點(diǎn)數(shù)量

此時(shí)來(lái)看題目對(duì)potion的描述，每次traversal會(huì)在一個(gè)節(jié)點(diǎn)生成一個(gè)potion，下一次traversal前消失，而我們只會(huì)有k個(gè)(即dp[1]個(gè))traversal。

因此實(shí)際上只需要考慮前k個(gè)potion。而由于potion是依靠traversal獲取的，因此potion和traversal,也就是葉節(jié)點(diǎn)，是一對(duì)一綁定的。假設(shè)我們目前在某個(gè)節(jié)點(diǎn)p，從點(diǎn)p出發(fā)獲得的potion數(shù)量不會(huì)超過(guò)點(diǎn)p的子樹(shù)擁有的葉節(jié)點(diǎn)數(shù)量。我們?cè)儆靡粋€(gè)樹(shù)上DP，potion[p]表示點(diǎn)p的子樹(shù)擁有的potion數(shù)量，狀態(tài)轉(zhuǎn)移方程為potion[fa] += potion[child]。統(tǒng)計(jì)完畢后再令potion[p] = min(potion[p], dp[p])。

potion[1]就是本題答案。

第3題

抽屜原理+同余性質(zhì)

題目等價(jià)于N個(gè)數(shù)除以L最多只有3個(gè)不同的余數(shù)，根據(jù)抽屜原理，任意選擇4個(gè)不同的數(shù) ，必定至少有兩個(gè)數(shù)a[i]和a[j]除以L的余數(shù)相同(即模L同余)。由同余的基本性質(zhì)可知abs(a[i]-a[j])必定能被L整除。

因此本題只需要從a[N]中任選4個(gè)不同的數(shù)，枚舉它們的兩兩差值(一共有 = 6 種)，對(duì)這6個(gè)數(shù)，枚舉它們的所有因子fac，進(jìn)行檢驗(yàn)(看看a[1]到a[N]除以fac是不是最多只有3個(gè)余數(shù))，符合要求則令ans+=fac。

課程目標(biāo)：完成USACO的知識(shí)點(diǎn)的學(xué)習(xí)。通過(guò)系統(tǒng)地梳理，充分的練習(xí)熟悉考試的題型和難點(diǎn)重點(diǎn)，沖刺USACO競(jìng)賽高分

USACO初級(jí)班：適合計(jì)算機(jī)編程剛?cè)腴T(mén)，語(yǔ)言基礎(chǔ)薄弱，無(wú)比賽經(jīng)驗(yàn)計(jì)劃申請(qǐng)計(jì)算機(jī)專業(yè)的中學(xué)生；

USACO中級(jí)班：適合至少會(huì)一門(mén)計(jì)算機(jī)編程語(yǔ)言(推薦C++或Java)，算法基礎(chǔ)一般，少量比賽經(jīng)驗(yàn)的學(xué)生

USACO高級(jí)班：適合具有完善的計(jì)算機(jī)編程語(yǔ)言基礎(chǔ)，有入門(mén)算法經(jīng)驗(yàn)，一定比賽經(jīng)驗(yàn)，如NOIP，USACO銀組等的學(xué)生

目前，犀牛已在上海、北京、廣州、深圳、蘇州、杭州、南京、青島、無(wú)錫、武漢、合肥、成都等多個(gè)城市開(kāi)設(shè)校區(qū)，線上線下全面開(kāi)班，提供國(guó)際競(jìng)賽、國(guó)際課程、語(yǔ)言培訓(xùn)、擇校、留學(xué)一站式課程培訓(xùn)，致力于為每一家庭提供優(yōu)質(zhì)服務(wù)。