T1

Description

给一个数列，长度为 $10^5$ 。划成 $20$ 段，每段权值为 #$\{i,j|a_i=a_j\}$。要求最小化权值和。

Solution

考虑 DP 。设 f[i][j] 表示把序列划成 $i$ 段，最后一段的最后一个位置为 $j$ 的最小权值。
可以得到转移方程：

$f_{i+1}[j]=f_i[k]+\text{val}(k+1,j)$

其中 $\text{val}(l,r)$ 表示 #$(i,j|a_i=a_j,l\leq i\leq j\leq r)$ 。

转移的形式大概就是 $f_i[1\sim n]\rightarrow f_{i+1}[1\sim n]$ 。
假设 $\text{pos}_k$ 表示 $f_{i+1}[k]$ 是由 $f_i[\text{pos}_k]$ 转移而来，那么有个结论：pos[] 数组单调不降。也就是 决策单调性 。
对于决策单调性的 DP ，我们可以分治处理。先暴力处理 $f_{i+1}[\text{mid}]$ 的转移位置，再递归左右两边。容易发现单次转移复杂度是 $\mathcal{O}(n\log_2)$ 的。

现在的问题就在于如何处理 $\text{val}$ 函数。暴力预处理是 $\mathcal{O}(n^2)$ 的，不可取。
$\text{val}$ 函数有个好用的性质：我们可以快速由 $\text{val}(l,r)$ 推出 $\text{val}(l\pm 1,r\pm 1)$ 。于是我们可以在分治的时候暴力地移动左右端点。如果把两个端点先从父亲层移动到左儿子层，再从左儿子层移回父亲层，再移动到右儿子层这整个过程的移动次数全部计入父亲层的话，两个端点在每一层的移动次数明显是 $\mathcal{O}(n)$ 的，所以单次转移的复杂度也是 $\mathcal{O}(n\log_2n)$ 的。

总复杂度 $\mathcal{O}(20n\log_2n)$ 。

设置状态有技巧。划段的 DP 状态一般都是设第几段和最后一段的最后一个元素。
要学会三个方法：决策单调性的判定；决策单调性的分治方法；$f(x,y)$ 形式的函数暴力移动指针计算。

T2

Description

一维数轴上，一个人移动速度为 $1$ 。建立新分身（不消耗时间）即摧毁旧分身，分身保持在原地不动。
给定 $q$ 个要求，限制此人或此人的分身在 $t_i$ 时刻必须在 $x_i$ 。
$q\leq 5\times 10^3,t_i,x_i\leq 10^9$

Solution

设 f[p][i] 表示人在 $p$ 处时分身是否能在 $i$ 处，g[p][i] 表示分身在 $p$ 处时人是否在 $i$ 处。然后按照时间顺序 DP ，可以根据前后是什么满足要求分类为人到人、人到影子、影子到人、影子到影子。四种情况分开讨论转移。

T3

Description

长为 $10^5$ 的闭区间序列。要求选一个最长子序列。使得该子序列，存在一种方案：

• 每个区间保留一个数
• 保留的数严格递增

Solution

最长单调上升子序列的加强版。状态的设置也可以从 $\text{LIS}$ 的状态上考虑。
令 dp[i][j] 表示考虑了前 $i$ 个数时，拼出 $j$ 个子序列时右端点可选的最小值。
显然 dp[i] 数组是单调递增的。每次转移时是将一段 dp[i] 赋值为 dp[i-1] ，并将某个 dp[j]设为当前区间左端点。可以用平衡树来维护。

T4

Description

$10^5$ 个点的树，随机断 $k$ 条边，求连通块大小的平方的和的期望。

Solution

Codechef 上一道著名的题目。
连通块大小的平方的和的期望就是任意两点连通的概率之和。
这个东西可以这么考虑：假设有一个大小为 $\text{sz}$ 的连通块，那么其贡献为

$\sum_{i=1}^{\text{sz}}1\sum_{j=1}^{\text{sz}}1$

也就相当于是拆若干个点对的和了。
长度相同的链贡献是一定的，于是就转化为统计有多少长度为 $i$ 的链。点分治即可。

