选择性记录

· · 个人记录

P5369

想法还是比较接近的。注意到 n 很小，考虑枚举集合 S 作为最大前缀和的排列数，那么这个排列应该有两个特点：

对于 1 \leq i \leq |S|，所有后缀和都 \geq 0；对于所有 |S|+1 \leq i \leq n，所有前缀和 <0。

考虑把两个特点分开处理，令 f_i 表示选定集合为 i，满足第一个特点的方案数，g_i 表示满足第二个特点的方案数。转移是平凡的，时间复杂度 \text{O}(n2^n)。

P5811

不妨假设 a \leq b \leq c，那么就有 a \leq \frac{1}{3}n,b \leq \frac{1}{2}n。我们考虑去选出大小为 a,b 的连通块，一定不劣。

先考虑树的情况，考虑以重心为根，那么对于 a 的连通块一定不经过根，即有解的条件为：存在大小超过 \frac{n}{3} 的子树。

然后考虑扩展到图的情况，横叉边会将生成树中的若干个子树连接，考虑找到这样的 siz \geq a 的连通块，此时可以说明有解，在这个过程中，该连通块一旦存在大小 \leq 2a，剩余部分 \geq n-2a，由于 n=a+b+c，那么有 n-2a=b+c-a \geq b，故有解。