發(fā)布時(shí)間:2024-02-26 15:14:58 編輯:小Q來源:網(wǎng)站
USACO競(jìng)賽怎么備考?競(jìng)賽分為多個(gè)等級(jí),我們?yōu)榇蠹曳治鲆幌裸y級(jí)別的題目解析,給大家一些參考,此外,還有不同年級(jí)的USACO競(jìng)賽備考規(guī)劃,歡迎咨詢網(wǎng)站客服了解詳情~
本月比賽出現(xiàn)了兩個(gè)變化:
①由于參賽人數(shù)過多,網(wǎng)站在比賽過程中崩潰了。
②在1月賽中,USACO官方提供了中文題面,對(duì)年齡段較低的信奧選手非常友好,建議都可以嘗試做一下本次比賽的題目。
有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(字典序最?。?/p>
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]有沒有沖突,有沖突輸出-1
注意事項(xiàng):這題有T個(gè)測(cè)試,每個(gè)輸出最后不能帶空格
以房間1為根節(jié)點(diǎn)的樹。每次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??梢杂脴渖螪P來記錄每個(gè)節(jié)點(diǎn)的子樹擁有的葉節(jié)點(diǎn)數(shù)量,狀態(tài)轉(zhuǎn)移方程為
dp[fa]+=dp[child],則dp[1]就是整棵樹擁有的葉節(jié)點(diǎn)數(shù)量
此時(shí)來看題目對(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ì)超過點(diǎn)p的子樹擁有的葉節(jié)
點(diǎn)數(shù)量。我們?cè)儆靡粋€(gè)樹上DP,potion[p]表示點(diǎn)p的子樹擁有的potion數(shù)量,狀態(tài)轉(zhuǎn)移方程
為potion[fa]+=potion[child]。統(tǒng)計(jì)完畢后再令potion[p]=min(potion[p],dp[p])。
最終potion[1]就是本題答案。
抽屜原理+同余性質(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。
USACO的前四場(chǎng)比賽是在線進(jìn)行的,而且歡迎世界各地的選手參加,近年來隨著國(guó)內(nèi)信奧學(xué)習(xí)熱度暴增,參加USACO的國(guó)內(nèi)選手人數(shù)也與日俱增。
對(duì)于希望提升或檢驗(yàn)自己信息學(xué)水平的中國(guó)選手,USACO是非常值得參加的;對(duì)于有前往美國(guó)留學(xué)意向的選手,USACO Platinum白金組的獲獎(jiǎng),也是相當(dāng)硬核的履歷加分項(xiàng)!
對(duì)于這一階段的孩子來說,培養(yǎng)編程計(jì)算機(jī)的興趣和思維能力更重要。建議大多數(shù)同學(xué)通過參加編程俱樂部,或者編程活動(dòng)使得學(xué)生對(duì)編程有濃厚的興趣,在編程方面可以從較為簡(jiǎn)單的Scratch、Code.org入手,了解基本的編程概念和算法原理。
接觸編程比較早的同學(xué),從6年級(jí)開始就已經(jīng)系統(tǒng)的學(xué)計(jì)算機(jī)相關(guān)知識(shí)了。那么對(duì)于剛接觸USACO競(jìng)賽的同學(xué)來說,可以先以USACO競(jìng)賽語言為突破口,先學(xué)習(xí)編程語言,對(duì)編程零基礎(chǔ)的同學(xué)可以從Python或Java入門,并學(xué)習(xí)對(duì)應(yīng)的數(shù)據(jù)結(jié)構(gòu)和算法??梢酝ㄟ^USACO競(jìng)賽官方的題庫(kù)在線練習(xí),在一定練習(xí)后可以準(zhǔn)備USACO競(jìng)賽銅級(jí)考試。
在這個(gè)階段,學(xué)生已經(jīng)掌握了較為扎實(shí)的基礎(chǔ)知識(shí),可以正式參加USACO競(jìng)賽實(shí)戰(zhàn)了,在備考時(shí),重點(diǎn)是深入學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)和算法,需要熟練掌握至少一門編程語言,建議學(xué)習(xí)C++語言,后面如果想繼續(xù)挑戰(zhàn)信奧賽也是支持C++語言的。
在備考USACO競(jìng)賽時(shí)還建議同學(xué)們多參加模擬比賽以及解題訓(xùn)練,不斷優(yōu)化解題思維。
這些學(xué)生面臨著申請(qǐng)壓力,通過USACO競(jìng)賽來提升申請(qǐng)競(jìng)爭(zhēng)力是很明智的,因?yàn)閁SACO競(jìng)賽備賽周期短,出分快還是很香的。
學(xué)生這一階段需要提升USACO競(jìng)賽獎(jiǎng)項(xiàng)含金量,比如爭(zhēng)取達(dá)到USACO白金級(jí)別。
USACO競(jìng)賽培訓(xùn)輔導(dǎo)課程:咨詢網(wǎng)站客服了解~
微信咨詢