# 第七屆簡單的小競賽題解

## [pA. 解題愛老鼠（太空人老鼠）](https://zerojudge.tw/ShowProblem?problemid=k800)

對 $i\to j$ 建一條 $c_{i,j}$ 的邊，跑一次 Floyd Warshall，可得到實際的花費 $c_{i,j}'$。

建一張圖，$S$ 向所有 $a_i>C$ 的點建 $(容量,費用)=(a_i-C,0)$ 的邊；所有 $a_j<C$ 的點向 $T$ 建 $(容量,費用)=(C-a_j,0)$ 的邊；所有 $a_i>C$ 的點向 $a_j<C$ 的點建 $(容量,費用)=(\infty,c_{i,j}')$ 的邊。

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

## [pB. 豬哥選總統](https://zerojudge.tw/ShowProblem?problemid=k990)

可以使用位元 dp，沒住人的格子以 $1$ 表示，在所處矩形右界的格子也以 $1$ 表示，轉移的時候只要看有沒有跟上一行的矩形對齊判斷是否要 $+1$。

可以做到 $O(n2^{2m})$。

## [pC. 人生遊戲](https://zerojudge.tw/ShowProblem?problemid=k991)

可以參考[康威生命遊戲](https://zh.wikipedia.org/zh-tw/%E5%BA%B7%E5%A8%81%E7%94%9F%E5%91%BD%E6%B8%B8%E6%88%8F)，發現有一種會移動的狀態叫滑翔機，經過實驗三關分別可以這樣構造：

  

## [pD. 送外賣2](https://zerojudge.tw/ShowProblem?problemid=k992)

直接讓最大的那條邊變 $5$ 倍，然後做最大生成樹，複雜度 $O(m\log(m))$。

## [pE. 合併排序](https://zerojudge.tw/ShowProblem?problemid=k993)

假設合併時左邊陣列大小 $x$，右邊陣列大小 $y$，排法共有 $C^{x+y}_x$ 種。

分成最大值在左邊與在右邊的情況，如果在左邊，那不會呼叫 cmp 的次數會是連續一段最大值的長度，假設是 $i$，那有 $C^{x+y-i-1}_{y-1}$ 種排法，期望值為 $\sum\limits_{i=1}^x (x+y-i)\times\dfrac{C^{x+y-i-1}_{y-1}}{C^{x+y}_x}=\frac{xy}{y+1}$，同理最大值在右邊的期望值為 $\frac{xy}{x+1}$。

令 $dp_n$ 為大小 $n$ 陣列的答案，那 $dp_n=dp_{\lfloor\frac{n}{2}\rfloor}+dp_{\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}$。