# Day 5 上機詳解

###### tags: `IONCAMP2019`

[TBA發大財](https://pc2.tfcis.org/dev/index.php/problem/view/71/)
---
* 把陣列排序一遍，由大到小拿K個。要注意$N$可能小於$K$。
時間$O(N\log N + K)$,
使用integer sorting $O(\max(a) + K + N)$

[艾梅洛閣下II世](https://pc2.tfcis.org/dev/index.php/problem/view/57/)
---

可以發現，每次應該要拿所有數字中，最小的兩個數字出來，要注意合成之後，新的大小也是要考慮的

* 80 % 使用 priority queue 放入資料，找最小值可以在 $O(n\log n)$ 的時間解決問題

注意題目給的序列是**已排序**的

考慮用 Priority Queue 的方法每次合成後，得到的刻印大小會是 **遞增** 的，因此，**如果不要把新得到的數字放回 Priority Queue，而是放入一個新陣列中(vector/deque)**，會得到一個遞增的序列。給定兩個**已排序的**陣列，取最小值可以 $O(1)$ 完成 (同合併排序法的合併步驟)，因此可以在 $O(n)$ 的時間解決題目。

[探窟專家](https://pc2.tfcis.org/dev/index.php/problem/view/58/)
---

選一個區域，使得平均越小越好。

最小值跟不是最小值的數字取平均，會比最小值還要大，所以就找最小值就好了。

[TBA's Coins](https://pc2.tfcis.org/dev/index.php/problem/view/70/)
---
假設硬幣種類為$K$(這裡是9種不包含折價券)
* 小測資：
因為$A_i$被$48000$整除，所以可以直接用硬幣問題的方法解決。
* 中測資：
我們可以枚舉折價卷使用的個數，從1, 2, 3,....，剩餘的金額就直接用硬幣問題解決即可。這樣最多要枚舉幾張呢？$\frac{B}{A}$即可。由於$A_i\geq 48000$，$\frac{B}{A}$最多48000。時間複雜度是$O(\frac{B}{A}QK)$，所以能在時限內解決這個問題。
* 大測資：
最後大測資由於$1 \leq A_i$，所以可以知道$O(\frac{B}{A}QK)$不能在時限內解決。我們可以分成兩種$Case$，第一種就是$A_i\geq 48000$，可以用中測資的做法解決。第二種$1 \leq A_i \leq 48000$，因為A x B = B x A。所以我們可以發現說當我們的折價券使用張數超過48000時，每48000張折價券都可以換成48000元的硬幣使用$A_i$個會來的更好。
所以基本上這題可以在$O(48000QK)$的時間內解決。

[我是要成為海賊王的男人](https://pc2.tfcis.org/dev/index.php/problem/view/95/)
---
把所有邊根據權重由小到大排序
從小到大檢查每個邊是不是原本就連通的
不是的話就加到答案裡面然後讓他們連通

[選數字3](https://pc2.tfcis.org/dev/index.php/problem/view/99/)
---
出處：107實驗中學學科能力競賽校內賽（我出的，原題$a[i]$可能$\leq 0$）

第一個子任務：
$N=1:a[1]$
$N=2:a[1]+a[2]$
$N=3:max(a[1]+a[2]+a[3],(a[1]+a[3])\times 2)$

第二個子任務：
枚舉所有子集合，可以很容易算出每個子集合的總和和組數。時間複雜度$O(2^N\times N)$。

第三個子任務：
定義狀態$d[i][j]=$考慮前$i$個數，$a[i]$**一定**要選，且目前所選的數共形成$j$組的最大總和。很重要的觀察是，不會有相鄰的兩個數都不選的情況，因為這樣可以多選擇其中一個，總和增加，但是組數不變。所以如果要選$a[i]$，上一個有選的數一定是$a[i-1]$或$a[i-2]$。分別討論：

1. 上一個有選的數是$a[i-1]$。多選$a[i]$之後，組數不變（$a[i]$跟$a[i-1]$屬於同一組），總和多了$a[i]$，得到轉移式$d[i][j]=d[i-1][j]+a[i]$。

2. 上一個有選的數是$a[i-2]$。多選$a[i]$之後，組數$+1$（$a[i-1]$不選，所以$a[i]$自己成為新的一組），總和多了$a[i]$，得到轉移式$d[i][j]=d[i-2][j-1]+a[i]$。

兩者取較大值。

如果$j+j-1>i$，組數過多，是不可能達到的狀態，不從它們轉移過來，避免影響答案（也可以預設成負無限大）。因為最後一個數選了一定比不選好，所以答案是$max(d[N][j]\times j|1\leq j\leq N)$。

當然，沒有一開始的觀察也可以解出這題，但是狀態就要額外紀錄$a[i]$要不要選。用上一個數$a[i-1]$是否要選來分解一個問題。這是一個多種狀態定義都能解出問題的例子。

定義狀態$d[i][j][0/1]=$考慮前$i$個數，$a[i]$一定不選/要選，且目前所選的數共形成$j$組的最大總和。

現在計算$d[i][j][0]$：

1. $a[i-1]$不選。總和不變，組數不變。$d[i][j][0]=d[i-1][j][0]$。

2. $a[i-1]$要選。總和不變，組數不變。$d[i][j][0]=d[i-1][j][1]$。

兩者取較大值。

現在計算$d[i][j][1]$：

1. $a[i-1]$不選。總和加上$a[i]$，組數$+1$。$d[i][j][1]=d[i-1][j-1][0]+a[i]$。

2. $a[i-1]$要選。總和加上$a[i]$，組數不變。$d[i][j][1]=d[i-1][j][1]+a[i]$。

兩者取較大值。

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

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

[新兵教育](https://pc2.tfcis.org/dev/index.php/problem/view/89/)
---

逆序數對的變形

一個**前面**元素的名次比**後面**元素的名次**大**$k$。
不難發現當$k=0$的時候就是逆序數對。

因為這題是要求名次，起手式先離散化一波。

除了從mergesort修改，也可以使用BIT解逆序數對(相關)題目：

LL inversion(int *arr, int n, int k = 0) {
    LL cnt = 0;
    for(int i = n-1; i >= 0; i--) {
        cnt += sum(arr[i]-k-1);  // [1, arr[i]-k-1] 前綴合
        add(arr[i], 1);
    }
    return cnt;
}

[達克妮絲的裝備](https://pc2.tfcis.org/dev/index.php/problem/view/64/)
---

這題需要的主要只有兩個技巧：

(1) 用 **bits** 表示一個集合 ( e.g. $5$的二進位是 $(101)$，所以可以用$5$代表$\{1,3\}$這個集合。 )
(2) DP

維護一個DP陣列 $DP[ i ][ j ]$ : 用剛好 $j$ 個配件湊出 $i$ 這個"部位集合"的方法數，且**任一個配件都不是多餘的**；而這樣的陣列大小是 $2^{K} * K$。

更新方法非常直觀：每拿到一個新配件，就去對 $2^{K} * K$ 種狀態做更新即可，詳細說明如下。

初始化 $DP[ 0 ][ 0 ] = 1$；接著每拿到一個配件$i$，若這個配件可以覆蓋的部位集合為$S_i$，則它能更新所有**不包含**$S_i$的DP狀態。

一個集合 $S$ 不包含 $S_i$ 若且唯若 $(S\ |\ S_i) \neq S$ ，對於所有不包含 $S_i$ 的集合 $S$ 做DP更新：

$DP[S\ |\ S_i][j] = DP[S\ |\ S_i][j] + DP[S][j-1]$

最後輸出最小的 $k$ 使得 $DP[ 2^{K}-1 ][ k ] \neq 0$ 即可，若不存在此 $k$ 則輸出 -1。

[反社會序列](https://pc2.tfcis.org/dev/index.php/problem/view/72/)
---
給定一個序列，多次詢問從一個區間$[l,r]$中取出最多$k$個元素，可以得到的最大和為何。

實作上可把所有負數設為0。所有詢問的$k$若大於$r-l+1$，則設為$r-l+1$。

- 子任務一($5\%$)：$N,Q\leq 500$
直接暴力將詢問的區間排序再計算答案，接著還原序列。時間複雜度$O(QN\log~N)$。

- 子任務二($10\%$)：$a_i\geq 0$且所有詢問的$k=N$
詢問的解即為區間所有元素的和，維護前綴和即可。$O(Q+N)$。

- 子任務三($13\%$)：所有詢問的$k=3$
線段樹維護各區間前三大的元素，時間複雜度$O((Q+N)\log~N)$。

- 子任務四($32\%$)：$N,Q\leq 10^4$
莫隊，移動指針時用Treap維護集合與和，更新答案時切出前k大就好。
時間複雜度$O((Q+N)\sqrt{N}\log~N)$。

- 子任務五($40\%$)：無限制
解法一：值域分塊
使用離線作法，先將所有詢問讀入。使用一個陣列$ans$維護所有詢問的答案。
將原序列由大到小排序後(記得紀錄其原本於序列的位置)，每$\sqrt{N}$個分成一塊。

每次拿出一塊所有的元素，前綴和維護當前這塊所有元素於原序列任意區間的和與元素數量；接著拜訪所有詢問，並用以下方法更新$ans$陣列與詢問的k：
- 如果當前詢問的區間的元素數量$< 詢問的k$，則將其對應的$ans$陣列加上這個區間的和，並將詢問的$k$減去區間元素的數量
- 如果當前詢問的區間的元素數量$\geq 詢問的k$，則暴力依序遍歷塊內的元素，若遍歷的元素於原序列的位置位於詢問的區間中，則更新$ans$陣列，並將詢問的$k$減少一，直到詢問的$k=0$
當所有的塊處理完時，所有的$ans$陣列也記錄完所有詢問的答案。

每次拿出一塊更新前綴和陣列，共有$N/\sqrt{N}=\sqrt{N}$塊，更新前綴和陣列需要$O(N)$，因次這部分時間複雜度為$O(N\sqrt{N})$。

每塊都會遍歷所有的詢問，共有$\sqrt{N}$塊與$Q$筆詢問；若更新時為第一種情況，時間複雜度為$O(1)$，這情況總時間複雜度為$O(Q\sqrt{N})$；若更新時為第二種情況，時間複雜度$O(\sqrt{N})$，而每筆詢問這情況只會發生一次，這情況總時間複雜度為$O(Q\sqrt{N})$。

因此，本做法時間複雜度為$O((N+Q)\sqrt{N})$。

解法二：持久化線段樹
本題其實與區間第k小類似。用類似的方法維護持久化線段樹，詢問時透過前綴和方式得到當前區間所形成的值域線段樹，節點維護區間元素數量與和，並在樹上二分搜來得到前$k$大個元素的和。

時間複雜度$O((N+Q)\log~N)$。

解法三：整體二分套BIT
使用離線做法，先將所有詢問讀入。
將原序列排序。
接著類似於解法二，所有詢問一起二分搜解，並用BIT取代持久化線段樹。

時間複雜度$O((N+Q)\log~^2N)$。

[智慧熱橋](https://pc2.tfcis.org/dev/index.php/problem/view/76/)
---
給你一個2-sat問題，問你要最少增加幾個條件才能讓這個2-sat無解，擬增加的條件不能有 $\neg$ 操作。

你會發現你增加的條件一定是 $a \lor a$ 這樣的形式，而且在沒有 $\neg a \lor \neg b$ 這樣格式的條件存在的話就會無解。

因此可以發現如果有解，最多只要增加兩個條件就行了。剩下的就是枚舉每個變數$x$加上 $x \lor x$ 的條件判斷有沒有解就行了。

[計算前綴](https://pc2.tfcis.org/dev/index.php/problem/view/68/)
---

把所有字串拿來蓋一顆 Trie ，在一次 dfs 中，窮舉前綴以及 LCP 是該前綴的的字串對

標程 DFS 內部實作

struct Trie {
  Trie* ch[26] = {0};
  long long cnt = 0;
  void insert(string &s, int i = 0) {
    if (i < s.size()) {
      if (not ch[s[i] - 'a']) ch[s[i] - 'a'] = new Trie();
      ch[s[i] - 'a']->insert(s, i + 1);
    }
    ++cnt;
  }
  long long dfs(long long dep = 0) {
    long long cross = 0, sum = 0;
    long long dp[26] = {0}, all = 0;
    for (int i = 0; i < 26; ++i) {
      if (ch[i]) dp[i] = ch[i]->cnt, sum += ch[i]->dfs(dep + 1);
      all += dp[i];
    }
    for (int i = 0; i < 26; ++i) cross += dp[i] * (all - dp[i]);
    long long leaf = cnt - all;
    return dep * dep * (cross + 2 * leaf * all + leaf * leaf) + sum;
  }
} root;

[最大面積三角形](https://pc2.tfcis.org/dev/index.php/problem/view/93/)
---

這是講義經典題目，網路有一堆模板可以用，包括講義也有

反正就先把凸包做出來，然後利用單調性來進行雙指標（旋轉卡尺）

[惠惠的おっぱい魔法](https://pc2.tfcis.org/dev/index.php/problem/view/63/)
---

因為數字很大，階乘不是太好處理的東西；但在這題有個明顯規律，就是 $N!$ 能被 $P$ 整除的次數每經過 $P$ 才會改變一次。

也就是說，計算 $0! * 1! * 2! ... N!$ 能被 $P$ 整除的次數，其實是在計算像是

$0+0+0+0....+1+1+1+1....+2+2+2+2....$ 這樣的東西。

知道這點之後，也許可以想出一個 $O(N/P)$ 的解，一步步加總得到答案；這個方法足以通過小測資，但對於大測資，我們需要更進一步的觀察。

剛剛的加總大家應該會想到用**梯形公式**去一次解決，再扣掉多算的部分；但對於任何 $P^K\ :\ K>1$，我們都會漏算 $K-1$ 次 (這部分不懂的話，最後一筆範例測資可以嘗試手算看看)，

所以對於 $P^1, P^2 ... P^r$ ，其中 $P^r$ 是剛剛好 $\leq N$ 的 $P$ 幕次，我們都要套用一次梯形公式，這樣能確保能加總到所有答案。

但這題有個陷阱：梯形公式需要除法 $(A*(A+1)/2)$，這個在模操作下是要極小心處理的東西；但由於我們的答案是上面的加總乘以**兩倍**，所以其實不需要任何除法。

複雜度： $O(\log_P N)$