这个方法可以扩展到更高的幂次，但是需要增添一些组合系数。
例如，如何求答案的 $p$ 次方的和的期望呢？
首先这玩意就是选出任意 $p$ 个点（可以相同）最后连通的概率的和。
我们先限制点之间不同。枚举点集 $S(|S|\in [1,p])$ ，那么每个点集造成的贡献为

${p\brace |S|}|S|!$

因为第一次选择 $a$ 第二次选择 $b$ 和第一次选择 $b$ 第二次选择 $a$ 是两种不同的情况，所以我们将每次选择视为不同的，故选择第二类斯特林数。同时，我选择 $a$ 和选择 $b$ 当然是不同的$(a\not ={b})$ ，所以再乘上阶乘。
可以发现点集的贡献只与点集的大小和点集连通的概率有关，考虑 DP 。
我们把每个点集的贡献在点集的 $\text{LCA}$ 处计算。设 dp[i][j] 表示 $i$ 子树内，所有的大小为 $j$ 并且至少还有一个点在 $i$ 的祖先（包含自己）的点集连通的概率和。
点集中每条边在最终时刻不被删的概率是相互依赖的，并不独立，所以需要再记一维 ，表示当前已经保留了多少条边。转移时背包合并即可。每次转移大概就是

$f[i][j+k][x+y+1]=\frac{n-1-(x+y)-k}{n-1-(x+y)}\times \sum_{j}\sum_{k}f[u][j][x]\times f[i][k][y]$

T5

Description

给定一棵有 $n$ 个节点的树。定义点集 $S$ 的权值为

$f(S)=\min_{u\in V}(\sum_{v\in S}\text{dis}(u,v))$

求 $\sum_{|S|=m}f(S)$ ，答案对 $10^9+7$ 取模。
$1\leq n,m\leq 10^6$

Solution

自然可以想到 $u$ 就是点集 $S$ 的重心，于是枚举每个 $u$ 来计算贡献。$u$ 连接的所有连通分量中在 $S$ 中的点至多只能占到 $|S|$ 的一半。这个条件的反面（大于一半）只有一个连通分量可以做到，可以容斥来计算。
但这样子颇麻烦。我们换成考虑边的贡献。
对于一条边 $e$ ，假设 $e$ 的左边有 $a$ 个点，右边有 $b$ 个点，那么 $e$ 的贡献就是 $\min(a,b)$ 。
然后答案式子就出来了。假设边 $e$ 一侧连 $A$ 个点。

$\sum_{e}\sum_{a=1}^{m-1}\min(a,m-a)\binom{A}{a}\binom{n-A}{m-a}$

每条边的贡献只与 $A$ 有关。我们把右边一堆东西记为 $F(A)$ 。
钦定最小值为 a 或者为 m-a 以去掉 $\min$ 。可以得到（令 $p=\frac{m-1}{2}$）

$\begin{aligned} F(A)&=\sum_{a=1}^{p}a\binom{A}{a}\binom{n-A}{m-a}\\ &=A\sum_{a=1}^{p}\binom{A-1}{a-1}\binom{n-A}{m-a} \end{aligned}$

考虑右边的东西的组合意义：要在 $n-1$ 个物品中选 $m-1$ 个物品，其中在前 $A-1$ 个物品中至多选择 $p-1$ 个。
显然从 $F(A)\rightarrow F(A+1)$ 若有变化，只可能增加一个临界值。所以就可以 $\mathcal{O}(n)$ 求了。

T6

Description

给一棵 $n$ 个点的树和一个 $m$ 个元素的集合。集合的元素为祖先后代关系的链。随机顺序删点，求期望多久集合里所有的链都被破坏。
$n,m\leq 300$

Solution

Min-Max 容斥转化为求对于每个子集而言第一次被选中的期望时间。设 f[i][j][k] 表示第 $i$ 个点的子树内，选择的链的点集并有 $j$ 个，经过 $i$ 的链中顶端的最大深度为 $k$ 时，这个链集的贡献。转移时 $j$ 维做加卷积，$k$ 维做 $\text{max}$ 卷积，并且带容斥系数。