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

解析：

算法：最短路

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

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

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

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

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

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

解析：

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

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

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

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

我們考慮以$x$為左端點的區(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ù)都加上次小值

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

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

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

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

解析：

算法：貪心，set

這個題放在金組內(nèi)比較簡單

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

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

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

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