第七屆簡單的小競賽題解

pA. 解題愛老鼠（太空人老鼠）

對

$i\to j$ 建一條

$c_{i,j}$ 的邊，跑一次 Floyd Warshall，可得到實際的花費

$c_{i,j}^{\prime }$。

建一張圖，

$S$ 向所有

$a_i>C$ 的點建

$(\mathrm{容}\mathrm{量},\mathrm{費}\mathrm{用})=(a_i-C,0)$ 的邊；所有

$a_j<C$ 的點向

$T$ 建

$(\mathrm{容}\mathrm{量},\mathrm{費}\mathrm{用})=(C-a_j,0)$ 的邊；所有

$a_i>C$ 的點向

$a_j<C$ 的點建

$(\mathrm{容}\mathrm{量},\mathrm{費}\mathrm{用})=(\mathrm{\infty },c_{i,j}^{\prime })$ 的邊。

跑一次最小費用流即為答案。

pB. 豬哥選總統

可以使用位元 dp，沒住人的格子以

$1$ 表示，在所處矩形右界的格子也以

$1$ 表示，轉移的時候只要看有沒有跟上一行的矩形對齊判斷是否要

$+1$。

可以做到

$O(n{2}^{2m})$。

pC. 人生遊戲

可以參考康威生命遊戲，發現有一種會移動的狀態叫滑翔機，經過實驗三關分別可以這樣構造：

pD. 送外賣2

直接讓最大的那條邊變

$5$ 倍，然後做最大生成樹，複雜度

$O(m\log (m))$。

pE. 合併排序

假設合併時左邊陣列大小

$x$，右邊陣列大小

$y$，排法共有

$C_x^{x+y}$ 種。

分成最大值在左邊與在右邊的情況，如果在左邊，那不會呼叫 cmp 的次數會是連續一段最大值的長度，假設是

$i$，那有

$C_{y-1}^{x+y-i-1}$ 種排法，期望值為

$\sum _{i=1}^x(x+y-i)\times {\displaystyle \frac{C_{y-1}^{x+y-i-1}}{C_x^{x+y}}}=\frac{xy}{y+1}$，同理最大值在右邊的期望值為

$\frac{xy}{x+1}$。

令

$d{p}_n$ 為大小

$n$ 陣列的答案，那

$d{p}_n=d{p}_{\lfloor \frac{n}{2}\rfloor }+d{p}_{\lceil \frac{n}{2}\rceil }+\frac{\lfloor \frac{n}{2}\rfloor \lceil \frac{n}{2}\rceil }{\lfloor \frac{n}{2}\rfloor +1}+\frac{\lfloor \frac{n}{2}\rfloor \lceil \frac{n}{2}\rceil }{\lceil \frac{n}{2}\rceil +1}$。