發(fā)布時(shí)間:2024-02-26 10:57:15 編輯:Lily來源:網(wǎng)絡(luò)
2023-2024年USACO競(jìng)賽第三場(chǎng)月賽考試已經(jīng)正式結(jié)束,今天為大家整理了USACO競(jìng)賽金牌真題解析。
解析:
算法:最短路
考慮對(duì)每一個(gè)點(diǎn)直接去求其余所有點(diǎn)到它的最短路,我們發(fā)現(xiàn)時(shí)間復(fù)雜度是$O(nmlogm)$的,會(huì)超時(shí)
由于題目只關(guān)心距離$x$點(diǎn)$R$以內(nèi)的點(diǎn)是否有$k$個(gè),所以我們可以轉(zhuǎn)化成求距離$x$點(diǎn)距離最近的$k$個(gè)點(diǎn)的距離分別是多少
回憶最短路算法,對(duì)于多源最短路算法,我們會(huì)初始的時(shí)候?qū)⑺性袋c(diǎn)都加入到優(yōu)先隊(duì)列中
對(duì)于這一題其實(shí)同理,我們可以將所有源點(diǎn)都加入優(yōu)先隊(duì)列,不同的是,我們不僅要記錄到一個(gè)點(diǎn)的最短路,我們也要記錄是從誰到它形成的最短路
這樣子看似我們的可行狀態(tài)是有$n^2$個(gè)的,但是注意到題目對(duì)于每個(gè)點(diǎn)只需要求距離最近的$k$個(gè),且$dijskra$算法優(yōu)先處理的就是距離最近的點(diǎn)對(duì),所以對(duì)于每一個(gè)點(diǎn)當(dāng)它出現(xiàn)的到達(dá)它的點(diǎn)超過$k$個(gè)的時(shí)候我們就可以不再去做,于是這樣子可以保證可行狀態(tài)只會(huì)有$O(nk)$個(gè)
時(shí)間復(fù)雜度:$O(nklogm)$
解析:
算法:數(shù)據(jù)結(jié)構(gòu),分治
首先題目由于數(shù)組是一個(gè)環(huán),所以我們可以通過遷移把最小值放在最后一位(后續(xù)會(huì)解釋它的用處)
考慮數(shù)組的次大值(假設(shè)下標(biāo)為$x$),這時(shí)候假設(shè)它左邊包括自己有$l$個(gè)元素,右邊到$n-1$為止有$r$個(gè)元素
我們考慮在移動(dòng)$i$次后有多少值會(huì)變?yōu)榇涡≈担覀儼l(fā)現(xiàn)答案等于原序列里有多少長(zhǎng)度為$i+1$的區(qū)間包含次小值且不包含最小值
我們考慮以$x$為左端點(diǎn)的區(qū)間有哪些包含次小值且不包含最小值的, 我們發(fā)現(xiàn)從$[1,r-1]$長(zhǎng)度都是可行的
考慮$x-1$: $[2,r]$可行
同理$x-i$: $[i+1,r+i-1]$可行
于是我們可以對(duì)于$[1,r-1], \ [2,r], \ ... ,[l,l+r-2]$這些范圍內(nèi)的數(shù)都加上次小值
由于直接加效率會(huì)比較低,所以這個(gè)地方我們可以利用二階差分來優(yōu)化(只需要修改4個(gè)位置)
最終只需要考慮當(dāng)前區(qū)間的最小值產(chǎn)生的貢獻(xiàn)并將區(qū)間分治去做(這就是一開始將最小值移到最后的目的,為了避免考慮環(huán)帶來的影響)
求區(qū)間最小值可以利用RMQ做到$O(1)$或者線段樹做到$O(logn)$
時(shí)間復(fù)雜度: $O(nlogn)$
解析:
算法:貪心,set
這個(gè)題放在金組內(nèi)比較簡(jiǎn)單
首先我們可以計(jì)算出對(duì)于任意兩個(gè)位置它們之間碰撞需要花費(fèi)的時(shí)間(分初始方向分類討論)
```c++
double cal(int x,int y){
if (x%2==1){
double tt=1.0*(a[y]-a[x])/(c[x]+c[y]);
int k=ceil(tt)-1;
double u=tt-floor(tt);
if (u<1e-8) u=1;
return k*2+u;
} else {
double tt=1.0*(a[y]-a[x])/(c[x]+c[y]);
int k=ceil(tt);
double u=tt-floor(tt);
if (u<1e-8) u=1;
return k*2-1+u;
}
}
```
其次我們發(fā)現(xiàn)每一次碰撞一定是由相鄰兩個(gè)位置產(chǎn)生的
于是我們可以開一個(gè)set來維護(hù)當(dāng)前相鄰兩個(gè)點(diǎn)的碰撞時(shí)間,每一次選出碰撞時(shí)間最早的兩個(gè)點(diǎn),將他們從set內(nèi)刪除,并加入新的相鄰兩個(gè)點(diǎn)的碰撞時(shí)間, 直到做到set為空為止
時(shí)間復(fù)雜度: $O(nlogn)$
USACO競(jìng)賽全程USA Computing Olympiad,美國(guó)信息學(xué)奧林匹克競(jìng)賽,旨在為每年夏季舉辦的國(guó)際信息學(xué)奧林匹克競(jìng)賽(IOI)選拔美國(guó)隊(duì)隊(duì)員。
USACO競(jìng)賽時(shí)間安排:
每年12月考試,
第一次月賽:2023年12月15日-18日
第二次月賽:2024年1月26日-29日
第三次月賽:2024年2月16日-19日
美國(guó)公開賽:2024年3月15日-18日
(中國(guó)學(xué)生只能參加到公開賽)
集訓(xùn)營(yíng):2024年5月23日-6月1日
EGOI:2024年7月21日-27日(荷蘭)
IOI:2024年9月1日-8日(埃及)
◆ 報(bào)名官網(wǎng):http://www.usaco.org/
◆ 競(jìng)賽語言:Java、Python、Pascal、C和C++
◆ 競(jìng)賽級(jí)別:USACO競(jìng)賽分為銅組、銀組、金組和白金組四個(gè)級(jí)別
◆ 報(bào)名費(fèi):免費(fèi);考生任意時(shí)間直接登錄官網(wǎng),注冊(cè)即為報(bào)名
◆ 競(jìng)賽時(shí)長(zhǎng):前3場(chǎng)晉級(jí)賽每場(chǎng)4個(gè)小時(shí),US Open 5個(gè)小時(shí)。
◆ 考試地點(diǎn):線上比賽,個(gè)人參賽,通過登錄USACO官網(wǎng),在線提交代碼
1、名校申請(qǐng)敲門磚
USACO競(jìng)賽整體含金量比較高,備受國(guó)際學(xué)校的認(rèn)可,目前不少國(guó)際院校都非常認(rèn)可USACO競(jìng)賽的成績(jī),MIT學(xué)校更是力薦學(xué)生參加USACO競(jìng)賽。
2、提高計(jì)算機(jī)能力
參賽者通過參加USACO可以提高編程技能和算法分析能力。同時(shí)還能擴(kuò)展視野、了解更多計(jì)算機(jī)科學(xué)知識(shí),并結(jié)交志同道合的伙伴,對(duì)未來的學(xué)習(xí)和職業(yè)生涯有很大幫助。
幾年級(jí)參加USACO競(jìng)賽比較好?USACO競(jìng)賽應(yīng)該如何規(guī)劃?
USACO競(jìng)賽資料/規(guī)劃
在線客服咨詢
微信咨詢