# TPOJ Round #6 Editorial
###### tags: `OI`

底下題解有空的話會補上每題的靈感來源，沒空就算ㄌ
個人認為難度排序: A << F partial(83%) < E = C = F < B < D
雖然就實際結果來看好像不是這樣ww

---

然後對於rejudge真的非常抱歉QAQ
我的checker把output file 跟 answer file弄反了，以後會注意不要犯這種錯QQ

## pA. 子字串
這題的設定是簽到題，就不分subtask了。

直覺上找的字串 $t$ 要越短越好，實際上也是如此：可以說明只要解存在，則必存在一個長度為 $1$ 的解。

證明非常容易：如果長度為 $1$ 的都不是解，說明了 `a` 到 `z` 的所有字串都存在於這 $n$ 個字串中，那更長的字串自然就不會是解了。

所以只需要驗證長度為 $1$ 的字串即可。複雜度 $O(\sum |s_i|)$ 。
http://codepad.org/U2ZhFOV3
## pB. 音遊大師
### Subtask 1
只能夠切成一段，所以相當於從中選出 $n-m$ 的數字使得全距最小。
我們可以把數字排序後，選擇連續 $n-m$ 的數字個數字中全距最小的。時間複雜度 $O(n \lg n)$ 。
### Subtask 2
不能夠有任何失誤。這個 Subtask 有很多種作法，我只介紹其中一種。
令 $dp[i][j]$ 代表把前 $i$ 個數字切成 $j$ 段時，最小的答案可以是多少。轉移式如下:
$dp[i][j]=\min\limits_{k\leq i-1} \max(dp[k][j-1],f(k+1,i))$
其中 $f(x,y)$ 代表 $a_x$ 到 $a_y$ 間的全距。直接進行轉移是 $O(n^3)$ ，但是注意到當 $k$ 越小時，$dp[k][j-1]$ 越小，$f(k+1,i)$ 越大，因此可以用三分搜找到最佳轉移點。時間複雜度 $O(n^2 \lg n)$ 。
### Subtask 3
注意到當切成 $k$ 段的解存在時，切成 $k+1$ 段的解必然存在（可以想想看為什麼）。因此我們可以對答案二分搜，然後每次限定最大可接受的全距在 $ans'$ 時，最少必須要切成幾段才行。後面這個問題可以使用DP，但是最簡單的作法是 Greedy 由前而後取數字：當加入的數字不會使全距超過 $ans'$ 時，就取那個數字，否則就前面那些數字切成一段，新加的數字自己形成一段。時間複雜度 $O(n \lg n)$ 。

### Subtask 4
我們可以使用類似於 Subtask 2 中的 DP解，只是需要先預處理 $f(x,y)$ 的值。時間複雜度 $O(n^3)$ 或 $O(n^3 \lg n)$ 。

