2025 XYD Summer Camp 7.25 模考
时间线
- 8:30 开题，发现 T1 昨天刚讲过做法。推式子，推到决策单调性本来想直接分治跑路，但是觉得 $n=3000$ 的 $O(n^2\log n)$ 会被卡（实则跑得飞快），于是硬着头皮被迫第一次在考场上推出并写对了斜率优化的式子，复杂度 $O(n^2)$。
- 写完 T1 是 9:30，开始奋战 T2，一开始推了一个 $O(n^22^n)$ 的假做法，写写写，过了两个小样例很开心，一测大样例发现算多了。
- 花了 inf 张草稿纸发现转移数重了很多很多，然后正确的转移是从一个集合里取一个独立集出来转移，但发现这玩意很难统计（其实恰好转至少就走上正解的路了，但是当时只是一味的红温），非常着急。
- 整个 T2 写写删删一路到了 11:30，精神崩溃，打了 7 分暴力遗憾离场。
- 最后时间看了眼 T3，因为愚蠢到我忘了 $O(n^3)$ 求最小圆覆盖导致毫无思路。
分数
题解
T1
你有 $n$ 个任务需要在第 $1\sim m$ 天中做完，并且只能按顺序做，做第 $i$ 个任务需要花 $x_i$ 个单位时间，一天可以做一段连续的任务或者不做，花的时间是做的任务的耗时之和。求 $m$ 天每天花的时间的最小方差，结果乘上 $m^2$ 输出。
$1\le m\le n\le 3000$，$\sum x_i\le 30000$。
设第 $i$ 花了 $t_i$ 的时间做任务，那么方差就是 $$ \frac{\sum_{i=1}^n(t_i-\overline x)^2}{m} $$ 其中 $\overline x=\frac{\sum_{i}x_i}{m}$，可以发现与每天具体做了哪些任务无关。考虑 dp，令 $f(i,j)$ 表示前 $i$ 天做了前 $j$ 个任务的最小方差。那么转移就是 $$ f(i,j)=\min_{k\le j}\left{f(i-1,k)+\left(\overline x-\sum_{t=k+1}^jx_t\right)^2\right} $$ 令 $s_i=\sum_{j=1}^ix_i$，那么有 $$ \begin{aligned}f(i,j)&=\min_{k\le j}\left{f(i-1,k)+\left(s_j-s_k-\overline x\right)^2\right}\&=\min_{k\le j}\left{f(i-1,k)+s_j^2+s_k^2+\overline x^2-2s_ks_j-2\overline xs_j+2\overline xs_k\right}\&=s_j^2+\overline x^2-2\overline xs_j+\min_{k\le j}\left{f(i-1,k)+s_k^2-2s_ks_j+2\overline xs_k\right}\end{aligned} $$ 令 $K_j=-2s_j,B_j=f(i-1,j)+s_j^2+2\overline xs_j$，那么原式就是 $$ f(i,j)=s_j^2+\overline x^2-2\overline xs_j+\min_{k\le j}\left{K_js_j+B_j\right} $$ 因为 $K$ 单调下降，$s$ 单调上升，因此转移具有决策单调性，可以进行斜率优化。时间复杂度 $O(nm)$。
T2
给定一张 $n$ 个点 $m$ 条边的有向图，你可以选择零条或若干条边进行反转，代价是反转的边数；求所有反转方案中，进行反转后该图没有环的所有方案的代价之和。对 $998244353$ 取模。
$n\le 18$，$m\le \frac{n(n+1)}{2}$，无重边、无自环。
没有环就意味着原图变成了一张 DAG，那么可以考虑按照类似拓扑排序进行计数。
设边集为 $E$，如果说有一种合法的反转方案是 $E’\subseteq E$，那么一定也有一种合法的反转方案是 $E-E’$，两种方案的代价和为 $m$。总方案数又总是偶数，因此总代价可以表示为：对这张 $n$ 个点 $m$ 条边的无向图的每条边定向成 DAG 的方案数再乘上 $m/2$。现在只需要考虑方案数。
设 $h(S)$ 表示对原图中点集为 $S$ 的子图进行定向，得到 DAG 的方案数。转移可以考虑类似拓扑排序的方法，不过对于一个 DAG 其拓扑序是不唯一的，但是可以用每一层取出的度数为 $1$ 的点的点集来唯一确定一个 DAG。于是我们可以取出 $S$ 中一个恰好是 $S$ 下一次会取出的一层点的点集 $T\subseteq S,T\ne \varnothing$，并且 $T$ 中没有连边（是一个独立集），设这么取的答案是 $g(S,T)$，那么有 $h(S)=\sum_{T\subseteq S,T\ne \varnothing}g(T,S)$。考虑容斥，设 $f(S,T)$ 表示 $T$ 中的节点一定是 $S$ 下一次会取出的一层点的点集，不在 $T$ 中的点不要求，那这个方案数是很好算的：把 $T$ 从 $S$ 中删去，$S-T$ 和 $T$ 中的连边全部定向为从 $S-T$ 到 $T$，剩下的只和 $h(S-T)$ 有关，因此方案数是 $$ f(S,T)=[T\text{ 是独立集}]h(T-S) $$ 根据容斥原理，因为 $f(S,T)=\sum_{T\subseteq T’}g(S,T’)$，因此有 $g(S,T)=\sum_{T\subseteq T’}(-1)^{|T’|-|T|}f(S,T’)$，带入 $h$ 的表达式中有 $$ \begin{aligned}h(S)&=\sum_{T\subseteq S,T\ne \varnothing} \sum_{T\subseteq T’}(-1)^{|T’|-|T|}[T’\text{ 是独立集}]h(S-T’)\&=\sum_{T’\subseteq S,T’\ne \varnothing,T’\text{ 是独立集}}(-1)^{|T’|}h(S-T’)\sum_{T\subseteq T’,T\ne \varnothing}(-1)^{|T|}\end{aligned} $$ 考察对于一个集合 $S$ 计算 $\sum_{T\subseteq S,T\ne \varnothing}(-1)^{|T|}$ 的值，改成枚举子集大小得 $\sum_{i=1}^n\binom{n}{i}(-1)^i$，因为 $\sum_{i=0}^n\binom ni(-1)^i=0$，因此原式等于 $-1$。那么 $h$ 的递推式就是 $$ h(S)=\sum_{T\subseteq S,T\ne\varnothing}T\text{ 是独立集}^{|T|+1}h(S-T) $$ 用 $O(3^n)$ 的方法枚举子集，时间复杂度 $O(3^n)$。求是否是独立集可以 $O(n2^n)$ 进行预处理。