WC 赛前训练日志 1

Yet Another DAG Problem

给出一个$n$个点$m$条边边带权 DAG，构造序列$a_1,\ldots,a_n$使得

• $a_i> 0$。
• $\forall (u,v,w) \in E, a_u>a_v$。

并最小化$\sum_{(u,v,w)\in E}(a_u-a_v)w$。

$n\le 18,m\le \frac{n(n-1)}{2}$。

状压

首先这题可以 LP，但鉴于$n$较小，有点大材小用。考虑状压。

由于是 DAG，我们将它整理为分层图的形式，相邻层的距离为$1$。把代价拆分到相邻层上即可。

设$f(S)$表示，$G[S]$（$S$的导出子图）的最小代价。转移时我们枚举下一层的点集$T$，使得$S,T$不相交且

• $\forall u\in T$，要么$u$是一个入度为$0$的点，要么$\exists\,v\in S,\,(v,u)\in E$。

新增的代价就是跨过$S,T$的边权的和：

$$f(S\cup T) \gets f(S) + \sum_{u\in S,v\in T,(u,v,w)\in E}w$$

在 DP 的过程中构造方案即可。

复杂度$O(3^n+2^nn^2)$，有一些预处理。

代码

Roads and Ramen

给出一棵$n$个点的无根树，边有黑白两种颜色。有$m$次操作，每次操作选择一条边反转它的颜色。每次操作后求黑边个数为偶数的最长简单路径的长度。

$n\le 5\times 10^5,m\le 5\times 10^5$。

直径

有两个做法。一个是性质做法，一个是套路做法。

算法一

假设树的直径是 AB。

那么若 AC 和 BC 奇偶性相同，则答案就是 AB。

否则假设最优解是 EF。那么有 CE 和 CF 的奇偶性相同。因为 AC 和 BC 奇偶性不同，不妨假设 AC 和 CE 奇偶性相同。因为 AB 是直径，所以$FC\le AC$，所以$FD\le AD$，所以$EF\le AE$。因此选 AE 不劣。

另一种$A-C_1-C_2-B$，然后$E-C_1$，$F-C_2$的情况也可以类似地证明。证明的关键点是$A-C_1$和$B - C_2$奇偶性相同，而$E-C_1$，$F-C_2$奇偶性不同。

这样我们就证明了，存在端点是直径端点的最优解。那么维护两棵树的到根路径最优解即可。这个很容易维护。

时间复杂度$O((m+n)\log_2n)$。

算法二

如何求直径？设$d_u$表示深度。那么我们要求的就是$\max_{u,v}\{ d_u+d_v-2d_{\text{lca}(u,v)} \}$。但是$\text{lca}$不是一个容易求的东西。考虑欧拉序。那么$\text{lca}(u,v)$一定在$u$到$v$的欧拉序中出现过。因此直径就转化为了$\max_{X_u\le w\le X_v}\{ d_u+d_v-2d_w \}$。

考虑线段树。对区间维护$\max d_u$，$\max_{X_u\le w}\{ d_u - 2d_w \}$和$\max_{w\le X_u}\{ d_u - 2d_w \}$。然后两个区间合并一下即可。

对于本题，加一个奇偶性讨论上去即可。

时间复杂度$O((m+n)\log_2n)$。

防御工事

给出一个$n$个点$m$条边的连通图。$q$次询问：

• 第$i$次询问给出$k_i$个点。要求你在图上选择一个点$u$使得：等概率随机选择不是$u$的$n-1$个点中的一个点$v$，这$k_i$个点中存在不经过$v$到达$u$的路径的点的个数的期望最大。

• 输出这个最大的期望乘上$n-1$的值。

$n\le 2\times 10^5, m\le 5\times 10^5, q\le 5\times 10^5,\sum k_i\le 5\times 10^5$。

圆方树 虚树 换根 DP

建出圆方树。$x$能不经过$v$到达$y$等价于圆方树上$x$能不经过$v$到达$y$。

