省队集训 2021 简要题解（Day1、2、3）

假如只有一个点被占领了，那么我们以这个点为根，可以列出以下的 DP 方程：

f_u=\min_{s\in son_u}{\{f_s+\sum_{v\in son_v-s}[v\le s]\}}

$n\log_2 n$ $a$ $b$ 走。

$g(u)$ $h(u)$ $u$ 为断点时两颗树分别的最小步数，于是答案就是：

\min_{u\in (a\rightarrow b)}{\max(g(u),h(u))}

$g(u)$ $h(u)$ 分别单调递增和单调递减，于是答案就是一个下凸函数。但是这个东西不能三分，因为会由平台，只能采取二分（类似冰火战士）。

$n-1$ $m-n+1$ 个点。

$f_{S,i}$ $S$ $i$ $h_{S,i}$ 为权值和。于是有：

f_{S,i}=\sum_{u\in S,j\in[0,g_{S-u}]}f_{S-u,j}\cdot\frac{(g_S-j)!}{(g_S-i)!}\\ h_{S,i}=\sum_{u\in S,j\in[0,g_{S-u}]}\left(h_{S-u,j}+f_{S-u,j}\cdot i\right)\cdot\frac{(g_S-j)!}{(g_S-i)!}\\

$g_S$ $S$ 点集的导出子图中有多少条非树边，可以通过 FMT 求出。这个做法复杂度巨大，不可过。

我们考虑把边反过来，这样就能去掉第二维；于是可以得到：

f_S=\sum_{u\in S}f_{S-u}\cdot\pmatrix{|S|+m-n-g_{U-S}\\g_{U-S-u}-g_{S-U}}\cdot(g_{U-S-u}-g_{S-U})!\\ h_S=\sum_{u\in S}h_{S-u}\cdot\pmatrix{|S|+m-n-g_{U-S}+1\\g_{U-S-u}-g_{S-U}+1}\cdot(g_{U-S-u}-g_{S-U}+1)!\\\ \ \ \ \ \ \ \ \ \ \ \ \ +f_{S-u}\cdot\pmatrix{|S|+m-n-g_{U-S}\\g_{U-S-u}-g_{S-U}}\cdot(g_{U-S-u}-g_{S-U})!\cdot (|S|+m-n-g_{U-S}+1)\\

目前这个做法是 AHSFNU OJ 最优解。

鸽鸽鸽

$n$ $s$ $q$ $l,r$ $s[l,r]$ 中有多少本质不同的子序列。
$10^9+7$ 取模。

DP $f_{i,j}$ $i$ $j$ 结尾的子序列个数，于是我们有：

f_{i,j}=[j=s_i]\sum f_{i-},k+[j\neq s_i]f_{i-1,j}

$A_i$ ，于是我们就是要求（暂且假设只有两个字符）：

[1,1,1]\cdot A_r\times A_{r-1}\times \cdots A_l\times\left[\matrix{1\\1\\1}\right]

于是我们可以矩阵求逆一下：

[1,1,1]\cdot A_r\times A_{r-1}\times \cdots A_1\times A_1^{-1}\times A_2^{-1}\times \cdots\times A_{l-1}^{-1}\left[\matrix{1\\1\\1}\right]

$n|\Sigma|^2+q|\Sigma|$ $n|\Sigma|+q|\Sigma|$ 。

不会

借这题讲一下提交答案题的常规做法：

直接在后缀树上线段树合并即可，比较 Trivial。

一定是由一段前缀和最大值组成，直接 0.618 法三分即可通过。注意，导数二分比直接三分来得更优秀。

$n$ 个子树，然后我们建一个总的堆，每次取出最小的那个子树来进行拓展；为了维护拓展，我们对于每棵子树再建一个堆，然后每次拓展的时候把堆复制一遍。

$O(n^2\log_2 n)$ $n\log_2 n$ ，是不是吊打标算呀？