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

解析：

算法：最短路

考慮對每一個(gè)點(diǎn)直接去求其余所有點(diǎn)到它的最短路，我們發(fā)現(xiàn)時(shí)間復(fù)雜度是$O(nmlogm)$的,會超時(shí)

由于題目只關(guān)心距離$x$點(diǎn)$R$以內(nèi)的點(diǎn)是否有$k$個(gè)，所以我們可以轉(zhuǎn)化成求距離$x$點(diǎn)距離最近的$k$個(gè)點(diǎn)的距離分別是多少

回憶最短路算法，對于多源最短路算法，我們會初始的時(shí)候?qū)⑺性袋c(diǎn)都加入到優(yōu)先隊(duì)列中

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

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

時(shí)間復(fù)雜度：$O(nklogm)$

解析：

算法：數(shù)據(jù)結(jié)構(gòu)，分治

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

考慮數(shù)組的次大值（假設(shè)下標(biāo)為$x$)，這時(shí)候假設(shè)它左邊包括自己有$l$個(gè)元素，右邊到$n-1$為止有$r$個(gè)元素

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

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

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

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

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

由于直接加效率會比較低，所以這個(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)比較簡單

首先我們可以計(jì)算出對于任意兩個(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)$