NOIP 模拟赛：2024-10-12

FLYlai / 2024-10-13 / 原文

T1：

break 忘了写，于是 -20pts

离散化，若一个段被 $\ge 3$ 个线段覆盖，无解；否则答案为 $2^{cnt}$，$cnt$ 为连通块个数。

这题卡常，要用 sort 离散化。

T2：

推式子，注意到轮数 $\le \log n$ 即可。

T3：

对于同色限制区间，若两个区间有包含关系，只需要保留小的。
把剩下的区间按 $r$ 排序。
$dp[i]$ 表示填 $1\sim i$，只满足所有右端点 $\le i$ 的区间的方案数。
我们按区间右端点的顺序枚举。假设当前枚举到区间 $k$，则我们要计算 $dp[r[k-1]+1\sim r[k]]$。设当前枚举到了 $i$。

若 $i$ 不是任何区间的右端点，$dp[i]=s\cdot dp[i-1]$；
若 $i$ 是区间的右端点（$i=r[k]$），考虑容斥。满足区间 $1\sim k$ 的方案数就是满足区间 $1\sim k-1$ 随便 $k$ 满不满足的方案数，减去满足区间 $1\sim k-1$ 不满足 $k$ 的方案数。

$1\sim k-1$ 满足、$k$ 随便的方案数很简单，就是 $dp[r[k-1]]\cdot s^{r[k]-r[k-1]}$。

$1\sim k-1$ 满足、$k$ 不满足，即强制要求 $l[k]\sim r[k]$ 全填 $b[k]$。
此时考虑与 $k$ 同色的上一个区间，记为 $k'$。若 $k'$ 与 $k$ 没有交，那么给 $l[k]\sim r[k]$ 染色 $b[k]$ 不会导致任何原本不会违规的区间变成可能违规的，因此方案数就是 $dp[l[k]-1]$。

否则因为 $l[k]\sim r[k']$ 这一段被强制染色 $b[k]$，那么前 $l[k]-1$ 个在染色时，必须保证 $l[k']\sim l[k]-1$ 这一段不全都是 $b[k]$ 色。那 "填前 $l[k]-1$ 个，满足所有右端点 $\le l[k]-1$ 的区间，且 $l[k']\sim l[k]-1$ 不全是 $b[k]$ 色" 的方案数 $S$ 是多少？

再做容斥。它的方案数为 $dp[l[k']-1]\cdot s^{l[k]-l[k']}$ 减去 $x$，$x$ 为强制 $l[k']\sim l[k]-1$ 为 $b[k]$ 且仍然满足 $\le l[k]-1$ 的区间的方案数。

再考虑与 $k'$ 同色的上一个区间 $k''$，如果没有交，$x=dp[l[k']-1]$；否则 $x=dp[l[k'']-1]\cdot s^{l[k']-l[k'']}-x'$，$x'$ 为强制 $l[k'']\sim l[k']-1$ 为 $b[k]$ 且仍然满足 $\le l[k']-1$ 的区间的方案数。

所以最终，
$S=dp[l[k']-1]\cdot s^{l[k]-l[k']}-(dp[l[k'']-1]\cdot s^{l[k']-l[k'']}-(dp[l[k''']-1]\cdot s^{l[k'']-l[k''']}-(\cdots-dp[l[k^?]-1])))$。

$dp[r[k]]=dp[r[k-1]]\cdot s^{r[k]-r[k-1]}-S$。

对每个区间 $R$，记录 $num[R]$ 等于上面那一串东西，$pre[R]$ 表示上一个与它同色的区间编号。

T4：

一种新的树的生成方式。

这个数据范围，一眼状压。考虑一颗以 $u$ 为根的树 $T$ 怎么生成：枚举 $u$ 的一个儿子 $v$，$v$ 的子树为 $T_0$，则可以先生成 $T-T_0$，然后生成 $T_0$，再连接 $u,v$。

令 $dp[T][u]$ 表示使用 $T$ 内的点构建一颗以 $u$ 为根的生成树，最小的代价是多少。
转移则枚举 $T_0,v$（显然应该有 $v\in T_0$），然后 $dp[T][u]\leftarrow dp[T-T_0][u]+dp[T_0][v]+dis(u,v)\times |T_0|\times (n-|T_0|)$.

这是 $O(3^n\cdot n^2)$ 的。考虑优化。

注意到当固定了 $u,T_0$ 时，$dp[T_0][v]+dis(u,v)\times |T_0|\times (n-|T_0|)$ 只与 $v$ 有关。考虑计算辅助数组 $p[T_0][u]=\min_{v\in T_0}\{dp[T_0][v]+dis(u,v)\times |T_0|\times (n-|T|)\}$。这可以在求出每个 $dp[S][i]$ 时，枚举 $j$ 更新 $p[S][j]$。复杂度 $O(2^n\cdot n^2)$。

于是 $dp[T][u]=\min_{T_0\subseteq T}\{dp[T-T_0][u]+p[T_0][u]\}$，复杂度 $O(3^n\cdot n)$。