做了这套题，如果是让现在的我当时去考的话应该一共可以有 450 分，格雷码，括号树，树的重心都可以做，树上的数可以有 10 分，Emiya 至少可以有 76 分， 划分也可以有 64 分。看 OIerDB 上可以有 166 名的好成绩。

我的代码合集：洛谷 / 云剪贴板

[CSP-S2019] 格雷码

首先是格雷码有一个很好的生成方式，最低位 $0110$ 的循环，次高位 $00111100$ 的循环……

也就是说第 $i$ 位由 $2^{i}$ 个 $0$，$2^{i + 1}$ 个 $1$，再来 $2^i$ 个 $0$ 来循环，并且这与总共有多少位是没有关系的！

那么我们就可以利用这个方法生成给定的第 $k$ 个数，输出前 $n$ 位即可。

[CSP-S2019] 括号树

首先我们考虑只有一条链怎么做。

将 () 看作 $1 / -1$，做出前缀和序列。

那么对于每一个区间 $[l, r]$，为合法括号序列当且仅当 $pre_{l - 1} = pre_r$ 并且 $\min_{l \le i \le r} = pre_r$。

于是可以利用单调栈，对于每一个右端点找到满足第二个条件的区间（也就是在前面第一个 $\lt pre_r$ 后的左端点都满足第二个条件），顺便记录一下与栈顶相等的数的个数即可。

如果放在树上，我们只需要一个支持撤销的栈即可。

[CSP-S2019] 树上的数

抽象题，我只会 $n!$ 和菊花图的做法 QwQ

[CSP-S2019] Emiya 家今天的饭

首先有一个很 naive 的 $O(m n^3)$ DP，稍稍卡常应该是完全可以过的。

具体来说，我们发现之多只有一个不满足 $\le \lfloor \frac k2 \rfloor$ 的食材，那么我们枚举这个食材是什么即可。

接下来，我们设 $f_{i, j, k}$ 表示对于这个食材，考虑了前 $i$ 种烹饪方法，选择了 $j$ 种这个食材，一共选择了 $k$ 种。那么枚举这一次的选择就可以转移了。

令 $S_i$ 表示第 $i$ 种烹饪方式有多少种选择，即 $S_i = \sum a_{i, k}$，如果当前食材为 $z$，那么转移为：

$$f_{i, j, k} = f_{i - 1, j, k} + f_{i - 1, j - 1, k - 1} \times a_{i, z} + f_{i - 1, j, k - 1} \times (S_i - a_{i, z}) $$

最后我们只需要 $\sum_{j \gt \lfloor \frac k2 \rfloor} f_{n, j, k}$ 即可。

然而这极度不优秀，将 $j \le \lfloor \frac k2 \rfloor$ 转化为 $j \gt k - j$，那么我们只需要 $\sum_{j \gt k - j} f_{n, j, k}$ 即可，也就是我们只关注 $j$ 与 $(k - j)$ 的差值，那么我们按照这个作为 DP 对象即可。

$$f_{i, d} = f_{i - 1, d} + f_{i - 1, d - 1} \times a_{i, z} + f_{i - 1, d + 1} \times (S_i - a_{i, z}) $$

这就是 $O(m n^2)$ 的了，可以过。

[CSP-S2019] 划分

首先，$O(n^2)$ 的 DP 是简单的，我们只需要记录 $f_i$ 表示最小代价，$g_i$ 表示使得为最小代价最后一段的最小值。

然而我们需要 $O(n)$ QwQ，于是考虑 $a^2 + b^2 \le (a + b)^2$，也就是我们需要使得划分出的段最多，那么只需要利用一个单调队列即可。

具体来说，我们需要找到 $g_j \le pre_i - pre_j$ 的最大的 $j$，也就是 $g_j + pre_j \le pre_i$ 的 $j$ 即可，由于 $pre_i$ 是单调的，这容易利用单调队列维护。

[CSP-S2019] 树的重心

见我的另一篇文章：[CSP-S2019] 树的重心 题解