TPOJ Round #4 Editorial
===
各題題目作者：
pA: Problem Idea: CatAgain, Statement: CatAgain
pB: Problem Idea: CatAgain, Statement: CatAgain
pC: Problem Idea: CatAgain, Statement: CatAgain
pD: Problem Idea: HNO2, Statement: CatAgain
pE: Problem Idea: HNO2, Statement: CatAgain
pF: Problem Idea: HNO2, Statement: CatAgain
pG: Problem Idea: HNO2, Statement: CatAgain
## pA. Hacked by the Red Box
> 題目會給$10$個相異的二進位碼，分別代表數字$0 \sim 9$加密後的結果。現在給定一個長度$50$、由$0、1$組成的字串，請你把它還原成$5$位的阿拉伯數字字串。(測資保證有唯一解。)

### Solution
這題限制實在過於寬鬆，題目又保證唯一解、加密後的二進位碼皆相異，所以直接把$10$個二進位碼存下來，暴力搜索即可。

## pB. 金閃閃與他打結的天之鎖
> 題目給了你一棵樹，要求最小高度。

###### 天啊演算法筆記竟然有答案QQQ

### 盲點

可能會有人把它當成樹重心做?

### Solution 1 dfs(演算法筆記的)
一棵無根樹的直徑，恰好是相離最遠的兩個點的距離，所以求出直徑的中點即可。

### Solution 2 greedy(原解)
最外圍的節點(入度為一)，可以直觀得知不會是我們所要的答案，故可以直節拔除。
如此拔到剩下$1、2$個節點時，所剩即為所求。

### Solution 3(暴力)
其實這題 $n$ 也不算很大，枚舉每個節點就是了。

>[name=CatAgain]真假QQQQ 不早說QQQ 該不會有人真的這樣做吧?QQQ
>[name=HNO2]其實我一開始把 $n$ 調小的目的就在這(?)
>不然scoreboard會更難看(?)
>[name=CatAgain]大家都正解OwOb
## pC. 八九寺的背包有十五公斤重
>有$n$種物品，每個有其重量$m$，然而，取到的第 $k$ 個某物品會變$p^{k-1}$倍重，求背包可裝的最大價值。

### Solution
首先，如果$p=1$，那就是水水的背包了。

所以接下來考慮$p \neq 1$的情況。
##### 比賽中也看到很多種寫法，這裡就不全放了。
把每個物品的每種重量分開做(物品重量不可能超過背包負重，故就算列出每種重量，也不會太多)，變成01背包。其中，我們甚至可以發現，不用強迫小倍率的物品先被拿，因為兩者價值相同但小倍率的比較輕，所以一定比較優。

## pD. 學徒
>有一個長度為 $n$ ($1 \leq n \leq 3\cdot 10^5$) 的序列，有以下兩種操作可以執行任意多次：
(1) 選擇兩個整數 $i,j$ 滿足 $1 \leq l < r \leq n, 0 < a_l$， $a_i:=a_i-1, a_j:=a_j+1$，花費是 $0$ 。
(2) 選擇一個整數 $i$ 滿足 $1 \leq i \leq n$，$a_i:=a_i+1$，花費是 $1$ 。
求讓整個序列元素都一樣的最小花費。

### Solution 1
注意到如果需要動用到第二種操作，那選擇 $i=1$ 永遠是最佳解。顯然，如果選擇 $j>1$ ，那一開始先對 $i=1$ 動用第二個操作，之後再動用第一種操作移到 $j$ 即可。

然後再注意到一件事：假設操作最後每疊有 $k$ 個盤子（不一定是最佳解），那 $k+1$ 也是可以達到的狀態。於是我們可以對 $k$ 進行二分搜，假設一開始有 $m$ 個盤子，那對 $i=1$ 進行第二個操作 $nk-m$ 次即可，答案也就是 $nk-m$。

至於給定一個 $x$，要怎麼判斷 $k=x$ 是可以達到的狀態呢？既然你已經知道最終狀態是每疊都有 $x$ 個盤子，那就先對 $i=1$ 進行第二個操作 $nx-m$ 次，然後 $\forall$ $1 \leq i \leq n-1$ ，把多餘的盤子移到 $i+1$ ，如果遇到一個時候盤子不夠就是不行，否則就可以。時間複雜度：$O(n\lg C)$。

### Solution 2
注意到對於原序列的每個後綴，盤子數量只增不減。同樣假設操作最後每疊有 $k$ 個盤子（不一定是最佳解），令 $s_k = \sum\limits_{i=k}^n a_i$，那答案至少要是 $x =\max\limits_{1 \leq i \leq n} \lceil \frac{s_i}{n-i+1} \rceil$ 。

