Day 2 上機詳解
===

###### tags:`IONCAMP2019`

[台灣記者基德](https://pc2.tfcis.org/dev/index.php/problem/view/59/)
---
1. 自定義struct，包含該黑人的名字及付的錢。

typedef struct{
    string name;
    int m;
}People;

3. 花$O(n)$紀錄輸入資料於`vector`中

int n,k;
vector<People> nig;
cin>>n>>k;//input
for(int i=0;i<n;i++){
    People tmp;
    cin>>tmp.name>>tmp.m;
    nig.push_back(tmp);
}

5. 再用`std::sort()`花$O(n \log n)$排序，並自定義排序的object

struct myclass {
    bool operator() (People i,People j) {
        return (i.m==j.m)? (i.name<j.name) : (i.m>j.m);
    }
} myobject;

std::sort (nig.begin(), nig.end(), myobject);

7. 最後再花$O(n)$數出第$k$大數字。

int previous;//record the previous one to avoid counting the same amount of money twice

for(int i=0;i<n;i++){ //output: count to k-th
    if(k==1&&previous!=nig[i].m){
        k--;
        cout<<nig[i].name;
        previous=nig[i].m;
    }
    else if(i==0){
        k--;
        previous=nig[i].m;
    }
    else if(previous==nig[i].m){
        if(k==0) cout<<'\n'<<nig[i].name;
    }
    else if(k<0) break;
    else{
        k--;
        previous=nig[i].m;
    }
}
cout<<'\n';

[為美好的扣釘獻上祝福](https://pc2.tfcis.org/dev/index.php/problem/view/91/)
---

- 發現單調性：
如果某個等級$k$可以打敗魔王，那等級$>k$也可以打敗魔王
所以我們可以對**等級**二分搜
等級下界：$1$，上界：$10^{10}$

- 檢查等級$k$時能不能打敗魔王：

1. 先確定自己的魔力夠不夠打敗魔王：攻擊幾次才能打敗魔王，總魔力值夠不夠？
2. 什麼時候要回血？
- 如果回血量 < 魔王攻擊：那就放棄回血吧，放了完了只是以更少的血量跟魔力面對魔王而已Orz
- 反正大法師沒有血量上限，那乾脆先一次把血量充肥一點再攻擊魔王
- 留足夠的魔力攻擊魔王($MP_{explosion} \times$必須攻擊幾次魔王)，剩下的魔力通通拿來回血

- 其他細節
注意Overflow

[選數字2](https://pc2.tfcis.org/dev/index.php/problem/view/46/)
---
出處：NCPC 2018 pA

$d[i]=$考慮$a[1]\cdots a[i]$的最大總和

所有考慮前$i$個數的選法($i\geq 3$)，可以分成兩類：

1. $a[i]$要選，此時$a[i-1]$和$a[i-2]$都不能選，但$a[i]$可以搭配$a[1]\cdots a[i-3]$的任一種選擇方案，此時最大總和是$d[i-3]+a[i]$。
2. $a[i]$不要選，此時最大總和是$d[i-1]$。

每一個合法的方案一定會剛好屬於其中一種，所以兩者取較大值就是答案。

邊界狀態是$d[0] = 0, d[1] = a[1], d[2] = max(a[1], a[2])$。

#include <iostream>
#include <algorithm>
using namespace std;
int n, a[100005], d[100005];
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    d[1] = a[1];
    d[2] = max(a[1], a[2]);
    for (int i = 3; i <= n; i++)
        d[i] = max(d[i - 3] + a[i], d[i - 1]);
    cout << d[n] << '\n';
}

[LCIS(最長共同遞增子序列)](https://pc2.tfcis.org/dev/index.php/problem/view/82/)
---
在第一層迴圈中用一個變數$k$紀錄目前的$max(d[i-1][l]|0\leq l < j, b[l]<a[i])+1$。

可以把$b[j]$換成$a[i]$，因為$k$有作用時$a[i]$一定等於$b[j]$。在$j$遞增時順便更新，原本的轉移式直接簡化成：

1. $a[i]\neq b[j]$，$d[i][j]=d[i-1][j]$。

2. $a[i] = b[j]$，$d[i][j]=k$。

#include <iostream>
#include <algorithm>
using namespace std;
int n, m, a[2019], b[2019], d[2019][2019], z = 0;
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= m; i++) cin >> b[i];
    for (int i = 1; i <= n; i++) {
        int k = 0;
        for (int j = 0; j <= m; j++) {
            if (b[j] < a[i]) k = max(k, d[i - 1][j] + 1);
            if (b[j] == a[i]) d[i][j] = k;
            else d[i][j] = d[i - 1][j];
        }
    }
    for (int i = 1; i <= m; i++) z = max(z, d[n][i]);
    cout << z << '\n';
}

[雙重背包問題](https://pc2.tfcis.org/dev/index.php/problem/view/87)
---
$d[i][j][k]=$只考慮前$i$個東西，且第一個背包總體積不超過$j$，第二個背包總體積不超過$k$的最大總價值

計算$d[i][j][k]$時，分三種情況討論：
1. 不選第$i$個物品，此時最佳解等於忽略這個物品，但體積上限不變的子問題最佳解，也就是$d[i-1][j][k]$。
2. 第$i$個物品放入第一個背包內，此時最佳解等於忽略這個物品，解決相對應的子問題之後再加入這個物品，也就是$d[i-1][j-a[i]][k]+b[i]$。
3. 第$i$個物品放入第二個背包內，此時最佳解等於忽略這個物品，解決相對應的子問題之後再加入這個物品，也就是$d[i-1][j][k-a[i]]+b[i]$。

#include <iostream>
#include <algorithm>
using namespace std;
int n, m, p, a[102], b[102], d[102][502][502];
int main() {
    cin >> n >> m >> p;
    for (int i = 1; i <= n; i++) cin >> a[i] >> b[i];
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            for (int k = 0; k <= p; k++) {
                d[i][j][k] = d[i - 1][j][k];
                if (j >= a[i]) d[i][j][k] = max(d[i][j][k], d[i - 1][j - a[i]][k] + b[i]);
                if (k >= a[i]) d[i][j][k] = max(d[i][j][k], d[i - 1][j][k - a[i]] + b[i]);
            }
        }
    }
    cout << d[n][m][p] << '\n';
}