### Subtask 5
同樣採用類似 Subtask 2 中的 DP解，只是這次的問題變成如何有效率的計算 $f(x,y)$ 的值。方法有非常多，以下一樣只介紹其中一種。
注意到這相當於問最多可以選多少個數字使得全距不超過限制。我們可以維護一棵線段樹，當加上一個數字 $x$ 時，把 $[x-ans',x]$ 這個區間加 $1$ ，去除則減 $1$ 。整體時間複雜度 $O(n^2 \lg n)$ 。

### Subtask 6
使用類似於 Subtask 3 中的 二分搜+Greedy解，只是現在問題變成當全距限制為 $ans'$ 時，判斷能否去除 $m$ 個數字滿足條件。再加上Subtask 5 中線段樹的判斷方法，我們就可以在 $n \lg n$的時間內判斷 $ans'$ 可不可行了。時間複雜度 $O(n \lg^2 n)$ 。
http://codepad.org/ZMSm0fLJ

## pC. 三色牆
### Subtask 1
輸出 $\max(\lfloor \frac{m}{2} \rfloor \cdot n , \lfloor \frac{n}{2} \rfloor \cdot m)$ 。
### Subtask 2
枚舉四個點 $(x_1,y_1),(x_2,y_2),(x_3,y_3),(x_4,y_4)$ ，用前綴和看 $(x_1,y_1),(x_2,y_2)$ 能否形成紅色矩形，$(x_3,y_3),(x_4,y_4)$ 能否形成藍色矩形。注意兩種顏色的矩形不能重疊。時間複雜度 $O(n^4m^4)$ 。

### Subtask 3
我原本有設定一個解法的，但是我忘了QQ
其實 Subtask 2 常數小一點就有這個 Subtask了(X)

### Subtask 4&5&6
注意兩種顏色的矩形不能重疊，因此必有一條鉛直或水平線把兩個矩形分開。因此我們可以看在某條線之前/後 能形成的紅色/藍色矩形最大可以是多少，之後枚舉那條水平或鉛直線。接下來的差別只是找矩形的方法的不同而已。
如果找矩形的方式是枚舉兩個點的話，時間複雜度為 $O(n^2m^2)$ ；如果採用枚舉上下界並使用單調對列的話複雜度是 $O(nm^2)$ ；如果採用一般最大矩形的寫法(掃描以後加上單調對列)的話則是 $O(nm)$ 。
http://codepad.org/0lnVJad9

## pD. 排列 Again!
### Subtask 1
注意到每個 $x$ 最多只能使用 $1$ 次。因此對於每個 $i$ ，枚舉是否需要交換，再檢查 $a$ 是不是一個排列。 $O(2^n \cdot n)$
### Subtask 2
折半枚舉以後，再檢查兩邊是否能形成一個排列。檢查兩邊是否能形成一個排列有很多種方法，其中一種是把每個數字指定一個 hash 值，再檢查兩邊是否有 hash 值 XOR 起來是指定值。$O(2^{n/2} \cdot n)$
### Subtask 3
這個 Subtask 有多種作法，以下只介紹其中一種。
建一張二分圖，把左邊的 $i$ 號節點連到右邊的 $a_i$ 與 $b_i$ 號節點，則可以發現解存在的條件是這張二分圖存在完美匹配。如果使用匈牙利算法的話複雜度就會是 $O(n^2)$ 。
### Subtask 4
和 Subtask 3 一樣的做法，但是這次採用 flow 解二分圖匹配。如果使用 Dinic 之類的算法的話複雜度是 $O(n \sqrt{n})$ 。

### Subtask 5
這個 Subtask 也有非常多種作法，在賽中看到好幾種作法我都覺得還不錯，但是還沒認真研究，如果有空的話再慢慢補上來。
這裡就先介紹我原本設定的解法：建一張 $n$ 個節點的圖，其中 $a_i$ 和 $b_i$ 建邊。則可以發現，原題有解的充要條件是存在一種把邊定向的方法使得每個節點的入度為 $1$ 。容易發現，如果一個連通塊的點數和邊數不一樣，則原問題無解。否則這張圖是 [Pseudoforest](https://en.wikipedia.org/wiki/Pseudoforest) ，每一個連通塊都是一個 1-tree (水母圖)。一個 1-tree 很好定向，可以自己想想看怎麼定。

這題的另解，感謝 FoodSheep 的提供:
https://hackmd.io/@9Fd7v5ViQ5-5a0f5OAjJbA/SkJiS_P7P

http://codepad.org/qgU3noeY

## pE. 密室逃脫
### Subtask 1
有一個直覺的想法：當進到一個房間以後，就蒐集房間內所有的鑰匙，嘗試打開所有的門，如果能進到新的房間就再蒐集鑰匙。如果每次拿到新的鑰匙就遍歷一次所有房間的話是 $O((n+m)p)$ 。
### Subtask 2
圖是一條鏈，那我們可以從第一個節點開始，同樣蒐集路上所有的鑰匙，如果能用現在手上的鑰匙打開下一扇門的話就進去，否則到這間房間為止就是所有的答案。
### Subtask 3
圖是一個 Star graph，基本上也是和 Subtask 1 一樣的想法，只是要改成適用 Star Graph的寫法。
我們可以把每個房間除了 $1$ 號房間以外的依照與 $1$ 號房間之間的門的種類進行歸類，當拿到某一種類的鑰匙時，就遍歷那把鑰匙的門。注意不要枚舉到重複種類的鑰匙。
### Subtask 4
這個 Subtask 其實我沒想法(?)
只是開一個 Subtask 給不知道滿分解的人而已
### Subtask 5
基本上也是和 Subtask 1 一樣的想法，只是細節更多了。
因為不要枚舉到重複種類的鑰匙，所以當我們拿到一把鑰匙時，不是用這把鑰匙打開 **現有** 的門，而是打開 **所有** 能夠打開的門，也就是說把一條邊標記為合法。除此之外，當進到新的房間以後，還要對這些房間進行BFS，所以可以分別對鑰匙和房間各做一個 queue ，在上面BFS即可。
http://codepad.org/HH9sV00A

## pF. 哈希之術 Again!
### Subtask 1
由於 mod 很大，所以 hash 以後算出來的值就是原本的值。詢問一次整個字串的 hash 值，便能輕易回推原本的字串。
### Subtask 2
暴力枚舉所有長度為 $3$ 的字串，再分別詢問能形成的 $4$ 個 hash 值，比對這 $4$ 個 hash 值的異同。
### Subtask 3
注意到每個回傳的 hash 值都是 $S_1,\cdots,S_n$ 的線性組合。隨機給出 $n$ 個詢問以後，使用 $O(n^3)$ 解 $n$ 元聯立方程組。
### Subtask 4
想法同樣是解 $n$ 元聯立方程組，只是這次要用比較快速的方式。我們可以詢問:
$v=\{ 1,2,\cdots,n\}$
$v_1=\{ 1,3,\cdots,n\}$
$v_2=\{ 1,2,4,\cdots,n\}$
$v_3=\{ 1,2,3,5,\cdots,n\}$
...
$v_{n-1}=\{ 1,2,3,\cdots,n-2,n-1\}$
容易發現$\forall 1 \leq i \leq n-1$ $(x-1)S_i=(GetHash(v_i)-Gethash(v))$，之後再使用 $v$ 及 $S_1$ ~ $S_{n-1}$ 找到 $S_n$ 。
### Subtask 5
同樣是 Subtask 4 的作法，只是這次要先找到 $x$ 的值。
我們再詢問一個陣列 $u=\{ 1,4,5,\cdots, n\}$ 。則可以發現 $(x^2-1)S_1=(GetHash(u)-Gethash(v_2))=(x+1)(x-1)S_1$ 。再結合之前得到的 $(x-1)S_1$ 的值，就能順利得到 $x$ 了。之後再套 Subtask 4 的做法即可。
http://codepad.org/DdcXIXzZ