CF 1422C
Description
Solution
考慮每個 digit 的貢獻，從右邊數過來，第 $i$ 個 digit 會貢獻 $10^{i-1}\cdot (i * \sum_{i+1}^n d_i + \frac{1}{2}(1+n-i)\cdot (n-i)\cdot d_i)$ 。
時間複雜度 $O(n)$ 。
CF 1550C
Description
Solution
觀察
- 假設 $i<j<k$ ，他們構成 bad triple 若且唯若 $a_i\leq a_j \leq a_k \lor a_k \leq a_j \leq a_i$ 。
- good subarray 的長度不會超過 $4$ 。
只需要檢查所有長度為 $3$ 和 $4$ 的 subarray 就好，所有被夾在中間的點都不能和其他點構成 bad triple ，長度 $3$ 檢查 $1$ 次，長度 $4$ 檢查 $4$ 次，答案別忘了再加上長度 $1$ 和 長度 $2$ 。
時間複雜度 $O(n)$ 。
CF 1695C
Description
Solution
DP + bitset
CF 1393C
Description
Solution
定義 $cnt_i$ 為數列 $a$ 中 $i$ 的個數， $cntcnt_i$ 為 $cnt_i$ 的個數。
計算完 $cnt$ 和 $cntcnt$ 後，找到 $x = \max\{i \mid cntcnt_i \neq 0\}$ ，我們要嘗試在 $(x-1)$ 個間隔嘗試填上其它的數字最大化 $cnt_i = x$ 這幾個數之間的間隔，因此答案為 $cntcnt_x+\frac{(n-cntcnt_x\times x)}{x-1}-1$ 。
時間複雜度 $O(n)$ 。
CF 1814B
Description
Solution
當長度為 $k$ 時總花費為 $$\left\lceil \frac{a}{k} \right\rceil+\left\lceil \frac{b}{k} \right\rceil+(k-1)$$
把上高斯去掉後用算幾不等式得到 $k=\sqrt{a+b}$ 會有最小值，但前面這樣算是假設為一維的情況，二維的情況比較複雜，我枚舉到 $k\in [1,\sqrt{2\max(a,b)}]$ 才 AC 。
時間複雜度 $O(\sqrt{\max(a,b)})$ 。