[旅行大閘蟹問題](https://pc2.tfcis.org/dev/index.php/problem/view/66/)
----
範圍：進階DP

#### 小測資
這是一個最短路徑問題的特殊情況，因此答案可以套用最短路徑的作法求出。
直接DFS暴力搜索所有可能路徑, 或者套用Bellman-Ford演算法即可。
由於所有路徑都可寫作表格中點的子集的一個排列, 路徑不可能超出(N $\times$ M + 2)!種。

複雜度$O(NM \times (NM+2)!)$, 實際上可能因實作方法有差。
若使用Bellman-Ford則是$O(N^2M^3)$

#### 中測資
可以發現這有點像遞增子序列, 定$dp[r][c]$ = 由起點走到$(r, c)$的螃蟹旅程的最高舒適度, 則有
$dp[r][c] = \min\{dp[i][j] + p[r][c] : H[i][j] < H[r][c],\mbox{ }r+c=i+j\mbox{ or }r-c=i-j\mbox{ or }i=r\}$
使用$H[r][c]$的順序填表即可。
這個做法是$O(NM^2)$的，也可視作把最短路徑演算法換成DAG最長路。

#### 大測資
可以發現轉移非常的規律。
專注在橫向走法, 會發現同個$row$的$dp[r][c]$枚舉的轉移幾乎一樣, 且$H[r][c]$較大者可以使用所有$H[r][c]$較小者的轉移。
所以在填表過程中，維護一值$row\_best[i]$，代表$row$ $i$中有$H[i][j]<H[r][c]$的所有轉移中舒適度最高者，就可以$O(1)$轉移橫向走法的部分。
維護此陣列時，可發現當要計算的$H[r][c]$增加時，需要新加入資料結構中的值只有正好$<H[r][c]$、剛算好的那些人。
每個$(r, c)$只會加入結構一次，一次只需$O(1)$，維護時需特別注意$H[r][c]$可能有重複值。

沿著對角線方向$(1, 1)$走時，$r-c$ 必定維持不變。
同理可得，對角線走法可用$r+c$及$r-c+(M-1)$作為id紀錄最佳策略。
複雜度$O(NM)$

[完美序列世界！](https://pc2.tfcis.org/dev/index.php/problem/view/61/)
---
#### 小測資
由於數列中每個位置可以選或不選，一個數列$A$所有可能的子序列有$2^N$種。
由於$N$非常小，可以列舉所有可能的子序列，並驗證它是否為完美子序列。
給定一個子序列，我們可以如此判斷他是否為完美子序列：
> (1) 嘗試將每個$A[i]$放到子序列的尾巴。
> (2) 加入一個$A[i]$後，判斷此數列是否仍為$A$的子序列，若是則回傳false，否則復原數列並繼續試$A[i+1]$。
> (3) 通過所有檢查者為完美子序列

這樣個做法正確是因為，雖然完美子序列的條件可以加入任意數字，不過加入一個不存在$A$中的數字必定不可能形成$A$的子序列。
我們可以把所有枚舉出的子序列放到std::set中，讓它把重複的子序列挑掉。
做完這些事後，將set中所有子序列取出加總即為所求。
判斷是否為子序列為$O(N)$, 判斷是否為完美子序列為$O(N^2)$。
兩個子序列比較一次為$O(N)$，放入大小為$2^N$的std::set需要$O(log2^N)=O(N)$次比較。
總時間$O(N^2 \times 2^N)$。

#### 中測資
以下詳解完全不考慮各種邊界條件，細節請自行思考。
令$next(i, j) = i往後看第一次出現字元j$的位置 = $\min\{k : k>= i\mbox{ and }a[k]=j\}$。
令$dp1[i]=$後綴$A[i ... N]$的相異完美子序列個數，我們可以用「第一個被放在子序列的人」來區分相異的完美子序列。
很直覺地，以 $j$ 為開頭的完美子序列應該要把開頭的 $j$ 拿去配對$A[next(i, j)]$，剩下的部分形成$A[next(i, j) + 1 ... ]$的完美子序列。

可證明$dp1[i] = \sum \{dp1[next(i, j) + 1] ：0 \leq j < 2000 \}$。
具體證明方法與共同子序列相似。
首先開頭不同者不可能取出相同的完美子序列。
對於開頭相同且等於 $j$ 的完美子序列，去除開頭後，必須要形成後綴$next(i, j) + 1$的完美子序列。
且所有後綴$next(i, j) + 1$的完美子序列加上開頭 $j$ 都會成為後綴 $i$ 的完美子序列，因此這是個one to one and onto關係。
為何如此，請思考如何判斷一個數列$B$是否為$A$的子序列。事實上就是要在$A$中找出$B$的一組不交錯的匹配。

同理，令$dp2[i]=$後綴$i$的相異完美子序列個數，則枚舉開頭後，同樣是將對應後綴的總和加入dp，但是要考慮開頭對總和的貢獻，因此有：
$dp2[i] = \sum \{dp2[next(i, j) + 1] + j * dp1[next(i, j) + 1] ：0 \leq j < 2000 \}$。

複雜度取決於如何計算$next(i, j)$，有非常多種做法。
在此測資範圍下，只要掃過一次陣列，並且對於每個可能的 $j$，在第一次出現 $j$ 時轉移即可。
$O(N^2)$

### 大測資
觀察上面的轉移式，dp2[i]和dp2[i-1]的轉移只會有一個不同之處。
以 $i$ 遞減順序填表，算完$dp[i]$，移動到$i-1$時，$next$這個函數唯一的變化只有$next(i-1, a[i-1])$變成了$i-1$，其餘位置皆滿足$next(i-1, j)=next(i, j)$。
因此我們可以在填表時順便維護$next(i, j)$，每次 $i$ 移動時此函數只會有一處變動，並將變動的轉移修改掉即可。
$O(N)$。

由於測資數量非常多，需要特別注意初始化的時間複雜度。

[我叫做基德，是一名刑警](https://pc2.tfcis.org/dev/index.php/problem/view/69/)
---
#### 小測資
對於每個組織，枚舉所有可能包住他的連續區間，暴力計算區間內兩兩相差絕對值，合法者取最大。

#### 中測資
「任兩者相差絕對值的最大值」必發生在「集合中的最大值減最小值」。
令$RMQ(i, j)=max\{a_k:i\leq k \leq j\}$，也就是區間最大值。
則有$RMQ(i, j) = max(a_i, RMQ(i + 1, j))$。
這個轉移是$O(1)$的，我們可以預先把所有可能的區間最大最小值全部算出。

蓋住一點的最長區間必定是該區間左界的最長區間。
所以枚舉左界，對於每個左界，再枚舉所有可能的右界，由於最大最小值已算好，我們可以$O(1)$算出枚舉出的區間是否合法。

知道每個左界的最大右界後，使用掃描線即可求出答案。
由於$N$真的蠻小的，也不一定要掃描線。
$O(N^2)$

#### 大測資
想像以 $i$ 遞減的順序枚舉左界，並且對於每個右界 $j$ 記錄$RMQ(i, j)$。
在 $i$ 給定的情形下，$RMQ(i, j)$這個函數對 $j$ 會是個遞增的函數(非嚴格)。
因為有$RMQ(i, j) = max(a_i, RMQ(i + 1, j))$，當左界從$i+1$退後到$i$時，所有的$RMQ(i + 1, j)$只要跟$a[i]$取最大值即可變化為$RMQ(i, j)$，但是這個做法遠遠超出時限。

我們可以用一個stack依 $j$ 順序紀錄$RMQ(i, j)$產生的變化的 $j$。
由於 $j$ 增加時範圍增加，$RMQ(i, j)$對於 $j$ 必定遞增，產生變化的$A[j]$必定隨著 $j$ 增加越來越大，可知stack越底下的值會越大。
當所有$RMQ(i+1, j)$要跟一值$A[i]$取最大值時，只要將stack top那些$<A[i]$的人pop掉即可，由於$A[i]$是第一個變化點，我們將它放進stack。

所有可能的區間最大值可以在$O(N)$內維護，雖然不可能全部列舉，但是中途調用任何一值只需要二分搜索(若要二分搜索，則stack需以vector實作)，最小值同理。

$RMQ\_max(i, j)-RMQ\_min(i, j)$的變化並不規律，不過我們可以分別維護max和min，由剛剛的過程中可知，$max-min$ 的變化可以由$O(N)$個區間加值完成。

將原條件移項得$RMQ\_max(i, j) - RMQ\_min(i, j) - j \leq -i - 1$
給定$i$，對每個 $j$，使用線段樹維護$RMQ\_max(i, j) - RMQ\_min(i, j) - j$，並在樹上二分搜索$\geq -i-1$的最大位置就可知道每個左界的最大右界，知道後即可掃描線。
$O(NlogN)$

[怪盜基德，參上！](https://pc2.tfcis.org/dev/index.php/problem/view/86/)
---
#### 小測資
把物品通通讀進來，轉換成0-1背包。
$O(NW)$

#### 大測資
同一種的物品價值越大越好，應該要按照價值排序。
令$dp[i][j] =$前 $i$ 種物品拿重量總和 $j$ 的最大價值。
$=max\{dp[i-1][j-k \times w_i] + v1+v2+...+v_k\}$，$v_x$為第$i$類物品中第$x$大的。
可發現，對$w_i$不同餘的 $j$ 之間不會有轉移關係。

把模 $w_i$ 同餘的 $j$ 一起處理，當表格的 $j$ 前進$w_i$時，每個可能的轉移重量$b = j-k \times w_i$ 都會多拿新的一個物品，且 $b$ 越大者多拿的物品價值越高。
假設最佳解發生在$b=b^*$，可知比 $b^*$ 小的轉移重量 $b$ 若未成為最佳解，在 $j$ 增加時成長又比最佳解差，不會再成為最佳解，最佳轉移位置的 $b^*$ 必定隨著 $j$遞增。

此外，雖然會有新增和刪除的轉移，但變動的位置並沒有跟此結論衝突，最佳解仍然遞增。
所以可以D&C優化。
$O(N+KWlogW)$