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

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

Day1 T1 树 (tree)

题面：

http://218.5.5.242:9019/problem/364。

题解：

假如只有一个点被占领了，那么我们以这个点为根，可以列出以下的 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)$ 分别单调递增和单调递减，于是答案就是一个下凸函数。但是这个东西不能三分，因为会由平台，只能采取二分（类似冰火战士）。

Day1 T2 最小生成树 (mst)

题面：

http://218.5.5.242:9019/problem/365。

题解：

我们对每条边建一个虚点；最小生成树的条件相当于每条非树边都要大于环上的每条边；我们把所有的大小关系都连边，这张图会是一张二分图，从左部的 $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 最优解。

Day1 T3 矩阵 (matrix)

鸽鸽鸽

Day2 T1 子序列 (subseq)

简要题意：

给定一个长度为 $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|$。

Day2 T2

不会

Day2 T3 Pajel 游戏 (pajel)

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

1. 一定要先手玩比较小的点。
2. 模拟退火在范围过大时也是撑不住的，可以考虑加入一些乱搞的限制条件，比如这题中把每个连通块的中间部分都涂成一样的颜色。

Day3 T1 她的名字 (name)

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

Day3 T2 选拔赛 (game)

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

Day3 T3 树 (tree)

我们考虑以深度最低的点为子树的代表节点，一开始我们有 $n$ 个子树，然后我们建一个总的堆，每次取出最小的那个子树来进行拓展；为了维护拓展，我们对于每棵子树再建一个堆，然后每次拓展的时候把堆复制一遍。

直接这样实现是 $O(n^2\log_2 n)$ 的，可以通过；利用可持久化可并堆就可以做到严格 $n\log_2 n$，是不是吊打标算呀？