2023.1 做题记录

P5268 [SNOI2017] 一个简单的询问

发现可以拆询问，答案即为：

$$\displaystyle\sum_{x}q(r_1,r_2)-q(l_1-1,r_2)-q(r_1,l_2-1)+q(l_1-1,l_2-1)$$

其中 $q(a,b)=\operatorname{get}(1,a,x)\operatorname{get}(1,b,x)$．

$q(a,b)$ 使用莫队维护，移动端点 $l,r$ 的过程中维护 $c_x,d_x$，分别表示 $[1,l],[1,r]$ 区间内 $x$ 的出现次数．容易维护答案．

P3224 [HNOI2012] 永无乡

用并查集维护连通性，权值线段树维护联通块内的排名．

注意合并并查集和合并权值线段树的方向要一致．

P8110 [Cnoi2021] 矩阵

趣味数学题．

进行一个式子的推，我们有：

$$\begin{aligned} \left(A^2\right)_{i,j} &= \sum_{k=1}^n A_{i,k}A_{k,j} \\ &= \sum_{k=1}^n a_ib_ka_kb_j \\ &= a_ib_j\sum_{k=1}^n a_kb_k \\ &= A_{i,j}\sum_{k=1}^n A_{k,k} \\ \end{aligned}$$

归纳可得：

$$\left(A^x\right)_{i,j}=A_{i,j}\left(\sum_{k=1}^n A_{k,k}\right)^{x-1}$$

所以有：

$$\begin{aligned} \sum_{i=1}^n\sum_{j=1}^n\left(A^x\right)_{i,j} &= \sum_{i=1}^n\sum_{j=1}^nA_{i,j}\left(\sum_{k=1}^n A_{k,k}\right)^{x-1} \\ &= \left(\sum_{k=1}^n A_{k,k}\right)^{x-1}\sum_{i=1}^n\sum_{j=1}^n A_{i,j} \\ &= \left(\sum_{k=1}^n a_kb_k\right)^{x-1}\sum_{i=1}^n\sum_{j=1}^n a_ib_j \\ &= \left(\sum_{k=1}^n a_kb_k\right)^{x-1}\left(\sum_{i=1}^n a_i\right)\left(\sum_{i=1}^n b_i\right) \\ \end{aligned}$$

分别计算 $\left(\displaystyle\sum_{i=1}^n a_ib_i\right)^{k-1}$，$\displaystyle\sum_{i=1}^n a_i$ 和 $\displaystyle\sum_{i=1}^n b_i$ 即可．

P2272 [ZJOI2007] 最大半连通子图

不难发现一个 SCC 中的所有点对一定满足半联通性质，所以我们先 SCC 缩点，设缩点后点的点权为其对应的 SCC 大小．

缩完点后的图变成了一个 DAG，可以发现我们只能选取这样的图中的一条链，所以我们的问题变成了求一个 DAG 中点权和最大的一条链的长度和这样的链的数目，不难用 dp 解决这个问题．

设 $f_u$ 表示结束在 $u$ 的链的最大点权和，$g_u$ 表示点权和最大的链的个数．令 $E_u$ 表示 $u$ 的入边集，$w_u$ 表示 $u$ 的点权，我们有如下转移：

$$f_v\leftarrow\max_{(u,v)\in E_v}\{f_u+w_v\}$$

$$\forall (u,v)\in E_v,g_v\leftarrow \begin{cases} g_u & \text{if }f_v=f_u+w_v \\ g_u+g_v & \text{if }f_v<f_u+w_v \end{cases}$$

值得一提的是，tarjan 缩点给 SCC 的编号是逆拓扑序，可以直接 dp．

LOJ10098 「一本通 3.6 例 1」分离的路径

首先注意到一个 E-BCC 中的所有点对一定有两条不同的路径联通，所以我们可以先 E-BCC 缩点．缩点完之后变成了一棵树，其中树上的所有边都是原图中的割边．

对于我们加入的一条边 $(u,v)$，$u$ 到 $v$ 的路径上的所有割边均被消除，为了最小化答案，我们加入的边一定都在叶子中连接．

记叶子个数为 $x$．叶子个数为偶数时，我们需要连接 $\displaystyle\frac{x}{2}$ 条边才能消除所有割边，这是因为一次连边最多消除 $2$ 个叶节点；奇数时先丢掉 $1$ 个叶节点，按照偶数方式处理，最后只剩 $2$ 个节点时再连 $1$ 条边，就能消除所有割边．

综上，答案为 $\displaystyle\left\lceil \frac{x}{2} \right\rceil$．

LOJ10225 「一本通 6.5 练习 3」迷路

首先，无权图定长路径计数是可以 通过矩阵乘法在 $O(n^3\log k)$ 内解决 的．

然后对于本题，注意到边权较小，而正权图可以拆边变成无权图，所以拆边后直接构造矩阵进行快速幂即可．

注意到这样做的点的级别为 $O(Wm)$，其中 $W$ 是最大的边权，$m$ 是边的数量．总时间复杂度 $O((Wm)^3\log t)$，不可接受．

