2024.1.14~1.20 周内刷题总结

[ABC158F] Removing Robots 题解

\qquad 题面

\qquad 本题的连锁反应显然在指引我们建图。但是建出 $DAG$ 后，我们发现转移也是很难搞的。在这里，我们引入一个小技巧：关于这类 $DAG$ 表示连锁关系的 $dp$ 中，$DAG$ 可以退化成一棵树，随后进行树形 $dp$。原先的连锁关系变为树上的祖先关系，而树形 $dp$ 就会十分好写。

\qquad Code

[ABC145F] Laminate 题解

\qquad 题面

\qquad 首先，我们要明确一点：这 $K$ 根被改变的柱子一定不会给总代价带来贡献。所以我们可以视为删去了 $K$ 根柱子，留下了 $n-K$ 根柱子。至此，我们便可设计状态：$d{p}_{i,j}$ 表示考虑完了前 $i$ 根柱子，保留了 $j$ 根柱子的最小代价。转移很简单。

\qquad Code

[ABC254G] Elevators 题解（坑点总结）

\qquad 题面

\qquad 本题的主要目标就是让我们从第 $x_i$ 栋楼的第 $y_i$ 层跳到第 $z_i$ 栋楼的第 $w_i$ 层。在这里，我们假设 $y_i<w_i$。若大于，交换即可。

\qquad 首先要确定一点：我们一定只会向上坐电梯，向下坐一定是不优的，因为向下之后早晚要再上去。所以，我们的问题就可以简化为：最少需要换几栋楼才能让我们从 $y_i$ 层到达 $w_i$ 层。

\qquad 接着，我们再贪心地想：如果我们现在要坐电梯向上走，那么我们坐到当前楼中能坐到的最高层一定是不亏的。毕竟迟早都要上到这么高，早上去一会肯定没问题。这就启发我们要把一层楼中有重叠部分的电梯合并成一个大电梯来处理。

\qquad 现在，我们思考：如何判断我们能否坐到第 $w_i$ 层呢？我们想：假设现在我们从第 $p$ 层出发，能坐到的最高的层数为 $q$。如果 $q\ge w_i$，那么是不是就能说明我们一定能坐到第 $w_i$ 层呢？这启发我们可以记录从第 $i$ 层出发，能坐到的最高的层数，记为 $f_i$。若 $f_{y_i}\ge w_i$，那就说明一定能坐到第 $w_i$ 层。

\qquad 但是，题目要求我们求出最小的转楼次数。我们如何将转楼次数与最高层数联系起来呢？我们可以大力添加状态的维度。设 $f_{i,j}$ 表示从 $i$ 出发，转 $j$ 次楼能坐到的最高层数。这显然是可搞的。但是时空复杂度是接受不了的。分析这一状态，我们发现，随着转楼次数的升高，能坐到的最高层数一定是不降的，所以我们可以考虑倍增的写法，设 $f_{i,j}$ 表示从 $i$ 出发，转 $2^j$ 次楼能坐到的最高层数，用线段树可以先求出 $f_{i,0}$，然后用倍增求出剩下的 $f_{i,j}$ 即可。

\qquad 坑点：1、区间合并的时候，右端点是不断在更新的！当前已合并区间的右端点是前面所有右端点的 $max$！2、倍增查询时，要先将初始的 $y,w$ 跳到所在电梯的最高层、最低层。因为倍增记录的是跨楼次数，但是这一初始化的进行是不需要跨楼的。

\qquad Code

[ARC160C] Power Up 题解

\qquad 题面

\qquad 本题如果直接硬对着序列设计状态（例如设计 $f_i$ 表示考虑到第 $i$ 个数可构成的集合的方案数）是不好转的，因为相等的数可能有很多，合并之后的情况很复杂。再者，我们观察到本题的值域较小，而且合并的过程也主要和值与其个数有关，所以我们大力设状态：$d{p}_{i,j}$ 表示在合并数字 $i$ 之前还剩 $j$ 个 $i$ 的方案数。那么转移也是好转的：$d{p}_{i,a_i+j}={\sum }_{k=j\times 2}^{NUMma{x}_{i-1}}d{p}_{i-1,k}$。$NUMma{x}_{i-1}$ 表示 $i-1$ 最多有多少个。乍一看，这是一个二维的转移式。但是，通过计算可得，它的总状态数是相当的少的，大概只有 $2N$ 范围，所以我们直接大力转移即可。转移时需要用到后缀和、滚动数组优化，不过都很简单。

\qquad Code

[ABC203F] Weed 题解

