今天有点摆啊。

分类

$\color{Green}{Easy}$：一眼题。

$\color{Blue}{Median}$：经过思考可以做出来。

$\color{Yellow}{Hard}$：看完题解立马理解。

$\color{Orange}{Insane}$：看完题解经过一段时间的思考能够理解。

$\color{Red}{Supreme}$：看完题解经过长久思考才理解。

P4027 [NOI2007] 货币兑换 $\color{Blue}{Median}$

考虑梭哈精神，如果卖出的话肯定全部卖出，买入则全部买入。

令 $dp_i$ 表示第 $i$ 天最多能有多少前，则可以得出以下状态转移方程：

$$dp_i = max(dp_{i - 1}, \max_{1 \leq j < i}(a_i x_j + b_i y_j)) $$

其中：

$$x_i = \frac{dp_i Rate_i}{a_i Rate_i + b_i}, y_i = \frac{dp_i}{a_i Rate_i + b_i} $$

转换为：

$$dp_i = max(dp_{i - 1}, max_{1 \leq j < i}(b_i (x_j \frac{a_i}{b_i} + y_j))) $$

使用李超线段树即可。

AT_abc416_g [ABC416G] Concat (1st) $\color{Blue}{Median}$

套路题。

CF2125E Sets of Complementary Sums $\color{Yellow}{Hard}$

转移成对长度为 $n$ 的元素两两不同的正整数序列 $a$ 计数，满足 $\min a = 1$ 且 $\sum a \leq x + 1$。

简单 $O(x \sqrt x)$ 就可以了。

P8865 [NOIP2022] 种花 $\color{Blue}{Median}$

读题时间 $\geq 15$ min。

P8866 [NOIP2022] 喵了个喵 $\color{Red}{Supreme}$

Go Die Ad-hoc！

P8867 [NOIP2022] 建造军营 $\color{Green}{Easy}$

有点板了，首先缩点，然后跑 dp 即可。