犀牛國際教育旗下指定官方網站~

課程咨詢熱線 400-656-1680

2023-2024年USACO競賽第三場月賽金組試題解析已出!

發(fā)布時間:2024-02-26 10:57:15 編輯:Lily來源:網絡

2023-2024年USACO競賽第三場月賽考試已經正式結束,今天為大家整理了USACO競賽金牌真題解析。

 

 
P1:Bessla motors

解析:

算法:最短路

 

考慮對每一個點直接去求其余所有點到它的最短路,我們發(fā)現時間復雜度是$O(nmlogm)$的,會超時

 

由于題目只關心距離$x$點$R$以內的點是否有$k$個,所以我們可以轉化成求距離$x$點距離最近的$k$個點的距離分別是多少

 

回憶最短路算法,對于多源最短路算法,我們會初始的時候將所有源點都加入到優(yōu)先隊列中

 

對于這一題其實同理,我們可以將所有源點都加入優(yōu)先隊列,不同的是,我們不僅要記錄到一個點的最短路,我們也要記錄是從誰到它形成的最短路

 

這樣子看似我們的可行狀態(tài)是有$n^2$個的,但是注意到題目對于每個點只需要求距離最近的$k$個,且$dijskra$算法優(yōu)先處理的就是距離最近的點對,所以對于每一個點當它出現的到達它的點超過$k$個的時候我們就可以不再去做,于是這樣子可以保證可行狀態(tài)只會有$O(nk)$個

 

時間復雜度:$O(nklogm)$

 

 
P2: Milk Exchange

解析:

算法:數據結構,分治

 

首先題目由于數組是一個環(huán),所以我們可以通過遷移把最小值放在最后一位(后續(xù)會解釋它的用處)

 

考慮數組的次大值(假設下標為$x$),這時候假設它左邊包括自己有$l$個元素,右邊到$n-1$為止有$r$個元素

 

我們考慮在移動$i$次后有多少值會變?yōu)榇涡≈担覀儼l(fā)現答案等于原序列里有多少長度為$i+1$的區(qū)間包含次小值且不包含最小值

 

我們考慮以$x$為左端點的區(qū)間有哪些包含次小值且不包含最小值的, 我們發(fā)現從$[1,r-1]$長度都是可行的

 

考慮$x-1$: $[2,r]$可行

 

同理$x-i$: $[i+1,r+i-1]$可行

 

于是我們可以對于$[1,r-1], \ [2,r], \ ... ,[l,l+r-2]$這些范圍內的數都加上次小值

 

由于直接加效率會比較低,所以這個地方我們可以利用二階差分來優(yōu)化(只需要修改4個位置)

 

最終只需要考慮當前區(qū)間的最小值產生的貢獻并將區(qū)間分治去做(這就是一開始將最小值移到最后的目的,為了避免考慮環(huán)帶來的影響)

 

求區(qū)間最小值可以利用RMQ做到$O(1)$或者線段樹做到$O(logn)$

 

時間復雜度: $O(nlogn)$

 

 
P3: Quantum Moochanics

解析:

算法:貪心,set

 

這個題放在金組內比較簡單

 

首先我們可以計算出對于任意兩個位置它們之間碰撞需要花費的時間(分初始方向分類討論)

```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ā)現每一次碰撞一定是由相鄰兩個位置產生的

 

于是我們可以開一個set來維護當前相鄰兩個點的碰撞時間,每一次選出碰撞時間最早的兩個點,將他們從set內刪除,并加入新的相鄰兩個點的碰撞時間, 直到做到set為空為止

 

時間復雜度: $O(nlogn)$

 

USACO競賽介紹

 

USACO競賽全程USA Computing Olympiad,美國信息學奧林匹克競賽,旨在為每年夏季舉辦的國際信息學奧林匹克競賽(IOI)選拔美國隊隊員。

圖片

USACO競賽時間安排:

每年12月考試,

第一次月賽:2023年12月15日-18日

第二次月賽:2024年1月26日-29日

第三次月賽:2024年2月16日-19日

美國公開賽:2024年3月15日-18日

(中國學生只能參加到公開賽)

集訓營:2024年5月23日-6月1日

EGOI:2024年7月21日-27日(荷蘭)

IOI:2024年9月1日-8日(埃及)

 

◆ 報名官網:http://www.usaco.org/

◆ 競賽語言:Java、Python、Pascal、C和C++

◆ 競賽級別:USACO競賽分為銅組、銀組、金組和白金組四個級別

◆ 報名費:免費;考生任意時間直接登錄官網,注冊即為報名

◆ 競賽時長:前3場晉級賽每場4個小時,US Open 5個小時。

◆ 考試地點:線上比賽,個人參賽,通過登錄USACO官網,在線提交代碼

 

USACO競賽含金量

 

1、名校申請敲門磚

USACO競賽整體含金量比較高,備受國際學校的認可,目前不少國際院校都非常認可USACO競賽的成績,MIT學校更是力薦學生參加USACO競賽。

圖片

 

2、提高計算機能力

參賽者通過參加USACO可以提高編程技能和算法分析能力。同時還能擴展視野、了解更多計算機科學知識,并結交志同道合的伙伴,對未來的學習和職業(yè)生涯有很大幫助。

 

 

幾年級參加USACO競賽比較好?USACO競賽應該如何規(guī)劃?

 

USACO競賽資料/規(guī)劃
在線客服咨詢

相關標簽:
TOP