CSES Additional Problems Solution

前言

應該很多人都知道 CSES problemset 吧，裡面基本上就是經典題大雜燴。而 additional problem 是裡面的最後一章，也是很多人容易遺忘的章節。

個人認為前面章節的題目都算是對應章節的裸題，主要只是讓你知道這類題目最基本的樣子而已。所謂經典技巧當然不是只有這些裸題，有更多經典技巧是只能靠刷題來累積的，additional problem 裡就直接幫你整理出了一大堆，讓你不用從茫茫題庫中尋找，還不會被大主題直接爆雷。除了經典技巧外，這裡一些有趣的梗題與不有趣的構造題，個人還蠻喜歡的。

那這麼好的題單卻查不到一份完整的題解（註：在 2021 年，我不確定現在有沒有了），真是太讓我難過了，所以我就開始寫這篇題解。

順便先提一點，additional problem 的題目不一定會比前面的章節難，裡面也有許多簡單題，可以不用害怕，從解題人數多的題目開始下手，也不用把前面都刷完再來寫這部份。

推題

開始之前先推些個人覺得很棒的題 > <

Movie Festival Queries
Stack Weights
List of Sums
Binary Subsequences
Programmers and Artists
Removing Digits II
Counting Bishops
Missing Coin Sum Queries
Creating Offices
Permutations II

1087 - Shortest Subsequence

連結

題解

一個直觀的 greedy 法就是從左掃到右，沿途計算目前四種字元的數量
若四種字元的出現過了，代表答案長度一定需要 +1，否則就會出現 subsequence
所以就把當前跑到的字元加到答案裡，並將數量歸零
跑完後要記得加上一個沒出現過的字元

1146 - Counting Bits

連結

題解

先分別計算第 0 個 bit、第 1 個 bit、… 的答案，再加起來就好
觀察一下可以發現第 $i$ 個 bit 每 $2^{i + 1}$ 個數會循環，且每個循環節前 $2^i$ 個數會是 0，其他會是 1
所以對每個 bit 直接算出循環的數量，再加一加就能得出答案了

1670 - Swap Game

連結

題解

遊戲最多只有 9! 種狀態，所以就蓋一張 9! 個點的新圖，將每種能互相到達的狀態用一條邊連接，然後再跑一遍 bfs 即可

小細節是要如何快速把一個狀態轉成一個數字，如果用 map 存可能會因為常數太肥而吃 TLE，這裡可以使用類似 hash 的方式，若這個狀態為字典序第 $k$ 大的狀態，那就把它的編號定為 $k$。編號加密與解密可以在 $O(9)$ 的時間內做完。

1134 - Prüfer Code

連結

題解

首先一個顯然的性質：沒被列在當前 Prüfer Code 裡的點一定是葉子
所以做法其實很單純，跑過一次陣列，每次挑出一個 index 最小的葉子跟陣列的點連邊
若連邊後該點已經不在 Prüfer Code 裡了就能夠將它視為葉子
整個過程可以用一個 priority queue 處理

1756 - Acyclic Graph Edges

連結

題解

把編號小的指到邊號大的，出來的圖就一定無環

2177 - Strongly Connected Edges

連結

題解

結論

1. 圖不連通或是圖上有橋，則無解
2. 否則蓋一棵 dfs 樹，把樹邊的方向定為 parent to child，回邊訂為 child to parent，這樣一定是對的

證明

有橋無解我覺得算 trivial，就不提了 =w=
圖上沒有橋 -> dfs 樹每一條樹邊一定會被一條回邊蓋到 -> 必定可以從一個點走到根
走到根之後就能直接經由樹邊走到所有點了

2179 - Even Outdegree Edges

連結

題解

結論：若有一個連通塊的邊數為奇數就無解，否則一定有解。

證明：首先因為一個連通塊的 out degree 和一定跟該連通塊的邊數相同，所以若邊數為奇數顯然無法讓該連通塊所有點的 out degree 皆為偶數。

而再來對於偶數的 case，我們用構造來證明。先只考慮一個連通塊且樹的 case，首先先隨便抓一個點當根開始 dfs，令 dfs(v) 會將子樹 $v$ 的所有點（但不包含 $v$）變偶出度，且會回傳 $v$ 的出度是奇數還是偶數。

這樣一來，對於一個點 $v$，它的兒子 $u$ 會有兩種 case：

1. dfs(u) 是 1，就將邊從 $u$ 指向 $v$
2. dfs(u) 是 0，就將邊從 $v$ 指向 $u$

這樣就可以讓兒子 $u$ 的出度變成偶數。

而因為整棵樹的邊數為偶數，所以最後根的 dfs 回傳值一定是 $0$，也就代表整個構造是正確的。

再來考慮一般圖的 case，會發現前面的方法還是可行的，只要將回邊的方向全部定為 parent to child 即可，這樣就不會動到該點子樹的奇偶性

2422 - Multiplication Table

連結

題解

對答案二分搜，$\leq m$ 的數量為：

$\sum\limits_{i = 1}^{n}{\min(n, \lfloor \frac{m}{i} \rfloor)}$

直接算就好

1142 - Advertisement

連結

題解