事實上這個答案就是最佳解。構造解的方法可以仿照 Solution 1 中的解法：先對 $i=1$ 進行第二個操作 $nx-m$ 次，然後由後至前考慮每個元素，然後如果有少的盤子，把前面隨便一個盤子移過來就可以了。因為$\forall$ $1 \leq i \leq n$ , $s_i \geq (n-i+1)x$ ，因此不會發生盤子短缺的問題。時間複雜度：$O(n)$。

## pE. 夏日大矩陣
>給定一個 $n$ ，構造一個滿足下列條件的矩陣：
(1) 每個元素都介於 $1$ 到 $n$ 之間。
(2) 對於每個介於 $1$ ~ $n$ 的正整數 $i$ ，如果 $i$ 在矩陣內出現至少一次，那每個 $i \times i$ 的子矩陣都含有至少一個 $i$。
(3) 矩陣內的元素種類需最大化。

### Solution
這題是構造題當然講開來就不值錢了(X

一件很神奇的事：如果題目改成對於每個介於 $1$ ~ $n$ 的正整數 $i$ ，如果 $i$ 在矩陣內出現至少一次，那每個 $2^k \times 2^k$ 的子矩陣都含有至少一個 $i$，其中 $k$ 為最大的整數滿足 $2^k \leq i$，相信很多人都會做了，但是把條件放寬反而變難題了XDD

我的構造方法：對於每個 $i$，令 $k$ 為最大的整數滿足 $2^k|i$ ，那 $a_{i,j}=2^{k+1}+((j-1)\mod2^{k+1} )$ (1-indexed)。就這樣XD

## pF. 公平
>給定一個序列，把這個序列切成 $k$ 段，求每段各自加總後這 $k$ 段總和標準差最小值。對於每個 $1 \leq k \leq n$ 分別求答案。
>
小故事：這題原本的題目更複雜，雖然有 $O(n^3)$ 的解法但是麻煩到我也不想刻，就簡化成現在的樣子，結果發現跟大陸出的某題撞題了QAQ ([連結](https://www.cnblogs.com/mlystdcall/p/6743830.html))

### Solution
標準差這個東西看來很麻煩，但是如果你有好好上數學課的話這題應該就好解多了(?)

$\sigma = \sqrt{\frac{1}{m} \sum\limits_{i=1}^m (x_i - \mu)^2}=\sqrt{\frac{1}{m} \sum\limits_{i=1}^m x_i^2 - \mu^2}$

$\mu$ 可以很容易的求出來，所以現在問題變成給定一個 $k$ ，把序列切成 $k$ 段使得每段總和平方最小。

某些人應該就知道接下來怎麼做了(?)，如果還不瞭解可以繼續往下看。

我們嘗試使用DP。令 $p_i$ 代表前 $i$ 項的總和，$dp[i][j]$ 代表把前 $i$ 項切成 $j$ 段平方和的最小值。有一個很顯然的DP轉移式：

$dp[i][j]=\max\limits_{0 \leq k < i} dp[k][j-1]+(p_i-p_j)^2$

直接算複雜度是 $O(n^3)$ ，這樣很顯然是不夠的。但是我們可以把DP式變形：

$dp[i][j]=\max\limits_{0 \leq k < i} dp[k][j-1]+(p_i-p_k)^2$
$=p_i^2+\max\limits_{0 \leq k < i} (-2p_kp_i+p_k^2+dp[k][j-1])$

這裡就是一個標準的CHT(~~中華電信~~斜率優化)模型了，時間複雜度 $O(n^2)$ 。想學斜率優化以下提供教學連結：[連結](https://codeforces.com/blog/entry/63823)

## pG. 上車!
>有一台公車，這台公車從車站 $1$ 開到車站 $n$，有載客量限制 $k$。有 $m$ 個人要搭公車，第 $i$ 個人要從車站 $a_i$ 搭到車站 $b_i$。每個乘客可以選擇載或不載。求最大載客量(最大載客量定義請見原題)。
>
小故事：出題者是每天搭公車(精確來說是客運)上學的，每次司機提高載客量的方式都是greedy，但是就會發現有時候反而到某個時間點車上空空如也，就想到這題了><
然後發現又撞題了QQ ([連結](https://blog.csdn.net/u013480600/article/details/39051023))
### Solution
這題是min-cost flow的題目喔~

建模：
* $n$ 個節點
* $\forall$ $1 \leq i \leq n-1$ , $i$ 到 $i+1$ 容量 $inf$ ，費用 $0$
* $\forall$ $1 \leq i \leq m$ , $a_i$ 到 $b_i$ 容量 $1$ ，費用為 $a_i$ 到 $b_i$ 的距離的相反數。

節點 $1$ 到 $n$ 的 min-cost flow 變正號再除以 $1$ 到 $n$ 的距離就是答案了。我好像也不知道要說什麼了XD