我们换一个建模方式．把每个点拆成 $8$ 个点，记 $u$ 拆成的第 $i$ 个点为 $u_i$，$u_i$ 和 $u_{i+1}$ 之间存在一条边．对于原图中的一条边 $(u,v)$，记其边权为 $w$，在拆点后对应的边为 $(u_1,v_w)$．然后对拆点后的图构造矩阵进行快速幂，复杂度 $O((Wn)^3\log t)$，可以通过本题．

[USACO 2005 February Gold] Secret Milking Machine

模拟赛做到的题目．似乎只有 POJ 提供这题的评测，所以在此放出题面．

题意

有一 $n$ 个点 $m$ 条边的带权图，需要找到 $t$ 条由 $1$ 到 $n$ 的路径，使得这 $t$ 条路径上边权的最大值最小．

解法

看到最大值最小，考虑二分最大值．

设当前二分答案为 $x$．我们断开边权大于 $x$ 的所有边，检查在这个图中 $1$ 到 $n$ 的路径数是否满足条件．问题转化为图上路径计数问题．

容易使用网络流来解决这个问题．我们将剩下边的流量设置成 $1$，$1$ 到 $n$ 的最大流即为路径数．

LOJ10188 「一本通 5.6 练习 1」玩具装箱

设 $f_i$ 为前 $i$ 个玩具装箱后的最小代价，有如下转移：

$$f_i\leftarrow\min_{j<i}\left\{f_j+\left[\left(i-(j+1)+\sum_{k=j+1}^iC_k\right)-L\right]^2\right\}$$

记 $\displaystyle s_x=\sum_{i=1}^xC_i$，转移式可化为：

$$f_i\leftarrow\min_{j<i}\left\{f_j+\left[\left(i-(j+1)+s_i-s_j\right)-L\right]^2\right\}$$

时间复杂度为 $O\left(n^2\right)$，无法通过本题．

令 $t_x=s_x+x,l=L+1$，注意到上式可化为：

$$f_i\leftarrow\min_{j<i}\left\{f_j+{t_j}^2+2t_j(l-t_i)\right\}+(l-t_i)^2$$

若对于当前转移有状态 $f_p$ 优于 $f_q$，那么必然有：

$$\begin{alignedat}{} && f_p+{t_p}^2+2t_p(l-t_i) &< f_q+{t_q}^2+2t_q(l-t_i) \\ &\Rightarrow& f_p+{t_p}^2-f_q+{t_q}^2 &< -2t_p(l-t_i)+2t_q(l-t_i) \\ &\Rightarrow& \left(f_p+{t_p}^2\right)-\left(f_q+{t_q}^2\right) &< -2(t_p-t_q)(l-t_i) \\ &\Rightarrow& \frac{\left(f_p+{t_p}^2\right)-\left(f_q+{t_q}^2\right)}{(t_p-t_q)} &< -2(l-t_i) \end{alignedat}$$

然后就可以斜率优化了．用单调队列维护决策点，时间复杂度 $O(n)$．

P1283 平板涂色

记第 $i$ 个矩形需要涂的颜色为 $c_i$，需要在第 $i$ 个矩形之前涂完色的矩形集合为 $L_i$．

设 $f_{S,x}$ 表示当前已涂色矩形集合为 $S$，最后一次涂的颜色为 $x$ 时的最小涂色次数，转移时枚举本次涂色的矩形 $i$ 和上一次涂色的颜色 $a$，转移方程如下：

$$f_{S\cup\{i\},c_i}=\min\{f_{S,a}+[a\not=c_i]\}$$

注意到 $1\le N\le 16$，允许我们将集合压位储存．

P8360 [SNOI2022] 军队

我们使用分块解决这个问题．

考虑分块如何维护颜色信息，我们可以在每个块中开 $C$ 个并查集，每个并查集中维护相同颜色的元素．初始化时，将每个元素插入到其颜色对应的并查集中．

先考虑怎么做第二个操作：对于整块 $i$，在 $i$ 中颜色 $x$ 对应的并查集的根节点上打上标记，通过维护并查集大小，容易计算块中元素更新后的和；对于散块，暴力修改即可．

然后考虑怎么做第一个操作：对于整块，将其中颜色 $x$、$y$ 对应的并查集合并；对于散块，将每个元素从 $x$ 对应的并查集中扣出来，插入 $y$ 对应的并查集中．注意到整块颜色合并时，如果直接将 $x$ 并到 $y$ 上，$y$ 上原本的标记会下传到 $x$ 中，所以合并时应当新建节点 $z$，将 $x$ 和 $y$ 都合并到 $z$ 上．

P4180 [BJWC2010] 严格次小生成树

先建出最小生成树 $T$，枚举不在 $T$ 的边集中的边 $(u,v,w)$，我们尝试用这条边去替换 $T$ 上的边，得到另外一个合法的生成树．要求次小生成树，这条边只会替换 $T$ 中 $u$ 到 $v$ 路径上最大的边权所对应的那条边，倍增或者树剖维护一下即可．题目要求严格次小生成树，只需在维护路径上最大值的同时维护一个严格次大值，若最大值等于 $w$，就用这条边替换严格次大的边权所对应的那条边．