經典題，叫做最大矩形覆蓋的樣子(?
先計算出 $l_i$ 代表從最大的 index $j$ s.t. $h_j < h_i$
再算出 $r_i$ 代表最小的 index $j$ s.t. $h_i > h_j$
這個可以用 stack 做單調隊列算出來，這裡講一下建出 $l$ 的做法：
首先我們觀察到若 $j < i, h_j \geq h_i$，則 $j$ 一定不會是之後的答案（因為 $j$ 會先被 $i$ 擋掉）
所以我們可以用一個容器存下還有可能作為答案的 index
每當加入一個數，就看它可以讓哪些位置不再作為答案（$h_j \geq h_i$ 的點），把它一個一個移除掉
結束之後就直接取在容器中最大的 $h$ 值，它就會是我們要的 $l_i$ 了

注意這整個過程容器需要的操作：

1. 找出在容器中的數字中，最大的 $h$ 值
2. 加入一個數

注意到加入的數字的 $h$ 值必會比當前在容器中所有數字的 $h$ 值大，所以只需要用一個 stack
過程中維護出 top 作為當前容器的最大值即可

至於陣列 $r$ 想法跟 $l$ 類似，就留給讀者自行思考吧~

算完之後答案會是 $\max\limits_{i = 1}^{n}{h_i \cdot (r_i - l_i)}$

怕我講的不太清楚，順便附上建造 $l$ 陣列的code：

vector <int> l(n);
stack <int> stk; // store index, not height
for (int i = 0; i < n; ++i) {
    while (!stk.empty() && h[stk.top()] >= h[i]) {
        stk.pop();
    }
    l[i] = stk.empty() ? i : stk.top();
    stk.push(i);
}

2186 - Special Substrings

連結

題解

先幫每個出現的字母定義一個 hash 值吧
須滿足每個字母的 hash 值總和為 0

這樣一來問題就轉換成有幾個區間和為 0
套前綴和後變成問有幾對數字相同，可以直接用一個 map 做完

非 hash 作法沒多想，不過我翻每個人的 code 也幾乎都是 hash 就是了 =w=

2229 - Permutation Inversions

連結

題解

$dp_{n, k}$ 代表長度為 $n$、有 $k$ 個 inversion 的 permutation 數量
則轉移式可考慮窮舉 $n$ 所在的位置：

$dp_{n, k} = \sum\limits_{i = 0}^{n - 1}{dp_{n - 1, k - i}}$

其中 $i$ 為增加的 inversion 數量

一段區間和，可用前綴和加速，複雜度 $\mathcal{O}(nk)$

1655 - Maximum Xor Subarray

連結

題解

首先定義 $pre_i$ 代表前 $i$ 項 xor 的和，則答案等於 $pre_r \oplus pre_l$ 的最大值

首先先把所有前綴值建一棵 0-1 trie
接下來要 query 一個數跟 trie 上所有數的最大 xor 值
由於二進位的性質，若可以先讓最高位變成 1 一定會較好
所以可以在那棵 trie 上尋訪，若原數該 bit 為 0，就優先選擇該 bit 為 1 的點，反之亦然
之後取全部的最大值即可

1664 - Movie Festival Queries

連結

題解

來考慮一下倍增吧
$dp_{i, j}$ 代表從時間 $i$ 開始，看 $2^j$ 個movie的最短結束時間
倍增的轉移：$dp_{i, j} = dp_{dp_{i, j - 1}, j - 1}$

之後每次 query 就從最大的 bit 開始看，看跳完會不會超過限制
如果不會超過就更新答案即可

1697 - Chess Tournament

連結

題解

greedy 法：每次挑選度最大的點，設度為 $d$，就把他跟當前度前 $d$ 大的點連邊
若連不完就代表 IMPOSSIBLE

證明 from tmt514

1702 - Tree Traversals

連結

題解

preorder: 根 - 左子樹 - 右子樹
inorder: 左子樹 - 根 - 右子樹
postorder: 左子樹 - 右子樹 - 根

做法就是：

1. preorder 的開頭是根，在 inorder 找到根所在的位置
2. 現在知道左子樹在 preorder 和 inorder 的區間了，所以遞迴下去
3. 同樣道理，遞迴右子樹的區間
4. 輸出根

1704 - Network Renovation

連結

題解

結論

令葉子數量為 $m$，則答案為 $\lceil \frac{m}{2} \rceil$
連邊的方法為將葉子按照以不為葉子的點為根做 dfs 的時間戳記排序好，將第 $i$ 個葉子連到第 $\lfloor \frac{m}{2} \rfloor + i$ 個葉子
若 $m$ 為奇數，再將第 $m$ 個葉子連到第 $1$ 個葉子即可

證明

首先，由於每一條邊最多只會讓兩個葉子滿足條件，所以答案會有下界為 $\lceil \frac{m}{2} \rceil$
接下來就只要證明這樣的連邊方法是好的

首先，對於每一條邊 $(u, v)$，假設 $u$ 為深度較淺的點，我們可以將葉子分成 $A, B, C$ 三類：

• 集合 $A$ 存時間戳記在 $v$ 之前的葉子
• 集合 $B$ 存在 $v$ 子樹底下的葉子
• 集合 $C$ 存時間戳記在 $v$ 之後，但不在 $B$ 的葉子

接著，我們想要證明若 $|A| > 0$ 或 $|C| > 0$，則至少有一條從 $A$ 到 $B$ 的邊或從 $B$ 到 $C$ 的邊。

WLOG, $|A| > 0$
定義 $a_0, b_0$ 為第一個 $A$ 的點，第一個 $B$ 的點，注意到 $|B| > 0$ 所以 $b_0$ 一定存在。
則以下分為三種 case:

1. $a_0$ 連到集合 $A$ 的點，則與 $b_0$ 連邊的點必屬於 $A$ 集合
2. $a_0$ 連到集合 $B$ 的點
3. $a_0$ 連到集合 $C$ 的點，則與 $b_0$ 連邊的點必屬於 $C$ 集合

而因為我們拿非葉子的點當根，$|A|, |C|$ 一定有一個會非零，也就代表每一條樹邊一定會被一條新建的邊覆蓋。

1707 - Graph Girth

連結

題解

對於每個點，我們計算出經過他的最小環，這樣再把全部取最小值即可
而求出最小環的方法就是跑一次 bfs，若遇到已經跑過的點就代表環產生，就直接更新最小值
這個做法的複雜度是好的原因是在本題的限制下，$\mathcal{O}(n(n + m))$ 不會爆

順便提一個最常見的假解，因為我自己也被坑過 XD

作法：從一個點開始做 dfs 樹，對於每一條回邊 $u$ 到 $v$，將答案和 $dep_u - dep_v + 1$ 取最小值，其中 $dep_i$ 為 $i$ 的深度

hack test:

假設以 1 為根，dfs tree 為 1 - 2 - 3 - 4 - 5
那這樣最小環會是 3，然後假解計算出來會是 4

1740 - Intersection Points

連結

題解

經典的 sweepline + 資結題
假設有一條垂直的直線，他會從左邊跑到右邊(?
那在這過程中可能會有三種情況

1. 遇到一個平行線段的起始點
2. 遇到一個平行線段的終點
3. 遇到一個垂直線段

其中當遇到 3. 的時候，會需要詢問當前的一段區間有幾條線段經過
而遇到 1. 2. 的時候，會需要將一個點加值或減值
而這些操作用一棵 BIT 可以做完

2214 - Inverse Inversions

連結

題解

首先，先定義一開始的陣列 $a_i = i$
注意到我們每次將一對 $a_i < a_{i + 1}$ 交換的話，inversion 數量會加 1
這樣可以得到一個暴力解：先將 $n$ 慢慢往前搬一格，直到沒辦法搬就換成把 $n - 1$ 往前搬，以此類推
因為每次往搬一格可以讓 inversion 數量加 1，所以一定會有一個時刻剛好有 $k$ 個 inversion，到這時就可以停止了。

然而這樣複雜度會是 $O(k)$，但優化方法也很簡單：只要事先算出每一個數字可以往前搬幾步多少就好了。

2215 - Monotone Subsequences

連結

題解

結論：$n > k^2$ 無解，否則可以先構出：
$k, 2k, 3k, \ldots, k^2, k - 1, 2k - 1, \ldots, k^2 - 1, k - 2, 2k - 2, \ldots, k^2 - 2, \ldots, 1, k + 1, \ldots, k^2 - k + 1$

再將 $> n$ 的數刪掉即可

證明：假設存在一個長度 $k^2 + 1$ 的排列 $p$，它的 lis 與 lds 長度皆最多為 $k$
(註：lis -> 最長遞增子序列 lds -> 最長遞減子序列)
對於每個位置 $i$，紀錄 $a_i$ 代表以 $i$ 為結尾的最長 lis 長度，$b_i$ 代表以 $i$ 為開頭的最長lds長度
那由於 $\forall i, 1 \leq a_i, b_i \leq k$
由鴿籠原理得知必存在兩數 $i, j$ 使 $a_i = a_j, b_i = b_j$

那接著分一下case：

1. $p_i < p_j$：
   此時 $a_i = a_j$ 顯然矛盾

2. $p_i > p_j$：
   此時 $b_i = b_j$ 顯然矛盾

故假設錯誤

1743 - String Reorder

連結

題解

首先先講一個顯然的結論，一個長度為 $n$ 的字串可以被 reorder 的條件為：
出現最多次的字母數量 $\leq \lceil \frac{n}{2} \rceil$

有了這個就可以導出之後的 greedy 策略：
每一次都選擇放置之後剩下的字元還能 reorder 的最小字母即可

2425 - Stack Weights

連結

題解

首先先講一個結論：
定義 $sufl_i$ 為放置在左邊且編號 $\geq i$ 的數量，$sufr_i$ 為放置在右邊且編號 $\geq i$ 的數量
則若左邊的重量確定小於右邊須滿足：
$\forall i, sufl_i \leq sufr_i$

原因：要是存在 $k$ 滿足 $sufl_k > sufr_k$，則將編號 $< k$ 的重量訂為 $i$，編號 $\geq k$ 的重量訂為 $\infty + i$ 即會使左邊較重

這樣就導出一個做法：
若是我們計算出 $c_i = sufl_i - sufr_i$，則

1. $\forall i, c_i \leq 0$，則代表右邊較重
2. $\forall i, c_i \geq 0$，則代表左邊較重
3. 無法分辨

所以就開一棵存取最大值和最小值的線段樹，放入一個硬幣就相當於對一個前綴 +1 或是 -1
之後就可以用全域的最大值和最小值判斷大小關係

1747 - Pyramid Array

連結

題解

可以發現最小的數字一定會出現最左邊或是最右邊
那把這個數字拔掉之後，剩下的數字中的最小值也會在最左邊或最右邊

所以這就導出一個做法：

1. 將數字從小到大看
2. 對於當前的數字，計算出他左邊的數量和右邊的數量
3. 取兩者最小值，並把該數從陣列中刪除

而對在位置 $i$ 的數來說，左邊的數量其實就是 $i$ - 左邊被刪除的數字，右邊同理
所以可以用一個 BIT 快速算出數量

1748 - Increasing Subsequence II

連結

題解

令 $dp_i$ 為陣列前 $i$ 項的答案，可以推出一個很顯然的轉移式：

$dp_i = \sum\limits_{j < i, a_j < a_i}dp_j$

一段前綴，可以先把數字離散化之後套 BIT 或線段樹來加速轉移

1149 - String Removals

連結

題解

定義 $dp_i$ 代表考慮前 $i$ 個字元，以第 $i$ 個字元為結尾的 subsequence 數量
則轉移式如下：
若在位置 $i$ 是第一次出現該字元，則 $dp_i = \sum\limits_{j = 0}^{i - 1}dp_j + 1$
否則若前一次是在第 $k$ 項出現該字元，則 $dp_i = \sum\limits_{j = k}^{i - 1}dp_j + 1$
原因的話是之前的字元都會在第 $k$ 項時算過，這樣就重複計算到了
這樣可以用前綴和在 $\mathcal{O}(1)$ 時間轉移，總複雜度 $\mathcal{O}(n)$

1188 - Bit Inversions

連結

題解

開兩棵可以求出區間最大連續和的線段樹，詳細可以看 CF EDU 的教學
一棵將 1 的位置設為 1 ，0 的位置設為 $-\infty$
另一開將 0 的位置設為 1 ，1 的位置設為 $-\infty$
之後每次修該完就能直接求答案

有另一種較狗幹的 set 實作法，因為我討厭那種作法就不提了 =w=

2419 - Xor Pyramid

連結

題解

根據巴斯卡三角形，第 $i$ 層第 $j$ 個位置會被算到的次數為 $\binom{i}{j}$
而原問題是 xor，所以只要能就快速判斷 $\binom{n}{i}$ 的奇偶性就好
方法是可以先預處理出 $n!$ 的質因數分解 2 的次方是什麼，然後就能在 $\mathcal{O}(1)$ 的時間完成判斷

1086 - Writing Numbers

連結

題解

觀察：最多的字元必為 1

這就導出一個合理的二分搜做法，至於要如何計算 $\leq x$ 的 1 的數量
可以採用跟 Counting Bits 類似的作法
留給讀者自行思考~

1113 - String Transform

連結

題解

連結
我就懶

2427 - Letter Pair Move Game

連結

題解

首先 $n \leq 6$ 直接暴力判所有 case，或可以用簡單的爆搜解決。剩下考慮 $n > 6$，一開始可以先用數次操作將空格移到最右邊兩格。

考慮每次操作先找到最小的 $i$ 滿足 $s_i$ 是 B，再找最小的 $j$ 滿足 $s_j$ 是 A 且 $j \geq i + 2$，則分一下 case（0-based）。

• $j < 2n - 3$

進行操作 $i \to j \to 2n - 2$

• $j = 2n - 3$

進行操作 $i \to j$ 後，只會剩下兩種可能：

1. 條件達成
2. 變成 $A^{n - 1}B^n..A$

原因：首先若 $s_{i + 1}$ 是 B，那 $i$ 後面只會剩下一個 A，做完上述操作後確實會結束
而若 $s_{i + 1}$ 是 A，唯一可能的字串為 $A^{n - 2}BAB^{n - 1}A..$ 這種形式，而這種形式做完之後就會變成上述 2. 的字串。

而若變成 2. 的字串，再做 $n - 1 \to 2n - 2$ 後會變成 $A^{n - 1}BAB^{n - 1}$。

• $j$ 不存在

字串一定會是 $A^{n - 1}BAB^{n - 1}$，做 $i + 1 \to 2n - 3 \to i$ 即結束。

對於 $j < 2n - 3$ 的情況，只會用 3 次操作，且操作完後 $s_i$ 會變成 A。而剩下兩個情況頂多用 7 次操作就可以達成條件，所以可以發現最多只要 3n + 7 次，就算加上最開始搬空格操作依然是綽綽有餘。

1147 - Maximum Building I

連結

題解

對於每一個位置，存下他往上撞到障礙物之前最高的高度，之後就用跟 Advertisement 一樣的做法解決
變成需要做 $n$ 次複雜度為 $\mathcal{O}(m)$ 的單調對列

1162 - Sorting Methods

連結

題解

1. 答案是 inversion 數量，即為 $j < i, a_j > a_i$ 的對數
2. 對於每一個 $i$，建一條 $i$ 指向 $p_i$ 的有向邊，則答案為 $n -$ 環的數量
3. 答案是 $n -$ lis 長度
4. 定義 $x$ 為最小的數 s.t. $[x, x + 1, ..., n]$ 為原陣列的 subsequence，則答案為 $x - 1$

說明

1. 首先，每次 swap 相鄰字元最多只會讓 inversion 數量減 1，所以交換次數至少為 inversion 數量
   接著講一個顯然結論：若一個陣列滿足 $\forall i, a_i \leq a_{i + 1}$，則 inversion 為 0
   這可以得出當 inversion 不為 0 時，必可以找到一個 index $i$ s.t. $a_i > a_{i + 1}$
   也因此，無論如何一定可以交換兩相鄰數使 inversion 數 -1
   因此證畢，最少次數為 inversion

2. 首先，用前面建邊的方式建圖，那最終狀態會是環數量為 $n$，而每次 swap 操作後最多只會讓環的數量 +1
   接著當環不到 $n$ 時，根據鴿籠原理必存在一個環大小 $\geq 2$，又挑選同一個環上的任意兩點都可讓環的數量 +1
   因此最少次數就是 $n -$ 環的數量

3. 顯然發現可以花一步將任意一個數移到正確的位置，因此目標可以視為最大化不移動的數字數量
   而這可以發現 lis 就是所求

4. 同上，同樣思考如何最大化不移動的數字數量即可推出結論

1191 - Cyclic Array

連結

題解

做法 1

我覺得這蠻玄的 XD 不過非常好寫
以下定義 $last_i$ 為從 $i$ 開始的最遠的值使的區間 $[i, last_i)$ 的區間和 $\leq x$，則：

int now = 0;
for (int i = 0; i < n; ++i) now = last[now];
// then now is one of the optimal starting points

證明 from Swistakk

然後就結束了 =w=
計算 last 的方式可以用雙指標做完，複雜度 $\mathcal{O}(n)$

做法 2

用倍增的方式，定義 $dp_{i, j}$ 為從 $i$ 開始，跳 $2^j$ 段的和
之後就可以窮舉起點，每次從最高的 bit 開始跳
若跳完總和不會超過就把答案加上去
而每個點最多跳 $\text{log}n$ 次，因此總複雜度 $\mathcal{O}(n\text{log}n)$

2414 - List of Sums

連結

題解

先把 $b$ 陣列排序好
首先，只要我們知道了 $a_0$，那麼就可以還原出整個陣列了
(每次挑選出 $b$ 陣列的最小值，把他和 $a_0$ 相減即可)

接下來，我們會知道 $a_2 - a_1 = b_1 - b_0$
(原因：$a_0 + a_1 = b_0, a_0 + a_2 = b_1$)

又由於 $a_1 + a_2$ 的值只有可能在 $b_2$ 到 $b_n$ 其中之一
所以可以推出只有 $n - 2$ 種可能的 $a_0$ 值，就每一個都試一遍即可

2132 - Increasing Array II

連結

題解

slope trick

1189 - Food Division

連結

題解

首先定義 $c_i = a_i - b_i$，每次操作同於挑選兩相鄰數，或是第 $n$ 項與第 1 項一個 +1 一個 -1
而換個角度想，當 $\forall 1 \leq i \leq n - 1$ 建好前綴和 $pre_i = \sum\limits_{j = 1}^{i}c_j$，那每次操作相鄰同於將一個數字 +1 或是 -1
至於挑選第 $n$ 項與第 $1$ 項做操作，這樣同於 $\forall 1 \leq i \leq n - 1$ 都 +1 或 -1

有了這些結論，可以說明答案為以下式子最小的可能值：

$\sum\limits_{i = 1}^{n - 1}{|pre_i - x|} + |x|$

而顯然 $x$ 為 $pre$ 與一個 0 所形成的陣列的中位數時該值最小

1654 - Bit Problem

連結

題解

SOS DP

1698 - Swap Round Sorting

連結

題解

首先先建邊 $i \to p_i$ 並拆成好幾個環，首先會有以下顯然結論：

1. 若所有環的大小都為 1，那答案為 0 次操作
2. 若所有環的大小不是 1 就是 2，那答案為 1 次操作

否則考慮一個大小為 $m$ 的環 $a_1 \to a_2 \to a_3 \to \dots \to a_1$，先做以下操作：

1. $m$ 是奇數：
   先交換 $a_{m - 1}$ 與 $a_m$，接著交換 $a_1$ 與 $a_{m - 2}$、$a_2$ 與 $a_{m - 3}$ …
2. $m$ 是偶數：
   先交換 $a_1$ 與 $a_2$，接著交換 $a_3$ 與 $a_m$、$a_4$ 與 $a_{m - 1}$ …

之後可以發現每個環都變成大小至多為 2 的環，因此再一次操作即可，總共 2 次

2430 - Binary Subsequences

連結

題解

首先，用一個跟之前這題作法不同的角度來想一下
定義 $dp_{i, 0}$ 為考慮前 $i$ 個字元，結尾為 0 的 distinct subsequence 數，$dp_{i, 1}$ 則代表結尾為 1 的
轉移式的話首先若當前結尾字元為 $x$，那 ~$x$ 的維度一定不會變，而 $x$ 的維度呢？
顯然的結論是每一個以 $x$ 結尾的 subsequence 都可以轉換成結束在第 $i$ 個位置，那就可以推出轉移式：
$dp_{i, x} = {dp_{i - 1, 0} + dp_{i - 1, 1} + 1}$

base case: $dp_{0, 0} = dp_{0, 1} = 0$，最後答案是 $dp_{n, 0} + dp_{n, 1}$

再來需要一些觀察：

1. 對於任意的 01 字串，他所產生的 pair $(dp_{n, 0}, dp_{n, 1})$ 是唯一的
2. 給定兩數 $a, b$，則可還原出唯一的 01 字串使的 $dp_{n, 0} = a, dp_{n, 1} = b$，或是判斷出無解

後者的方式是不斷將較大數減掉較小數 + 1，過程中若兩數相等且不為 0 則無解
當兩數皆為 0 就代表結束 (已回到 base case)

而我們需要找的是最小的 01 字串長度使的 $dp_{n, 0} + dp_{n, 1}$ 為給定的數字
所以可以窮舉每一個 $dp_{n, 0}$ 的值，使用類似輾轉相除法的方式把複雜度壓到一次 $\mathcal{O}(\text{log}n)$，最後再還原出字串即可

1700 - Tree Isomorphism I

連結

題解

我們嘗試將有根樹標上編號，編號相同則代表兩者同構，否則代表不同構。注意到兩棵有根樹同構的條件為：

• 將兩棵樹根的兒子數量相同，且樹根兒子的子樹們可以一一對應，對應的兩者為同構關係

所以如果我們得知了一棵樹拔掉根後每一個連通塊的編號，那就只要檢查他們的集合是否相同即可。

因此我們開一個 map<vector <int>, int>，能夠將樹根兒子的子樹編號們打到一個這棵樹的編號，之後就只要 dfs 一遍沿途維護好每棵子樹的編號即可。

如果有點難理解的話可以參考一下別人的 code

2228 - Counting Sequences

連結

題解

以 $k = 3$ 為例，答案等於：
(所有可能) - (沒有 1) - (沒有 2) - (沒有 3) + (沒有 1、2) + (沒有 1、3) + (沒有 2、3)

而沒有的種類數相同，答案數其實也是相同的，所以這樣就可以推出正確答案為：

$\sum_{i = 0}^{k - 1}{(k - i)^n \cdot \binom{k}{i} \cdot (-1)^i}$

而這個算式其實就是 Stirling numbers of the second kind

1703 - Critical Cities

連結

題解

Dominator Tree

有其他作法 我看懂再說= =

1706 - School Excursion

連結

題解

首先，這題先用並查集可以轉換成這個題目：
有 $m$ 個東西，每一個有重量 $w_i$，且 $\sum\limits_{i = 1}^{m}{w_i} = n$
$\forall 1 \leq i \leq n$，請輸出有沒有可能湊出重量 $i$

這個問題很明顯是背包問題，然而 $\mathcal{O}(nm)$ 會爆欸 QQ

來點不一樣的想法吧，總和為 $n$ 這個條件可以推出最多只有 $\mathcal{O}(\sqrt{n})$ 種可能的重量
原因：$1 + 2 + 3 + ... + x \leq n$

這樣就可以套有限背包解決這題，複雜度 $\mathcal{O}(n\sqrt n)$

痾… 這裡講一個簡單實作的方法
對於每一種重量 $w$，在跑 dp 的過程多開一個陣列維護若 $i$ 這個重量是這一輪才跑到，那它需要用幾個 $w$
這樣要是數量太多的話就可以直接判斷出來
我還是不太會表達= =，直接看 code 可能比較快

vector <bool> dp(n, false);
for (int w : W) { // W store all possible weight
    int num = cnt[w]; // number of weight w item
    vector <int> t(n, 0); // number of use
    for (int i = 0; i + w < n; ++i) if (dp[i] && t[i] + 1 <= num) {
        dp[i + w] = true;
        t[i + w] = t[i] + 1;
    }
}

1709 - Coin Grid

連結

題解

裸裸的二分圖最小點覆蓋
轉換方法是二分圖兩邊各 $n$ 個點，若第 $i$ 行第 $j$ 列有硬幣，就把左邊第 $i$ 個點和右邊第 $j$ 個點連邊
而二分圖最小點覆蓋 = 二分圖最大匹配數 (可以自行 google 原因)
二分圖最大匹配可以用匈牙利解，但我是直接砸 flow la
再講一下還原解，flow 的作法是從源點開始 bfs，只走還有流的邊
最後挑選左邊還沒被跑過的點和右邊被跑過的點當作覆蓋的點即可
可以證明這是一組最小點覆蓋

1742 - Robot Path

連結

題解

我們把移動表示成線段，我們會想要算出「最多可以移動多少，讓線段的交點數量依然為線段數量 -1」

而這個可以合理的二分搜 + 掃描線 BIT，複雜度會是兩個 $\text{log}$

這題也有很多實作細節，首先需要特判互相平行的線段是否有交點，還有相鄰操作方向相反之類的

總之，加油 =w=

2426 - Programmers and Artists

連結

題解

首先先將人按照作為 programmer 的數值由大到小排序好，這樣會有一個性質：
若一個解是 optimal 的，假設最後面作為 programmer 的人是 $i$，那在 $i$ 之前的人都一定有職業
證明：因為若存在一個人沒有職業，那把第 $i$ 個人的 programmer 職業給那個沒職業的人一定不會變差

所以這導出一個作法：
先 $\forall a \leq i \leq a + b$，計算出 $pre_i$ 代表從前綴 $i$ 挑選 $a$ 個 progammer，而其他都是 artist 的最大答案
接著 $\forall a \leq i \leq a + b$，再計算出 $suf_i$ 代表從後綴 $i$ 挑選 $b - i + a$ 個 artist 的最大答案
這些數值都可以用一個 priority queue 計算完，最後再取全部最大即可

1757 - Course Schedule II

連結

題解

作法：
每次從最大 index 且出度 0 的點開始填，大的數字開始放

證明：
假設一個點 $v$ 沒有滿足條件，在上面操作被標成 $x$，那把他變成他可到達的最大值，假設為 $y$ ，那把所有被標成 $x + 1$ 到 $y$ 的數字都 -1，這樣字典序會變更小，矛盾

而整個過程用一個 priority queue 維護出度為 0 的點即可做完

2174 - Removing Digits II

連結

題解

首先定義 $f(x)$ 為 $n = x$ 的答案，我們有以下觀察：

1. 每次一定是移除最大的數字

同於證明 $\forall n \geq 1, f(n - 1) \leq f(n)$

過程：考慮數歸，$n = 1$ 時，$0 = f(0) \leq f(1) = 1$，成立
假設 $n < k$ 時皆成立，那麼當 $n = k$ 時，定義 $s$ 為 $k$ 最大的數碼，顯然可以推論出移除 $s$ 是其中一個最佳解
再令 $t$ 為 $k - 1$ 最大的數碼
那麼 $f(k) = f(k - s) + 1$，$f(k - 1) = f(k - 1 - t) + 1$
由 $k$ 跟 $k - 1$ 的關係可知 $t \geq s - 1$，那麼 $k - s \geq k - 1 - t$，可推出 $f(k) \geq f(k - 1)$
最後由數歸即證畢

2. 將 $n$ 變為 0 的過程中，對於任意一數 $x$ 滿足 $0 \leq 10x \leq n$，必存在一數 $0 \leq c \leq 9$ 使的過程經過 $10x + c$

有了這個有甚麼用呢？首先一個簡單的想法是每次都將十位數 -1，然而這樣顯然會超時，不太可行
那就換個角度想，考慮看看一次把一個位數 -1，那這樣就會在導出另一個問題：能不能讓十位數經由 -1 變成一個固定的數字，讓後面百位數、千位數在做運算的時候可以更方便

答案是可以的，我們將位數變成 9，這樣一來會變成需要計算的是將形式 $x99999y$ 變成 $(x - 1)99999z$的所需步數，以及過程後個位數變成的值(即為 $z$)

舉個例子，3234 的移動步驟為：
3234 -> 322? -> 321? -> 320? -> 319? -> 309? -> 299? -> 199? -> 99? -> 0

這部分可以先預處理，$dp_{i, j, k}$ 代表考慮 $i$ 個 9 與 1 個 $j$ 組成的數字，其中在這些數字之前的數碼最大值為 $k$，需要花費的步數使的數字變成 $< 0$，$to_{i, j, k}$則代表上述 state 變成 $< 0$ 時的個位數字
這裡為了方便計算答案，將 $i = k = 0$ 的 dp 值定為讓數字變成 $0$ 的次數

至於預處理的方法可以將一堆 9 才拆成頭 1 個 9 及剩下的，後半段經由前面的預處理已得出答案，所以只要將前面的字元從 9 開始扣即可

所以預處理完就順著前面的步驟移動就好，複雜度是 $\mathcal{O}(18 \times 10^3)$

2180 - Coin Arrangement

連結

題解

觀察：存在一組最佳解使的對於任意兩相鄰 column，不會同時往左移動又往右移動

原因是這樣可以把他轉成往上動往下動

這也導出一個 greedy 策略：首先為了方便先將每一個數字 -1，問題變成要讓所有數字變成 0

之後從左邊掃到右邊，維護現在上排和下排的數字，如果上下正負號不一樣就移動直到兩個變一樣

跑完最後即為最佳解

2176 - Counting Bishops

連結

題解

(from dannyboy)

首先先將座標轉 45 度

可以發現白色和黑色互不影響，可以分開考慮

接著我們要對於每一個 $k$，算出在每一行、每一列最多只能放一個棋子的情況下，有幾種放法可以放下 $k$ 個棋子
而這要怎麼做呢？我們改變一下行的順序吧，把他排成如下圖這樣：

因為每個 row 可以放棋子的部份都會被後面的 row 覆蓋，就可以好好 dp 了。考慮 $dp_{i, j}$ 代表前 $i$ 行放置 $j$ 個棋子的方法數
轉移式：

$dp_{i, j} = dp_{i - 1, j} + dp_{i - 1, j - 1} \cdot (cnt_i - j + 1)$

其中 $cnt_i$ 為第 $i$ 行的格子數量

而兩個棋盤分別算好 dp 之後就能直接用卷積的式子算出答案了

2432 - Grid Puzzle I

連結

題解

flow 經典題，建模方法為：
左邊 $n$ 個點，右邊 $n$ 個點
將 source 到左邊第 $i$ 個點連一條流量為 $a_i$ 的邊
將右邊第 $i$ 個點到 sink 連一條流量為 $b_i$ 的邊
之後中間全點對連一條流量 1 的邊
然後直接讓他流下去即可

2131 - Grid Puzzle II

連結

題解

同上，只是改為 MCMF 即可
實作上可以將邊的 cost 定為負數，這樣跑出來的就會是 max value

1080 - Empty String

連結

題解

$dp_{i, j}$ 代表將區間 $[i, j)$ 變成空的方法數
那轉移的話可以考慮枚舉第 $i$ 個字元會和誰消除掉，轉移式為：

$dp_{i, j} = \sum\limits_{s_i = s_k}{dp_{i + 1, k} \cdot dp_{k + 1, j} \cdot \binom{\frac{j - i}{2}}{\frac{k - i}{2}}}$

其中轉移式包含 combination 的原因是要考慮兩個區間誰先取後取的方法數

1078 - Grid Paths

連結

題解

首先，先解決障礙數為 0 的問題：在一個 $n \times m$ 的矩形，每次移動只能往右或往下走，要從左上角走到右下角的方法數是多少？
因為往左走的次數會是 $m - 1$，往下走的次數會是 $n - 1$，所以方法數是 $\binom{m + n - 2}{m - 1}$

那接著來考慮 dp 吧，$dp_i$ 代表不經過其他障礙物，最後停在第 $i$ 個障礙物位置的方法數
轉移的直觀想法是用扣的，把方法數扣掉已經先經過其他點的情況，而具體上的想法可以考慮下面兩種 case：
1.

s.k. 
.j..
...i

$j, k$ 為任意兩障礙物，$s$ 為起始點
可以明顯發現 $s$ -> $j$ -> $i$ 的路徑與 $s$ -> $k$ -> $i$ 的路徑不會重複
2.

sk..
..j. 
...i

由於經由 dp 算出的 $s$ -> $j$ 路徑不會經過 $k$(由定義)
因此可以發現 $s$ -> $j$ -> $i$ 的路徑與 $s$ -> $k$ -> $i$ 的路徑一樣不會重複

也因此，對於任意兩個在 $i$ 點左上方的障礙物，所有經由他們到達 $i$ 的路徑都是相異的
對於 $i$ 來說，需要扣除的答案其實就是：

$\sum\limits_{x_j \leq x_i, y_j \leq y_i}{dp_j \times \binom{x_i - x_j + y_i - y_j}{x_i - x_j}}$

而計算 dp 可以先將點座標按照 $x$、$y$ 由小到大排序，即可按照順序 dp
有一個小 trick 是可以加一個點座標為 $(n, n)$ 的障礙物，而答案就會是該點的 dp 值

總複雜度$\mathcal{O}(m^2 + n\text{log}mod)$

2115 - Bit Substrings

連結

題解

假設蓋好前綴和 $pre_i$ 代表前 $i$ 項的 1 數量
再算好 $cnt_i$ 代表 $pre_j = i$ 的數量
那麼題目變成要對於每一個 $k$，計算 $\sum\limits_{j - i = k}{cnt_i \times cnt_j}$
而這個是一個卷積的形式，可以用 FFT 來做完，詳細作法是將一個正的 $cnt$ 多項式和一個負的 $cnt$ 多項式乘起來

2075 - Reversal Sorting

連結

題解

反正操作可以做到 $n$ 次，那就每次都讓一個人回到正確的位置即可
那作法就是需要支援快速區間 reverse 和詢問最小值
那這些用一棵 Treap 即可解決，只要維護最小值即可

2421 - Counting Reorders

連結

題解

考慮排容，令 $x$ 為一個長度為 $n - 1$ 的 01 字串，則定義 $f(x)$ 為滿足 $\forall 0 \leq i < n - 1, x_i = 0 \lor s_i = s_{i + 1}$ 的字串數量

又定義 $g(n) = \sum\limits_{cnt1_x = n}f(x)$，$cnt1_x$ 為 $x$ 字元 1 的數量

那答案會是 $g(0) - g(1) + g(2) - g(3) + ...$

換個角度想，我們想要將一個字串分成許多個區間，區間內的每個字元都相同，而且我們事實上只在乎有幾個區間而已，因為只要有區間數量就可以知道排容正負號了

因此我們可以考慮 dp 了，$dp_{i, j}$ 代表考慮前 $i$ 種字元，已經分成了 $j$ 個區間

那考慮主動向上更新，枚舉第 $i$ 種字元要被分成 $k$ 個區間，則可以得出轉移式：$dp_{i, j + k} = \sum\limits_{k = 1}^{cnt_i}dp_{i - 1, j} \cdot \binom{j + k}{j} \cdot \binom{cnt_i - 1}{k - 1}$，其中 $cnt_i$ 為第 $i$ 種字元的數量

第一個 C 為考慮原本區間與當前區間的排列數，第二個 C 為考慮將第 $i$ 種字元分成 $k$ 個區間的方法數

乍看之下複雜度是 $\mathcal{O}(26n^2)$，但實際上如果每次 dp 第二個維度只跑到當前可能的最大上限，複雜度就會變成好好的 $\mathcal{O}(n^2)$

原因的話可以使用樹背包的想法，因為我有點懶就交給讀者自己思考了 (X

1159 - Book Shop II

連結

題解

有限背包，這裡來講一下單調隊列的作法
$dp_{i, j}$ 為考慮前 $i$ 個物品且重量為 $j$ 的方法數，則

$dp_{i, j} = \max_{0 \leq num \leq x_i}(dp_{i - 1, j - num * w_i} + num \cdot v_i)$

變一下

$dp_{i, j} = \max_{k \equiv j \pmod {w_i}, 0 \leq \frac{j - k}{w_i} \leq x_i}(dp_{i - 1, k} + v_i \cdot \frac{j - k}{w_i})$

再變一下

$dp_{i, j} =v_i * \lfloor \frac{j}{w_i} \rfloor + \max_{k \equiv j \pmod {w_i}, 0 \leq \lfloor \frac{j}{w_i} \rfloor - \lfloor \frac{k}{w_i} \rfloor \leq x_i}(dp_{i - 1, k} - v_i \cdot \lfloor \frac{k}{w_i} \rfloor)$

這樣就可以分開處理每一個同餘的數字，而轉移的又是一段遞增區間的最大值
可以使用單調隊列優化讓複雜降低到 $\mathcal{O}(nW)$

1677 - Network Breakdown

連結

題解

如果只有加邊的話用並查集可以輕鬆維護，刪邊的話好像不太能直接做
那要是將詢問反過來做的話呢？這樣一來刪邊就變成加邊了，也就可以用並查集直接做完了

這個技巧也叫做時光逆流

1203 - Visiting Cities

連結

題解

對正圖以 1 為 source 做一遍 dijkstra，並維護到每一個點的最短路徑數
再對反圖以 $n$ 為源點做一樣的事
而判斷一條點是否為答案的條件就是距離和 = 原本的距離且方法數乘積 = 原本的總方法數

而要注意的是存下的方法數可能會太大，所以要取模
也因為這樣，這個方法有一定的錯誤率，但我也不知道其他作法就是了 owo

2184 - Missing Coin Sum Queries

連結

題解

首先先講一下 $q = 1$ 的作法(就是這題)
方法是將硬幣由小到大排好，一開始 $ans = 0$，每次跑到一個價值硬幣 $x$ 的時，要是 $ans + 1 < x$，就代表 $ans + 1$ 無法被湊出來，因此輸出答案
否則代表到 $ans + x$ 都可以湊出來，因此把硬幣加上去，繼續跑下去

要推廣到多筆詢問的話，首先觀察到要是當前的最小值是 $x$，且符合 $ans + 1 \geq x$，那其實介於 $x$ 到 $ans + 1 + x$ 的數字都可以直接加進去
這樣就可以導出一個做法：

1. 將所有硬幣分成 30 層，第 $i$ 層存下價值介於 $[2^i, 2^{i + 1})$ 的硬幣
2. 從第 0 層開始跑，若該層有硬幣，就取出該層的最小值 $x$

若滿足 $ans + 1 \geq x$ 就保證該層硬幣都可以直接加進答案
因此只需要支援靜態詢問區間最小值與詢問區間和即可

複雜度為 $\mathcal{O}(q\text{log}n\text{log}C)$

然而這樣可能會被卡常，可以離線用並查集做 RMQ，複雜度可以壓到 $\mathcal{O}((n + q)\text{log}C\alpha(n))$

1157 - Number Grid

連結

題解

打表一下

0 1 2 3 4 5 6 7
1 0 3 2 5 4 7 6
2 3 0 1 6 7 4 5
3 2 1 0 7 6 5 4
4 5 6 7 0 1 2 3
5 4 7 6 1 0 3 2
6 7 4 5 2 3 0 1
7 6 5 4 3 2 1 0

然後就出來了

1148 - Maximum Building II

連結

題解

參考類似 Maximum Building I 的做法
這裡在蓋 $r$ 陣列時蓋成非嚴格，即為：$r_i$ 代表最小的index $j$ s.t. $h_i \geq h_j$
這樣一來可以發現，我們會有 $\sum\limits_{i = 1}^{n}{h_i \cdot (r_i - i) \cdot (i - l_i)}$ 種不同的矩形，如下圖

而為了要快速計算每一種的形狀，可以採取以下方法：

1. 首先，先推出給定 $l, r$，寬為 $x$ 的數量為：(WLOG, $l \leq r$)
   $x$, if $x \leq l$
   $l$, if $l < x \leq r$
   $r + l - x$, if $x > r$

2. 可以發現這是線性函數，可以用以下方法：
   寬度為 $x$ 的數量，我們使用兩個數值 $a, b$ 表示答案為 $ax + b$

這樣一來，要將答案加上 $l, r$ 的貢獻可轉換成：

1. $[1, l]$ 區間 $a$ 值 +1
2. $(l, r]$ 區間 $b$ 值 +$l$
3. $(r, l + r)$ 區間 $a$ 值 -1，$b$ 值 +$l + r$

這樣一來就轉換為一堆二維的矩陣加值問題，用二維前綴和先預處理完即可

2423 - Filling Trominos

連結

題解

首先，$n, m$ 一定要有一個是 3 的倍數，WLOG 假設 $n$ 是 3 的倍數
接下來狗幹分 case：

1. $n = 1$ 或 $m = 1$，顯然無解
2. $m$ 偶數，那就拆成一堆 $3 \times 2$ 的矩形即可

AACCEE
ABCDEF
BBDDFF

3. $n$ 偶數、$m$ 奇數，可以拆成前 3 行與剩下，前 3 行可以拆成 $2 \times 3$ 的矩形，剩下的回到上面的 case，拆成一堆 $3 \times 2$ 即可

AABAA
ABBAB
CCDBB
CDDCC
EEFCD
EFFDD

4. 其他($n, m$ 皆為奇數)，首先 $n = 3$ 或 $m = 3$ 顯然無解
   其他的話由於 $9 \times 5$ 有解：

AACAA
AECCA
GEEGG
GGBAG
DBBAA
DDIIG
AAIGG
ADFFD
DDFDD

所以可以將原棋盤拆成 $9 \times 5$、$9 \times (m - 5)$ 與 $(n - 9) \times m$，用前面的 case 即可解決

這裡再講一下塗色的方法，可以觀察到：

AA.AA
AA.AA

無論 T 型怎麼擺都不會撞到這兩塊，因此將 T 型左上角的 row 與 col 座標模 3 後即可直接用這個做為顏色

1161 - Stick Divisions

連結

題解

考慮從切完後的樣子回推回去
可以考慮 greedy 策略：
每次挑選兩個最小長度合併

證明 from BurnedChicken

1665 - Coding Company

連結

題解

首先先把值大到小排序好
這樣一來每一組值的計算方式可以變成在新建組的時候將值加上去，結束組的時候將值扣掉
接著考慮 dp，$dp_{i, j, t}$ 代表考慮前 $i$ 個人，現在有 $j$ 組尚未結束且當前的值是 $t$
轉移用主動向上轉移，case 有：

1. 第 $i$ 個人新建一組，state 會從 $dp_{i, j, t}$ 變成 $dp_{i + 1, j + 1, t + v_i}$
2. 第 $i$ 個人加入其他的組，但沒有結束，會有 $j$ 種可能，state 會從 $dp_{i, j, t}$ 變成 $dp_{i + 1, j, t}$
3. 第 $i$ 個人結束其他的組，會有 $j$ 種可能，state 會從 $dp_{i, j, t}$ 變成 $dp_{i - 1, j - 1, t - v_i}$

最後答案是 $\sum\limits_{i \leq x}{dp_{n, 0, i}}$

1699 - Flight Route Requests

連結

題解

首先，可以只花 $n$ 條邊將 $n$ 的點強連通：

做法：
考慮有向圖轉無向圖的每一個 CC，令 $n$ 為 CC 的點數，若這個 CC 的有向圖有環，那就代表邊數一定 $\geq n$，花 $n$ 條邊即可
否則代表那張圖是 DAG，只需要花 $n - 1$ 條邊
最後把每個 CC 答案加起來即可

2402 - Two Stacks Sorting

連結

題解

首先觀察一下發現兩個數 $i < j$ 如果滿足以下兩個條件，那它們必須要放在不同堆：

• $p_i < p_j$
• 存在 $k > j$ 滿足 $p_i > p_k$

而只要有一項沒滿足的話，它們兩個放在同一堆也沒差，所以這可以得出一個 $O(N^2)$ 的解：建完邊後判斷圖是不是二分圖即可。

優化方法的話，首先注意到我們只要找到這張圖的隨便一棵生成森林，二分圖著色後再 $O(N)$ 檢查一遍這個擺法是不是好的就好了。

再來我們要想辦法化簡有邊的條件。假設 $i < j$ 時，條件為 $suf_j < p_i < p_j$，其中 $suf_i$ 為 $i < k$ 的最小 $p_k$。

這個條件已經足夠簡單了，我們就可以來優化前面的二分圖塗色：建一棵區間詢問最小值位置的線段樹，每次跑到點 $v$ 時，就暴力在 $[suf_v, p_v]$ 這段區間內尋找符合條件的 $i$，每次找出最小的只要檢查是否 $i < v$ 就可以繼續拜訪下一個點了。而只要再記得將跑過的點從線段樹上刪掉，複雜度均攤就會是好好的 $O(N \log N)$。

而 $v < i$ 的邊可以用類似的方法處理，因此整體二分圖塗色就可以在 $O(N \log N)$ 做完。

1701 - Tree Isomorphism II

連結

題解

跟 Tree Isomorphism I 相比，現在變無根樹了
可以發現兩棵樹若是同構的，樹重心(們)也一定會相同
所以就以樹重心為根做跟上一題相同的事就好

1705 - Forbidden Cities

連結

題解

首先先對這張圖點雙連通分量縮點，如果 $c$ 不是割點的話那顯然答案是 YES
否則要是縮點後 $c$ 點在 $a$ 和 $b$ 的路徑上，就代表答案是 NO，否則為 YES
而後者要判斷的話可以用樹剖將路徑拆成一堆區間，再判斷那些區間有沒有包含 $c$ 即可
複雜度會是一個 $\text{log}$，因為只需要判斷區間而不用線段樹

1741 - Area of Rectangles

連結

題解

經典題，叫矩形覆蓋面積(?
做法是使用掃描線讓問題降低一個維度，變成需要支援：
區間加值、減值
詢問整體區間非 0 的數量
而注意到這整個過程中不會有負數，所以開一棵線段樹維護最小值與最小值數量即可

2429 - Grid Completion

連結

題解

一臉組合題，首先可以先把問題轉換成這樣：

給定兩個長度 $n$ 的 array $p, q$，陣列每一項可能是 -1 或是 1 到 n 的整數
現在請將每個 -1 填上一個 1 到 n 的整數，使：

1. $p, q$ 都是 permutation
2. $p_i \neq q_i$

考慮排容，令 $x$ 為一個長度為 $n$ 的 01 字串，則定義 $f(x)$ 為滿足 $\forall 0 \leq i < n, x_i = 0 \lor p_i = q_i$ 的字串數量

又定義 $g(n) = \sum\limits_{cnt1_x = n}f(x)$，$cnt1_x$ 為 $x$ 字元 1 的數量

那答案會是 $g(0) - g(1) + g(2) - g(3) + ...$

接著思考甚麼情況會 $p_i = q_i$，有以下三種可能

1. $p_i = -1$ 且 $q_i = -1$
2. $p_i = -1$ 且 $q_i \neq -1$，數字 $q_i$ 並未在出現在原始的 $p$ 陣列
3. $p_i \neq -1$ 且 $q_i = -1$，數字 $p_i$ 並未在出現在原始的 $q$ 陣列

因此方法就出來了，首先先計算出三種可能的位置數量，假設位置數量分別為 $c_1, c_2, c_3$
再計算出有多少個數字沒有出現在兩個原始陣列中，假設此數量為 $c_4$
再計算出有多陣列 $p, q$ 分別有幾個 -1，假設此數量為 $c_p, c_q$
由於每個位置最多只會被分在一類，因此答案為：

$\sum_{i = 0}^{min(c_1, c_4)}\sum_{j = 0}^{c_2}\sum_{k = 0}^{c_3}\binom{c_1}{i}\binom{c_2}{j}\binom{c_3}{k}\binom{c_4}{i}(i)!(c_p - i - j)!(c_q - i - k)!(-1)^{i + j + k}$

1752 - Creating Offices

連結

題解

結論：隨便取一個點當根做 dfs，將點按照深度大到小開始看，若可以選的話就選，不能選就跳過，可以證明這樣出來會是其中一組最優解

證明：(from syl123456)
只要證明選取一些點之後，以下兩件事情會發生至少一件即可：

1. 深度最深的點可以被選
2. 將其中一個已被選的點換成深度最深的點仍然一組最優解

令最深的點為 $v$，當 1. 不成立時，必存在一點 $u$ 使的他已被選取且 $dis(u, v) \leq d$
令 $x = lca(u, v)$，則選擇 $v$ 會擋住的點包括：

1. $x$ 的子樹 (原因：$v$ 為深度最深的點)
2. 在 $x$ 子樹外且滿足與 $v$ 距離 $\leq d$ 的點

考慮在 $x$ 子樹以外的點，因為 $v$ 是深度最深的，所以將 $u$ 換成 $v$ 不會讓子樹以外被擋住的點數變多，也因此換完仍然會是一組最優解

由上可證明原本的 greedy 策略，只要不斷取深度最深的點即可
至於檢查某點使否可被選擇可以用重心剖分維護距離最小值，詳細可以參考 CF 這題
複雜度是常數有點肥的 $\mathcal{O}(n\text{log}n)$

1075 - Permutations II

連結

題解

首先，這題 OEIS 搜的到，而且複雜度可以做到 $\mathcal{O}(n)$，但我覺得這題的 $\mathcal{O}(n^2)$ 想法很優質，所以還是講一下

我們考慮 dp：$dp_{i, j, k}$ 代表考慮長度為 $i$ 的 permutation，有 $j$ 對相鄰數字皆 $\leq i - 1$ 且相差 1
其中 $k = 1$ 代表 $i$ 與 $i - 1$ 相鄰，$k = 0$ 代表無

轉移用主動向上轉移，case 有：

1. 將 $i$ 插在 $i - 1$ 旁邊
   state 從 $dp_{i, j, 0}$ 變成 $dp_{i + 1, j, 1}$，這有兩種可能 (左右)
   state 從 $dp_{i, j, 1}$ 變成 $dp_{i + 1, j, 1}$ 或是 $dp_{i + 1, j + 1, 1}$
2. 將 $i$ 插在原本相差 1 的數之間
   state 從 $dp_{i, j, k}$ 變成 $dp_{i + 1, j + k - 1, 0}$，這有 $j$ 種可能
3. 其他
   state 從 $dp_{i, j, k}$ 變成 $dp_{i + 1, j + k, 0}$，這有 $i - 1 - j$ 種可能

而最後答案會是 $dp_{n, 0, 0}$

2415 - Functional Graph Distribution

連結

題解

首先，這題 OEIS 還是搜的到，但還是講一下正常的作法，先在這裡感謝 dreamoon 的提點 > <

先講個東西叫 Cayley’s formula，這東西說明了 $n$ 個有編號節點所能形成的無根樹數量為 $n^{n - 2}$，詳細可以使用前面提過的 Prüfer Code 來證明，有興趣可以自行研究或查詢

而這東西是有 general 版的，大致如下：

「滿足以下的無根森林數量：

1. 有 $n$ 個有編號的節點
2. 有 $k$ 個連通塊
3. 點 $1, 2, \cdots, k$ 在不同連通塊

為 $k \cdot n^{n - k - 1}$」

詳細證明可以使用數學歸納法

那我們再回來看這題，首先，先說明 $k = 1$ 要如何計算

因為 functional graph 的一個連通塊一定會有一個環，所以考慮枚舉「環的大小」吧

當環的大小為 $x$ 時，我們有 $\binom{n}{x}$ 種挑選環上點的方法，而環中又有 $(x - 1)!$ 種排列方式

現在剩下環外的邊了，考慮把環的邊都拔掉，會發現題目問的就是上面 Cayley’s formula general 的版本

所以方法數會是 $x \cdot n^{n - x - 1}$

整體而言，答案會是：

$\sum\limits_{x = 1}^{n}\binom{n}{x} \cdot (x)! \cdot n^{n - x - 1}$

現在來考慮 general 的 case，我們稍微改一下枚舉的東西，改成枚舉「$k$ 個連通塊的環的大小總和」

假設數量是 $x$，這樣的話一樣有 $\binom{n}{x}$ 種挑選環上點的方法，接著要把 $x$ 個點拆成 $k$ 個環，這個東西的方法數其實就是 stirling number of first kinds。這有個簡單的遞迴式：

$s(n + 1, k) = n \cdot s(n, k) + s(n, k - 1)$，其中 $s(0, 0) = 1$

最後環外的邊一樣把環的邊拔掉後用 Cayley’s formula 解決掉，整體答案會是：

$\sum\limits_{x = 1}^{n}\binom{n}{x} \cdot s(x, k) \cdot x \cdot n^{n - x - 1}$

再經過整理即可得出與 OEIS 相同的式子

可以使用 $\mathcal{O}(n^2)$ 建出 stirling number，再用 $\mathcal{O}(n^2)$ 算答案即可

1685 - New Flight Routes

連結

題解

首先，我們先將圖 SCC 縮點，會變成一個 DAG，而問題就是最少需要加幾條邊才能讓這張圖變成只有一個 SCC

假設那張 DAG 有 $s$ 個 source，$t$ 個 sink，(source = 入度 0 的點，sink = 出度 0 的點)

那答案顯然會有下界 $max(s, t)$，那我們會合理懷疑這就是答案

這時我們可能會想說亂連會不會就對了，然而這是有反例的：

如果連 2->1 和 3->4，那會是好的，然而，要是不小心連到 2->4 和 3->1 就慘了

總之，數量確實是這樣沒錯，問題就是到底要怎麼連才會是好的

首先，建一張二分圖，左邊為所有的 source，右邊為所有的 sink，兩個點 $(u, v)$ 之間有邊 iff $u$ 可以經由一些邊走到 $v$

那，我們先找出這張二分圖的 maximal matching，假設 matching 為 $(u_1, v_1), (u_2, v_2), \cdots (u_k, v_k)$，那就先建邊 $(v_1, u_2), (v_2, u_3), \cdots (v_k, u_1)$

注意的是這裡是 maximal matching，代表需要移除至少一條匹配邊才能讓一條非匹配邊加入

至於剩下沒匹配到的點呢？這些點亂連就好了

具體作法是每次挑出一個 source 和一個 sink，連 sink 到 source 的邊

至於還有多出來的點的話就亂連即可

Proof: 考慮這種連邊情況下的每一個 sink，要證明他們都能走到每一個 source

首先任意一個 sink 都可以走到至少一個 source

接著由於這是 maximal matching，任意一個 source 都可以走到一個 matching 上的 sink

再來由於這是 maximal matching，matching 上的 source 能走到所有的 sink

所以證完了

最後是實作的問題，因為這張新圖邊的量級是 $\mathcal{O}(n^2)$ 我們不可能建出所有的邊下去找 maximal matching

這裡我是直接用 flow 跑增廣路的方法下去硬找

複雜度是玄學，但總之因為 flow 很快所以這樣不會 TLE

其他做法的話可以在 dfs 的過程中，將已經跑完的邊用並查集壓縮起來，這樣只要一只對 source dfs 就好

2418 - Grid Path Construction

連結

題解

可以參考一下 Hamilton Paths in Grid Graphs 這篇論文，稍微看一下這篇可以激發不少靈感 XD。

首先不失一般性假設 $n \leq m$ 且令起點終點為 $(x_s, y_s), (x_t, y_t)$，同時假設起點為較左邊的點。另外，定義左上角的格子為 $(1, 1)$，右下角為 $(n, m)$，若 $x + y$ 為偶數則格子 $(x, y)$ 為白色，否則為黑色。除了顯然的塗色判無解方法外，論文的 3.1 告訴我們還有以下幾種無解情況：

• $n = 1$ 且起終點不是 $(1, 1)$ 與 $(1, m)$
• $n = 2$ $1 < y_s = y_t < m$
• $n = 3$ 且 $m$ 為偶數、$(x_s, y_s)$ 為黑色。同時以下兩種條件至少一項成立：
  • $y_s < y_t - 1$
  • $x_s = 2$ 與 $y_s < y_t$

那看完論文的 3.2 後我們可以得出以下作法，同樣不失一般性假設 $n \leq m$ 且起點為左邊的點：

• $m \leq 5$：直接用爆搜找答案
• $m > 5$ 且 $y_s > 2$：切成左邊 $n \times 2$ 與右邊 $n \times (m - 2)$，之後做以下事：
  • 遞迴找到右邊長方形的解
  • 上述解中一定可以找到在最左邊直排往上或往下的一步，將它改成往左與往右，最後在這兩步之間插入對應的左邊長方形的解即可。討論一下 $n = 1, 2, 3$ 的 case 後可以發現兩塊長方形一定都可以找的到解。
• $m > 5$ 且 $y_t \leq m - 2$：左右相反後變成上面那種 case
• 其他：一樣切成左邊 $n \times 2$ 與右邊 $n \times (m - 2)$ 兩塊，之後做以下事：
  • 找到一個點 $(x, 2)$ 使存在一組 $n \times 2$ 的長方形從 $(x_s, y_s)$ 到 $(x, 2)$ 的解
  • 遞迴找 $(x_s, y_s)$ 到 $(x, 2)$ 在 $n \times 2$ 長方形的解與 $(x, 3)$ 到 $(x_t, y_t)$ 在 $n \times (m - 2)$ 長方形的解後接起來即可。同樣討論一下 $n = 1, 2, 3$ 的 case 可以證明右邊長方形一定找的到解。

剩下就只剩實作問題了，個人覺得這個作法已經足夠乾淨了，有想清楚就不會到很難寫。