CEOI 2016 Day 2
今天來繼續整理 CEOI 題目吧～
給你一個小寫英文字母組成的字串 $(1\le |S|\le 10^5)$，請你把每個字元換成 ( 或 )，使得 (1) 它會是一個合法的括弧匹配，以及 (2) 每一個對應的括弧配對，在原本字串中對應位置的英文字母相同。請輸出滿足條件字典順序最小的字串。
這題基本上是分而治之+Greedy+DP。對於一個子字串 $S_i…S_j$，我們去找最大的 $k\in (i, j]$，使得 $S_i…S_k$ 和 $S_{k+1}…S_j$ 分別可以用兩個合法括弧字串表示。這個 $k$ 要怎麼找呢？定義 $\DP(j, c)$ 為最大的 $k \le j$ 滿足 $S_{k+1}…S_j$ 是可以對應到合法括弧串而且 $S_k=c$。我們很驚訝地發現這東西可以利用動態規劃完美解決：令 $pos= \DP(j-1, S_j)$，我們可以依據 $S_{pos-1}\mathtt{==}c$ 來 $O(1)$ 判斷要給 $\DP(j, c)$ 什麼值。
某場程式解題比賽有 $N$ 個參賽者。這場比賽僅有一題，而這題包含了 $T$ 筆測試資料（編號從 $1$ 到 $T$），每一筆測資都有一個點數（Points）。命題委員想要把該題測資分成至多 $S$ 個子任務。
子任務們是這樣運作的：每一個測資必須屬於恰好一個子任務，而且每一個子任務至少要包含一個測資，而且必須包含編號連續的測資。若一個參賽者在同一個子任務中任何一筆測試資料回答不正確，那麼此參賽者將會在該子任務獲得 $0$ 分。若成功了，那麼此參賽者可以獲得所有測資的點數總和。
命題委員是邪惡的（笑），他們決定在比賽後再決定子任務的分佈。已知所有 $N$ 個參賽者執行 $T$ 筆測資是否成功，這個資訊被放在 Results[][] 這個二維陣列裡面。命題委員們想請你幫忙回答，對於所有的 $1\le K\le S$，在恰好有 $K$ 個子任務的情形下，讓所有參賽者總得分最低的子任務分配法是什麼。
- $1\le N\le 50$
- $1\le T\le 20000$
- $1\le S\le \min(50, T)$
顯然會有個簡單的 DP: $\DP(i, j)=$ 把前 $i$ 個測資恰好分成 $j$ 個子任務能夠得到的最低總分為何。對於每一個 $\DP(i, j)$，若我們往前考量最後一組子任務，其所佔測資筆數恰好為 $\Delta$，那麼我們可以得到：
這樣直接做下去的時間複雜度會是 $O(T^2S)$，從範圍限制看起來是拿不到滿分的。
注意到更新的 $cost(i-\Delta+1, i)$ 這個函數，他其實是計算「有多少個參賽者對於 $[i-\Delta+1, i]$ 這個範圍的測資全對」：所以可以寫成 $count(i-\Delta+1, i)\times points(i-\Delta+1, i)$。這時候，我們可以發現 $\DP(i, j)$ 與 $\DP(i+1, j)$ 之間的關聯：很多時候 $count(i-\Delta+1, i)$ 與 $count(i-\Delta+1, i+1)$ 的參賽者數量是相同的！
因此我們可以做出 $O(TSN)$ 複雜度的動態規劃（蛤）
給定以下條件，你想要構造一個有向圖：
- $N$ 個入度數為零的節點（稱為 input nodes），編號從 $1$ 到 $N$。
- $N$ 個出度數為零的節點（稱為 output nodes），編號從 $N+1$ 到 $2N$。
- $K$ 個中繼節點，編號從 $2N+1$ 到 $2N+K$。
- $M$ 條有向邊（$M\le M_{lim}$）
- 這個圖沒有圈。
- 對於任意一組 $(X, Y)$，若有一條路可以從 $X$ 走到 $Y$，那麼這條路必須是唯一的。
- 每一個節點被定義為「可以連到自己」
- 任何一個 input node 可以連到任何一個 output node
我們定義一個節點 $X$ 的 「$P$值」為：可以連到該點的 input nodes 總數 $IN_X$ 乘上可以連出到達的 output nodes 總數 $OUT_X$。請你構造一個圖使得所有節點的最大 $P$ 值不超過給定的 $P_{lim}$。
嗯，就，構造吧XD