模擬賽

2025多校沖刺CSP模擬賽1

交友（friend）

原題鏈接

寶寶題，直接貪心。

如果有 CGC 這樣橫向或縱向的子串出現，必然是直接給兩端匹配，否則掃描矩陣的每一行，貪心選就行。

煉金（alchemy）

原題鏈接

賽時寫了一個復雜的不真實的做法，可能是題目的特殊性質的原因，總之是沖過去了。

思路就是二分答案，然后搜。（這里用BFS應該更方便一些）

如果當前種類金屬不夠，就向它的原料索取。加一些操作以保證復雜度即可。

這里有一個為什么要用二分答案的問題。在上述做法中，顯然可能有多個不同金屬的合成會用到同一種金屬，由于金屬合成是單向的，預先消耗過多某一類金屬可能使其他金屬的合成不夠用，所以我們采用需要多少拿多少的暴力思路，然后二分答案就很自然了。

當然存在不用二分答案的做法，看你喜歡寫什么。

磁鐵（magnet）

原題鏈接

我要開始辱罵自己了：是不是唐人，預設型DP，都考過無數遍的trick了還能被創飛！這確實是我的嚴重錯誤。我需要徹底承認我完全沒有水平，過的預設型DP題也全是簽到變著花樣耍陰招的垃圾水題，現在毫無天賦的 Oier 要想辦法把國慶集訓的多校聯訓糊弄過去。

顯然的一個思路是把這些磁鐵無縫銜接地排列起來，然后把多出來沒用到的空位插到相鄰磁鐵之間，是一個插板狀物。

先按照升序排序，這樣容易計算貢獻，設 $ f_{ i,j,k } $ 表示前 \(i\) 個磁鐵分為 \(j\) 個連通塊，一共占據了 \(k\) 個空位的方案數。轉移有：

1. 當前磁鐵是一個新的連通塊， $ f_{ i,j,k } = f_{ i-1,j-1,k-1 } $

2. 并到之前的連通塊兩端， $ f_{ i,j,k } = 2 \times f_{ i-1,j,k-len(i) } \times j $

3. 合并兩個連通塊， $ f_{ i,j,k } = f_{ i-1,j+1,k-2len(i)+1 } \times (j+1) \times j $

答案就是 $ \sum_{ i \ge 1 } f_{ n,1,i } \times \dbinom{ m-i+n }{n} $

鐵軌（rail）

原題鏈接

感覺這題很厲害啊。

首先進行一個聰明的轉化：把每個速度抽象成節點，每個路段就是速度之間的連邊，一個完整的路線應該是形成一個歐拉通路（現在是不完整的）。

為方便起見，我們建立一個速度為 \(inf\) 的虛點，最大點向 \(inf\) 連邊， \(inf\) 向最小點連邊。（以上所有邊都是沒有代價的），容易發現此時目標改為歐拉回路沒有影響。

現在問題變成了：在這些節點之間連一些邊（加速邊沒有代價，減速邊代價為兩者之差），使得原圖形成一個歐拉回路。

我們拿出值域上相鄰的兩點，考慮值域跨度能夠同時包含他們的邊，如果這是一個歐拉回路，那么加速邊和減速邊的數量應該是相等的。反之，如果不相等，手動加邊，統計代價。

這樣原圖變成了很多歐拉回路連通塊。最后一個問題是不連通，仍然需要加邊，顯然可能有用的邊一定是值域相鄰的節點之間，用MST狀物維護就好了。