CF 2171E
Description
Solution
從 $1$ 開始，每六個連續數字一組，$\operatorname{block}_i$ 表示第 $i$ 組，每一組按照以下方式排 \[ \operatorname{block}_i = \begin{cases} [2+6i,\,1+6i,\,4+6i,\,6+6i,\,5+6i,\,3+6i], & \text{if $i$ is odd} \\ [3+6i,\,5+6i,\,6+6i,\,4+6i,\,1+6i,\,2+6i], & \text{if $i$ is even} \end{cases} \] ，這樣保證每一組裡面和每一組的連接處都會是 good ，最後那幾個湊不出一組的數直接放最後面。
時間複雜度 $O(n)$ 。
CF 2158D
Description
Solution
在紙上畫一下就可以很快證明所有長度為 $4$ 的字串可以經過操作變成任意字串，由此可以再推得長度 $n\geq 4$ 的也會滿足，例如 $n=6$ 時可以拆成 $[1,4]$ 和 $[3,6]$ 兩塊長度為 $4$ 的子字串。
用 BFS 計算所有長度為 $5$ 的字串變成任意字串的所需操作，輸出結果後觀察到最大操作次數不會超過 $4$ ，因此可以把整個字串每五個拆成一塊，不足五個的往左延伸補到五個。最差會需要 $4 \times \lceil\frac{n}{5}\rceil$ 操作。
當 $n=4$ 的時候可以再 BFS 一個長度為 $4$ ，最大操作次數不會超過 $6$ ，或者在 $s,\ t$ 後面都補個 $0$ 當成長度 $5$ 來算也剛好不影響答案。
時間複雜度 $O(n)$ 。
如果你想要只想要用 BFS 長度為 $4$ 的結果就計算答案的話, $n=5$ 要多特判幾個 case。
CF 2138C2
Description
Solution
令 $d_u$ 表示 $u$ 點的深度，LCS 的最大值會是 $\displaystyle\min_{u\in \text{leaf}}(d_u)$ ，並且我們只需要關注那些 $d_v \leq \displaystyle\min_{u\in \text{leaf}}(d_u)$ 的點就好，因為如果 LCS 的一部分存在於比 $\displaystyle\min_{u\in \text{leaf}}(d_u)$ 更深的地方，那跟上面的點交換也必定能滿足，並且需要的 label 個數只會更小或不變。
令 $cnt_i$ 表示 $d_u=i$ 的點有多少個，$x$ 表示 $d_v>\displaystyle\min_{u\in \text{leaf}}(d_u)$ 的點有多少個。
因為那些深度超過 $\displaystyle\min_{u\in \text{leaf}}(d_u)$ 的點放什麼都可以，所以檢查 $cnt$ 能不能恰好湊出 $[k-x,k]$ 之間至少一個數字，如果可以則答案為 $\displaystyle\min_{u\in \text{leaf}}(d_u)$ ，否則為 $\displaystyle\min_{u\in \text{leaf}}(d_u)-1$ 。
subset sum + bitset， 時間複雜度 $O(\frac{n ^ 2}{64})$ 。
CF 2131G
Description
Solution
令 $f(x)$ 表示把集合 $s$ 中的最小元素 $x$ 移除，並且移除所有後續新增元素所需的操作次數。同樣地，令 $g(x)$ 表示操作所得到的乘積，觀察可以得到
$$f(1)=1,\quad f(x)=1+\sum_{i=1}^{x-1}f(i)=2^{x-1}$$ $$g(1)=1,\quad g(x)=x\times\prod_{i=1}^{x-1}g(i)$$
注意到 $k\leq 10^9<f(32)$ ，因此只需要計算到 $f(31)$ 就好。排序 $s$ 後從小到大不斷把 $k$ 扣掉 $s_i$ 直到 $s_i>k$ ，接著寫個遞迴模擬剩下的操作直到 $k$ 被扣到 $0$ 。
時間複雜度 $O(n \log n + \log ^ 2 k)$ 。
CF 2063D
Description
Solution
觀察可以得到 $k_{max}=\min(n, m, \lfloor\frac{n+m}{3}\rfloor)$ 。
一個三角形由一邊的一個點和另一邊的兩個點構成，並且那一個點不管選哪一個都不會影響三角形的面積，因此我們要想辦法極大化那兩個點構成的邊長。排序 $a$ 和 $b$ ，每次取最遠的兩點構成一個邊長並記錄這個邊長是 $a$ 還是 $b$ 取出來的，丟進一個陣列 $c$ 並由大到小排序。
每次要盡可能取最長的邊，開兩個 stack 每次 push 取過的邊。當遇到 $a$ 或 $b$ 的點不夠用時，要把不夠用的地方刪掉一條在那個地方取過且最小的邊，從 stack 直接 pop 掉就好，再找另一邊的邊補回去。本質上是在 $a$ 和 $b$ 上面做 $O(n+m)$ 的雙指標。
時間複雜度 $O((n+m) \log (n+m))$ 。