\qquad 题面

\qquad 首先，本题的贪心策略显然是错误的，想 $Hack$ 也很简单。所以我们考虑设计 $dp$ 状态。本题要求两个值：1、最小的操作次数；2、满足操作次数最小的基础上，预先拔掉草的数量最小。我们可以设 $d{p}_{i,j}$ 表示操作了 $j$ 次，解决了前 $i$ 株草，所需要预先拔掉的最少的草的数量。设计这个状态主要的一点好处就是同时包含了题目要求的两个值，通过判断 $d{p}_{i,j}\le K$ 来判断 $j$ 次操作是否可行。转移很显然，每株草有被预先处理和不被预先处理两种选择。式子很好写。由于每次操作相当于折半操作，所以最多进行 $log$ 次操作，状态数为 $nlog$ 级别的，直接跑可过。

\qquad Code

Shopping

\qquad 题面

\qquad 本题对树背包的限制是：选取的物品在树上一定要连成一个连通块。这一点可以启发我们用点分治来解决。不过正常去跑树上多重背包显然是会 $T$ 的。在这里引入一个树形 $dp$ 的优化方法：求出树的 $dfs$ 序后在 $dfs$ 序上 $dp$。再加上一个单调队列优化多重背包，便可做到 $O(Tnm\log d)$ 的时间复杂度。

\qquad Code

时代的眼泪

\qquad 网络流妙题。

\qquad 前面几档状压的分就不说了，考虑 $K=1$ 怎么搞。通过前面的状压我们得到了两条性质：1、可以将 $A$ 类事件删减成一个 $x$ 递增，$y$ 递减的形状；2、$B$ 类事件覆盖一整个区间一定是优的。在这两条性质的基础上，我们便可以列一个 $dp$ 式子：$f_i$ 表示前 $i$ 个 $A$ 类事件被覆盖的最小代价。转移很好写：$f_i=\min (f_{j-1}+\max (x_i-x_k,0)+\max (y_j,y_k,0))$，$k$ 是我们枚举的使用哪个 $B$ 类点。这个 $dp$ 是很难优化的，我们考虑用更巧妙的方法来完成它。我们把所有事件的 $x,y$ 坐标都存起来，并分别从小到大排序。然后我们考虑建图：$x_i$ 向 $x_{i+1}$ 建一条边权为 $x_{i+1}-x_i$ 的边，同时连一条边权为 $0$ 的反向边。$y_{i+1}$ 向 $y_i$ 连一条边权为 $y_{i+1}-y_i$ 的边，同时连一条边权为 $0$ 的反向边。对于每个B类事件，我们从其 $y$ 向 $x$ 连一条边权为 $0$ 的边。这样，上面转移式中的 $\max +\max$ 就可以表示为从 $y_j$ 到 $x_i$ 的最短路。原因如下图：

\qquad 我们想从 $j$ 转移到 $i$，$y$ 是从大指向小的，$x$ 是从小指向大的，所以上述建图方法跑出来的最短路就是 $B$ 类事件需要移动的最短距离。但是这样转移还是 $O(n^2)$ 的，怎么优化呢？上面的性质 $2$ 已经解决了这一问题。性质 $2$ 旨在表明一个 $A$ 类事件最多被覆盖一次，所以我们跑完 $y_j$ 到 $x_i$ 的最短路后，下一次一定是从 $y_{i+1}$ 开始往后跑。所以我们对于每个A类事件，从 $x_i$ 向 $y_{i+1}$ 连一条边权为 $0$ 的边，最后跑一个 $y_1$ 到 $x_n$ 的最短路就是答案。

\qquad 那么对于 $K$ 为任意值怎么搞呢？那就相当于在图上找 $K$ 条路径并让他们总权值最小。这里边 $B$ 类事件连出来的边只能被经过一次，因为一个 $B$ 类事件最多被移动到一个位置。这个模型就非常像费用流。我们把上图中的边权变为费用流中的费用，让 $B$ 类事件连的边的容量为 $1$，其余边容量为 $INF$，跑一个流量为 $K$ 的最小费用最大流即可。但是本题直接按照正常的基于 $spfa$ 寻找增广路的费用流去跑是会 $T$ 的。而 $Dijkstra$ 跑不了带负边权的流网络。怎么办呢？我们可以采用 $Johnson$ 算法的思想，给每个点赋一个势能，在增广的过程中动态更新势能即可。这样就可以用 $Dij$ 来增广。总时间复杂度为 $O(Kn\log n)$，常数较大。

\qquad Code