2024年2月（第三場）USACO計算機競賽金牌題解

金牌題解來咯，因文章篇幅有限，將金牌的三道題解分享給大家。

USACO 2024年2月金牌第一題

P1:Bessla motors

解析：

算法：最短路考慮對每一個(ge) 點直接去求其餘(yu) 所有點到它的最短路，我們(men) 發現時間複雜度是$O(nmlogm)$的,會(hui) 超時由於(yu) 題目隻關(guan) 心距離$x$點$R$以內(nei) 的點是否有$k$個(ge) ，所以我們(men) 可以轉化成求距離$x$點距離最近的$k$個(ge) 點的距離分別是多少回憶最短路算法，對於(yu) 多源最短路算法，我們(men) 會(hui) 初始的時候將所有源點都加入到優(you) 先隊列中對於(yu) 這一題其實同理，我們(men) 可以將所有源點都加入優(you) 先隊列，不同的是，我們(men) 不僅(jin) 要記錄到一個(ge) 點的最短路，我們(men) 也要記錄是從(cong) 誰到它形成的最短路這樣子看似我們(men) 的可行狀態是有$n^2$個(ge) 的，但是注意到題目對於(yu) 每個(ge) 點隻需要求距離最近的$k$個(ge) ，且$dijskra$算法優(you) 先處理的就是距離最近的點對，所以對於(yu) 每一個(ge) 點當它出現的到達它的點超過$k$個(ge) 的時候我們(men) 就可以不再去做，於(yu) 是這樣子可以保證可行狀態隻會(hui) 有$O(nk)$個(ge) 時間複雜度：$O(nklogm)$

USACO 2024年2月金牌第二題

P2: Milk Exchange

解析：

算法：數據結構，分治首先題目由於(yu) 數組是一個(ge) 環，所以我們(men) 可以通過遷移把最小值放在最後一位（後續會(hui) 解釋它的用處）考慮數組的次大值（假設下標為(wei) $x$)，這時候假設它左邊包括自己有$l$個(ge) 元素，右邊到$n-1$為(wei) 止有$r$個(ge) 元素我們(men) 考慮在移動$i$次後有多少值會(hui) 變為(wei) 次小值，我們(men) 發現答案等於(yu) 原序列裏有多少長度為(wei) $i+1$的區間包含次小值且不包含最小值我們(men) 考慮以$x$為(wei) 左端點的區間有哪些包含次小值且不包含最小值的, 我們(men) 發現從(cong) $[1,r-1]$長度都是可行的考慮$x-1$: $[2,r]$可行同理$x-i$: $[i+1,r+i-1]$可行於(yu) 是我們(men) 可以對於(yu) $[1,r-1], [2,r], ... ,[l,l+r-2]$這些範圍內(nei) 的數都加上次小值由於(yu) 直接加效率會(hui) 比較低，所以這個(ge) 地方我們(men) 可以利用二階差分來優(you) 化（隻需要修改4個(ge) 位置）最終隻需要考慮當前區間的最小值產(chan) 生的貢獻並將區間分治去做（這就是一開始將最小值移到最後的目的，為(wei) 了避免考慮環帶來的影響）求區間最小值可以利用RMQ做到$O(1)$或者線段樹做到$O(logn)$ 時間複雜度: $O(nlogn)$

USACO 2024年2月金牌第三題

P3: Quantum Moochanics

解析：

算法：貪心，set這個(ge) 題放在金組內(nei) 比較簡單首先我們(men) 可以計算出對於(yu) 任意兩(liang) 個(ge) 位置它們(men) 之間碰撞需要花費的時間（分初始方向分類討論）```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; }}```其次我們(men) 發現每一次碰撞一定是由相鄰兩(liang) 個(ge) 位置產(chan) 生的於(yu) 是我們(men) 可以開一個(ge) set來維護當前相鄰兩(liang) 個(ge) 點的碰撞時間，每一次選出碰撞時間最早的兩(liang) 個(ge) 點，將他們(men) 從(cong) set內(nei) 刪除，並加入新的相鄰兩(liang) 個(ge) 點的碰撞時間, 直到做到set為(wei) 空為(wei) 止時間複雜度: $O(nlogn)$

為(wei) 什麽(me) 參加USACO計算機競賽:

1. 挑戰性：USACO計算機競賽是一項世界級的競賽，提供了挑戰性的問題，涵蓋了廣泛的計算機科學概念，包括算法、數據結構和編程技能。

2. 學習(xi) 機會(hui) ：通過解決(jue) USACO的問題，你可以學到很多關(guan) 於(yu) 算法和編程的知識，提高自己的技能水平。這對於(yu) 計算機科學和編程領域的學習(xi) 都是非常有幫助的。

3. 競賽經驗：參加USACO計算機競賽可以為(wei) 你積累競賽經驗，這在未來參加其他競賽或者申請計算機相關(guan) 的學校和工作時會(hui) 有所幫助。

4. 社區支持：USACO計算機競賽有一個(ge) 龐大的社區，你可以和其他競賽選手交流經驗、分享解決(jue) 問題的方法，這對於(yu) 提高自己的技能也是非常有益的。