以$u$为根。称询问的点是关键点。则不能（不经过$v$）到达$u$的点有且仅有$v$子树中的点。

因此圆方树上建虚树，虚树上换根即可。

时间复杂度$O(\sum k_i + n+m)$。

代码

微信步数

考虑$k$维空间里的一个超立方体空间$[1,w_1]\times [1,w_2]\times\cdots \times [1,w_k]$（以下简称空间）。给出一个长度为$n$的二元组序列$(c_i,d_i)$满足$1\le c_i\le k$，称为行动序列。

对于一次从$(x_1,\ldots,x_k)$出发的行动，我们会循环执行行动序列，第$i+nk$步我们会执行二元组$(c_i, d_i)$代表的行动，即$x_{c_i} \gets x_{c_i} + d_i$，直到走出了空间就停止。

求以空间中的每个点为起点行动的步数的和。

$n\le 5\times 10^5, k\le 10, w_i\le 10^9, d_i\in \{1,-1\}$。

rounding box 高维空间 差分 自然数幂

对于一个行动序列，定义它的 rounding box 是每一维坐标在变化过程中的极差区间构成的超立方体空间，定义它的行动向量是每一步行动的向量和。感性理解一下。

用两个向量$(l_1,\ldots,l_k)$（减向量）和$(r_1,\ldots,r_k)$（增向量）表示整个行动序列的 rounding box，其中$l_i$表示第$i$维坐标的最大减量，$r_i$表示最大增量。同时用$\textbf{v}$表示它的行动向量。

为了方便叙述和实现，我们先对行动序列处理一下，使得$\mathbf{v}$的每一维都非负。直观的说，让$\mathbf{v}$的方向指向“右上角”。这样的变换不影响答案。

考虑走不超过$n$步就走出场地的点。可以枚举$i$，计算走恰好$i$步走出空间的点数，也就是【前$i-1$步的 rounding box 在空间内】的点数减去【前$i$步的 rounding box 在空间内】的点数。

接下来考虑不属于上述类的点。

行动的过程可以概括为：从起点$x$出发，先走若干次（可能为$0$）行动向量到达一个点$y$，然后走$n+j$步（$1\le j\le n$）走出空间。

为什么要这么分类

如果我们将行动过程概况为：从起点$x$出发，先走$t$次（可能为$0$）行动向量到达一个点$y$，然后走$j$步（$1\le j\le n$）走出空间。

那么就会发现：当$t=0$和$t=1$对应的$y$的点集之间的关系不能简单地用$\mathbf{v}$的信息表示，因此难以合并计算。

接下来考虑$y$的分布。固定$j$。

要求从$y$点恰好在$n+j$步走出空间，合法的$y$的个数相当于【前$n+j-1$步的 rounding box 在空间内】的点数减去【前$n+j$步的 rounding box 在空间内】的点数。差分$y$的分布，将问题转化为：$y$分布在一个超立方体内，求所有$y$的贡献和。

考虑分布在【走$n+j$步的 rounding box】的$y$的贡献。一个$y$的贡献可拆分为：

• 从$y+\mathbf{v}$走$j$步走出边界的贡献和。
• 从$x$走到$y+\mathbf{v}$的贡献和。

容易发现，【走$n+j$步的 rounding box】的减向量与原行动序列的减向量相同，仍是$(l_1,\ldots,l_k)$。用$(r'_1,\ldots,r'_k)$表示其增向量。

则$y$的限制是$l_i< y_i \le w_i - r'_i$。

第一部分

为了计算从$y+\mathbf{v}$走$j$步走出边界的贡献和，我们要先考虑有多少个$x$能走到$y$。

考虑固定$y$，计算有多少个可以到达$y$的起点$x$。那么$x$的限制是$x_i > l_i$（$1\le i\le k$），此外$x+t\mathbf{v} = y$（$t\ge 0$）。这样的$x$的个数是

$$f(y) = \min_{1\le i\le k}\left\lfloor \frac{y_i-l_i-1}{\mathbf{v}_i}\right\rfloor+1$$

