2021.09.19模拟赛

应是天仙狂醉，乱把白云揉碎。

2021.09.19模拟赛

A. 背包问题

背包问题

考虑没有背包的限制就是一个二维偏序，有背包的话因为我们选出来的体积越来越大，肯定是用大背包装大物品比较优

都从大到小排序，跑一下价值上的最长上升子序列即可

code

B. 子树问题

子树问题

经典问题了属于是

不如考虑暴力多项式做法，枚举子树个数和大小，设 $F_j(x)$ 表示深度不超过 $j$ 的个数

考虑枚举子树个数并拼接，有 $F_j(x) = x\exp(F_{j-1}(x))$

（就是拼接树

$O(n^2\log n)$ 常数起飞

正常的 $dp$ 思路是考虑枚举一下子树的大小，设 $dp_{i,j}$ 表示 $i$ 个点 深度不超过 $j$ 的方案数

有 $dp_{i,j} = \sum dp_{i-k,j}\times dp_{k,j-1} \times\binom{i-2}{k-1}$

就是在 $i-k$ 的基础上插入一个新的大小为 $k$ 的子树，为了保证不计重，需要让 $k$ 的根标号是 $2$

而给剩下的点分配标号就是 $\binom{i-1-k+k-1}{k-1}=\binom{i-2}{k-1}$

code

C. 括号序列

括号序列

带颜色括号的合法字串个数

考虑 $O(n^2)$ 暴力，每个点开个栈往后扫，碰到一个同色的能弹就弹，栈空了就合法

那么如果我从 1 开始记录栈，如果有两个栈的状态一样，说明清空了，有 $n$ 个就是任选两个 $\binom{n}{2}$

code

D. 倾斜的线

倾斜的线

懒了，不想写式子了

通分一下能够发现把每个点写成 $(Qy-Px,Qx)$ 的形式

就是找最小斜率，排序扫一遍就行

code