柊四千的倉庫

筆者參與了這屆全國賽的驗題，也出了 pD 與 pG 的所有測試資料。由於現場講解有些不夠明確 ，故在這邊放一份兩位驗題者與筆者提供的詳解。題本的連結在 這裡 ，pE / pF / pG / pH 的時間限制分別為 2.0s / 2.3s / 6.5s / 0.1s，其餘題目皆為 1.0s。 A. 礦砂採集 這題是很典型的 連續背包問題 。結論非常簡單：只要不斷貪婪地將單位重量價值最大的礦砂放進背包，直到背包已滿或所有礦砂均已被放入，就能最大化總價值。 一個簡單的做法是將所有礦砂依照單位重量價值由大到小排序，依序放入背包直到滿即可。複雜度是 $O(n \log n)$。 線性做法 雖然並不是本題的考點，但有一個值得一提的 $O(n)$ 做法存在。以下為了方便說明，假定所有的 $x_i$ 均相異。 隨機選擇一個礦砂 $i$，並將所有的礦砂分為單位價值 $\ge x_i$ 與 $< x_i$ 兩堆。 分歧判斷： 若單位價值 $\ge x_i$ 的礦砂可以塞滿背包，則將 $< x_i$ 的礦砂全刪除，並往大的 $x$ 找答案。 反之則將價值 $\ge x_i$ 的礦砂全刪除，往小的 $x$ 找答案。 搜尋完後得到的值代表「總價值最大時，背包中單位重量價值最小的礦砂」，再用這個價值去反求答案。 演算法與 quickselect 非常相似，期望時間複雜度為 $O(n)$。 B. 村莊與小徑 這題是一道最短路徑的問題，但給定的限制中有幾個點要注意： 給定的圖是 DAG（有向無環圖）。 邊權可能是負的。 條件 1 保證這張圖存在拓樸排序，求解可用 top-down DP，或找出拓樸排序後用 bottom-up DP。 // ord = 拓樸排序的點順序 // fr[x] = 連到 x 的所有點 fill(dis, dis+n+ 1 , INF); dis[ 1 ] = 0 ; for ( int i= 1 ; i<=n; i++) { int p = ord[i]; // 找所有能連到 p 的點 j，更新 p 的最短距離 for (Edge j: fr[p]) dis[p] = m