考虑从$y+\mathbf{v}$走$j$步走出边界的贡献和，即：

$$j\times \sum_{y_1=l_1+1}^{w_1-r'_1} \sum_{y_2=l_2+1}^{w_2-r'_2}\cdots \sum_{y_k=l_k+1}^{w_k-r'_k} f(y)$$

记$p_i = w_i-r'_i-l_i-1$。上式可以化简为$j\times \sum_{t\ge 0} \prod_{i=1}^k\max(0,p_i-t\mathbf{v}_i+1)$。

化简过程

$$\begin{aligned} &\sum_{y_1=l_1+1}^{w_1-r'_1} \sum_{y_2=l_2+1}^{w_2-r'_2}\cdots \sum_{y_k=l_k+1}^{w_k-r'_k} \min_{1\le i\le k}\left\lfloor \frac{y_i-l_i-1}{\mathbf{v}_i}\right\rfloor+1\\ =& \sum_{y_1=0}^{p_1} \sum_{y_2=0}^{p_2}\cdots \sum_{y_k=0}^{p_k} \min_{1\le i\le k}\left\lfloor \frac{y_i}{\mathbf{v}_i}\right\rfloor+1 \\ =& \sum_{t\ge 1} \sum_{y_1=0}^{p_1} \sum_{y_2=0}^{p_2}\cdots \sum_{y_k=0}^{p_k} \left[\min_{1\le i\le k}\left\lfloor \frac{y_i}{\mathbf{v}_i}\right\rfloor+1\ge t \right] \\ =& \sum_{t\ge 0} \sum_{y_1=0}^{p_1} \sum_{y_2=0}^{p_2}\cdots \sum_{y_k=0}^{p_k} \left[\min_{1\le i\le k}\left\lfloor \frac{y_i}{\mathbf{v}_i}\right\rfloor \ge t \right] \\ =& \sum_{t\ge 0} \sum_{y_1=0}^{p_1} [y_1 \ge t\mathbf{v}_1] \sum_{y_2=0}^{p_2} [y_2 \ge t\mathbf{v}_2]\cdots \sum_{y_k=0}^{p_k} [y_k \ge t\mathbf{v}_k] \\ =& \sum_{t\ge 0} \prod_{i=1}^k\max(0,p_i-t\mathbf{v}_i+1) \end{aligned}$$

考虑如何计算上式。容易发现当存在$p_i-t\mathbf{v_i} < 0$时整个式子的值就是$0$。因此可以把$\max$去掉。

设$q = \min_{1\le i\le k}\lfloor\frac{p_i+1}{\mathbf{v}_i}\rfloor$，则上式可以化简为$j \sum_{t = 0}^q \prod_{i=1}^k(p_i-t\mathbf{v}_i+1)$。

连乘积可以看作一个关于$t$的$k$次多项式$F(x) = \sum_{i}f_ix^i$，则可以化简为$j\sum_{i=0}^kf_i\sum_{t = 0}^qt^i$。

后者是个$k$次前缀和的式子。可以$O(k^2)$预处理$O(k)$计算。

计算过程

设$f(n,k) = \sum_{i=0}^n i^k$。考虑差分，定义$f_0(n,k) = f(n,k), f_i(n,k) = f_{i-1}(n,k) - f_{i-1}(n-1,k)$（$i>0$）。差分$k+1$次，就会变成常数序列。

那么用$f_i(i,k)$计算对$f(n,k)$的贡献即可。容易发现这是个格路计数问题。

因此可以$O(k^2)$预处理$O(k)$计算。

第二部分

考虑从$x$走到$y+\mathbf{v}$的贡献和。枚举走了$t$轮行动序列到$y$（即$x+t\mathbf{v} = y$）。同时我们要求$l_i<x_i$，因此贡献和为

$$n\times \sum_{t\ge 0}(t+1)\sum_{y_1=l_1+1}^{w_1-r'_1} \sum_{y_2=l_2+1}^{w_2-r'_2}\cdots \sum_{y_k=l_k+1}^{w_k-r'_k} \prod_{i=1}^k [y_i - t\mathbf{v}_i> l_i]$$

化简得到$n\sum_{t\ge 0}(t+1) \prod_{i=1}^k(p_i - t\mathbf{v}_i + 1)$。

化简过程

$$\begin{aligned} &\sum_{t\ge 0}(t+1)\sum_{y_1=l_1+1}^{w_1-r'_1} \sum_{y_2=l_2+1}^{w_2-r'_2}\cdots \sum_{y_k=l_k+1}^{w_k-r'_k} \prod_{i=1}^k [y_i - t\mathbf{v}_i> l_i] \\ =& \sum_{t\ge 0}(t+1)\sum_{y_1=0}^{p_1} \sum_{y_2=0}^{p_2}\cdots \sum_{y_k=0}^{p_k} \prod_{i=1}^k [y_i \ge t\mathbf{v}_i] \\ =& \sum_{t\ge 0}(t+1) \prod_{i=1}^k(p_i - t\mathbf{v}_i + 1) \end{aligned}$$

可以用与第一部分类似的方法处理。

算上枚举$j$的复杂度，总复杂度$O(nk^2)$。

代码

烟花表演

给出一棵$n$个点边带权的有根树。要求改变边的长度使得所有叶子结点的深度相同。将一条长度为$w$的边改成$w'$的代价是$|w-w'|$（$w'\ge 0$）。

$n\le 6\times 10^5, w_i\le 10^9$。

凸函数 拐点 可并堆 DP

设$f_u(x)$表示将结点$u$子树的叶子到$u$的距离调整为$x$的最小代价。用$s(u)$表示$u$的儿子结点集合，那么我们可以将转移过程分成两个部分：

• 把$u$连一条长度为$w$的边到它的父亲。即设$g_u(x)$表示把$u$的儿子调整到$u$的父亲距离为$x$的最小代价，那么$g_u(x) = \min_{0\le i \le x}\{ f_u(i) + |w-x+i| \}$。
• 将$u$的儿子的贡献合并：$f_u(x) = \sum_{v\in s(v)}g_v(x)$。

为了高效维护这两种操作，我们需要重点分析第一个转移的性质。

感性理解一下，$f_u$其实是$O(n+m)$个绝对值函数的“和”，可以认为$f_u$具有凸性（下凸壳）。算法的过程会证明这一点，因此我们先认为它是对的。

同样显然的是，$f_u$是个直线围成的凸壳，直线的斜率是整数。

分析$g_u$的转移。为了方便叙述，省略下标$u$。

固定$x$，则$|w-x+i|$取到最小值当且仅当$i=x-w$。另一方面，不妨设$f$的最小值区间是$[L,R]$。

注意到绝对值函数顶点两边的斜率是$-1$和$1$，而$f$函数$L$左边的斜率$\le -1$，$R$右边的斜率$\ge 1$。换言之我们应当优先满足$f$的最优性再考虑绝对值函数的最优性。

对于转移式

$$g(x) = \min_{0\le i \le x}\{ f(i) + |w-x+i| \}$$

• 当$x < L$时，$f(i)$为最小值的条件是$i=x$。因此有$g(x) = f(x) + w$。
• 当$L\le x < L+w$时，$f(i)$为最小值的条件是$L\le i < \min(L+w,R+1)$。而注意到$x-w<L$，因此当$i=L$时$f$取到最小值，绝对值函数取到极小值，即$g(x) = f(L) + w-x+L$。
• 当$L+w \le x\le R+w$时，让$i=x-w$可以使$f$和绝对值函数同时取到最小值，则$g(x) = f(x-w) = f(L)$。
• 当$R+w < x$时，让$i=R$可以使$f$取到最小值，此时绝对值函数取到极小值，则$g(x) = f(R) + |w-x+R| = f(L) + x-w-R$。

接下来考虑怎么维护$f$。

上述过程的实质是平移、加一段斜率为$-1$的直线、将凸壳的右边替换为斜率为$1$的直线。

考虑用可重集维护拐点的横坐标。一个拐点会导致其右边的斜率加$1$。再维护一下最后一个拐点右边的斜率$k$，就可以表示整个凸包了。

• 对于第一种转移，我们只需要找到一个$L$和$R$（$L$不唯一，$R$唯一），然后将$R$右边的拐点删掉，将$L$和$R$分别变成$L+w,R+w$即可，然后把$k$改成$1$。将一个$L$变成$L+w$相当于加一段斜率为$-1$的直线。

• 对于第二种转移，相当于点值相加，那么合并可重集，$k$相加即可。

为了维护上述可重集，我们还需要支持：找到$L$和$R$。这个并不难。由于一个拐点会导致其右边的斜率加$1$，而我们知道最后一个拐点右边的斜率，那么我们可以删除横坐标最大的$k-1$个拐点就可以找到$R$，然后再删$R$就可以找到$L$。

一个拐点右边的斜率恰好等于$u$的儿子数，因此复杂度有保证。

最后考虑如何计算答案。我们知道$f(0)$等于边长之和，这样就可以计算出$f(L)$处的点值了。

不妨用可并堆维护可重集。时间复杂度$O(n\log_2n)$。

代码

硬件包管理器

有$n$个三元组$(t_i,a_i,b_i)$和$m$个限制，第$j$个限制形如$(l_j,r_j)$，表示要求将区间$[l_j,r_j)$的三元组的$t$调整为$\ge t_{r_j}$。将$t_i$调整为$t'_i$的代价是$a_i\max(t_i-t'_i,0) + b_i\max(t'_i-t_i,0)$。

求满足所有限制的最小调整代价。

$n\le 3\times 10^5, m\le 3\times 10^5$。

凸函数 拐点 可并堆 DP

限制可以处理成树形结构。接下来就和烟花表演的思路类似了。

设$f_u(x)$表示让子树$u$的$t$都$\ge x$的最小代价。有

• $g_u(x) = \sum_{v\in s(u)} f_v(x)$。
• $f_u(x) = \min( \min_{x\le i\le t_u}g_u(i)+(t_u-i)a_u, \min_{i\ge t_u,i\ge x} g_u(i) + (i-t_u)b_u )$。

第二个转移可以理解为，给$g_u$加上一个类绝对值函数，然后把斜率小于$0$的部分改成水平直线。

相当于加一个横坐标为$t_u$的拐点。

这次我们用二元组$(x,y)$表示拐点的横坐标以及这个拐点对斜率的增量。就可以用可并堆维护了。

这题的可并堆是小根堆。求答案的时候用$f(10^5)$减掉差值。

代码

寿司早餐

给出$n$个$d$位线性基$B_1,\ldots,B_n$，问他们的张成空间的并（去重）的第$k$大。

$n\le 12, d\le 50, k\le 10^{18}$。

线性基 线性基合并 容斥

数理题。

记线性基$B$张成的线性空间为$V=\text{span}(B)$。

我们要求的是$U = \text{span}(B_1)\cup \cdots \cup \text{span}(B_n)$中的第$k$大。

可以转化为，枚举$i$，固定前缀$\overline{u_1\ldots u_i}$，求$U$中以$\overline{u_1\ldots u_i1}$为前缀的向量的个数。

计数问题可以容斥，则枚举$[n]$的子集$S$，求$\bigcap_{j\in S}\text{span}(B_j)$中以$\overline{u_1\ldots u_i1}$为前缀的向量的个数。

引理 1：两个线性空间的交仍是线性空间。

证明

对于两个线性空间$V_1,V_2$，如果向量$a,b$满足$a,b\in V_1\cap V_2$，则有$a\oplus b\in V_1$，$a\oplus b\in V_2$，则$a\oplus b \in V_1 \cap V_2$。

因此问题转化为如何求两个线性空间交的线性基。

引理 2：对于两个线性基$B_1,B_2$，设$W=\{v \in B_2 | v\in \text{span}(B_1)\}$，即$B_2$中能被$B_1$表示的向量基。若$\text{span}(B_1)\cap \text{span}(B_2\setminus W) = \varnothing$，即$B_1$与$B_2\setminus W$线性无关，则$W$是$\text{span}(B_1)\cap \text{span}(B_2)$的一组线性基。

设$B_1 = \{a_1,\ldots,a_x\}$，$B_2=\{b_1,\ldots,b_y\}$。

证明

不妨设$W = \{b_1,\ldots,b_z\}$（$z\le y$）。

对于任意向量$v\in \text{span}(B_1)\cap\text{span}(B_2)$，$v$能被$a_i$和$b_i$分别表示。

假设$v = \sum A_ia_i = \sum B_ib_i$，那么$\sum A_ia_i - \sum_{i\le z}B_ib_i = \sum_{z<i\le y}B_ib_i$。

式子的左边是用$B_1$和$W$表示的，式子的右边是用$B_2\setminus W$表示的。

由于$W$可以被$B_1$表示，因此左边可以只用$B_1$表示。

因为$B_1$与$B_2\setminus W$线性无关，因此等式右边必须为$0$，否则等式不可能成立。

注意到这个等式是对任意$v\in \text{span}(B_1)\cap\text{span}(B_2)$成立的。换言之对任意$v\in \text{span}(B_1)\cap\text{span}(B_2)$都有等式的右边为$0$。

因此$B_i = 0$（$z<i\le y$），因此$v=\sum_{i\le z}B_ib_i$，即$v$可以被$W$表示，即$v\in\text{span}(W)$。

因此$\text{span}(B_1)\cap\text{span}(B_2) = \text{span}(W)$。

但问题在于，对于两个线性基$B_1,B_2$，并非总是存在$W=\{v \in B_2 | v\in \text{span}(B_1)\}$使得$B_1$与$B_2\setminus W$线性无关。因此我们需要构造一个线性基$B_2'$，使得$\text{span}(B_2) = \text{span}(B_2')$且对于$W'=\{v \in B'_2 | v\in \text{span}(B_1)\}$，有$B_1$与$B_2'\setminus W'$线性无关。

设$B_2' = \{c_1,\ldots,c_y\}$。对于$b_i$：

• 如果它能被$a_1\ldots,a_x, b_1\ldots,b_{i-1}$线性表出，那么随便取一种表出方案，设$b_i = p_1a_1+\cdots + p_xa_x+q_1b_1+\cdots + q_{i-1}b_{i-1}$，那么令$c_i = p_1a_1+\cdots + p_xa_x$。
• 否则，令$c_i = b_i$。

构造的正确性

首先证明$B_1$与$B_2'\setminus W'$线性无关。

这是显然的。因为$B_2'\setminus W' = \{c_i | c_i = b_i\}$，因此这些基与$B_1$可以合并成一个线性基。而一个线性基的划分显然是互相线性无关的。

接下来证明$B_2$能被$B_2'$表示（相当于证明$B_2'$是合法的线性基）。容易发现$b_i$可以用$c_i$和$b_1, \ldots, b_{i-1}$表示。当$i=1$时始终有$b_1 = c_1$，使用归纳法可以证明$b_i$能被$c_1,\ldots,c_i$表示。

实现上述构造算法的时候，我们维护$a_1\ldots,a_x, b_1\ldots,b_{i-1}$构成的线性基$T$，并维护$T$中的每个向量是$a_1\ldots,a_x, b_1\ldots,b_{i-1}$中哪些向量的和（一种方案即可），用二进制数表示。

已知线性基求张成空间中前缀为$\overline{u_1\ldots u_i1}$的向量个数可以$O(d)$计算。

直接枚举$[n]$的子集容斥的复杂度是$O(n2^nd^2)$。从去掉最后一个数的基转移可以优化到$O(2^nd^2)$。预处理出线性基后容斥的复杂度是$O(2^nd\log_2k)$，因此总复杂度$O(2^n(d^2+d\log_2k))$。

代码