2024.1.14~1.20 周内刷题总结

本文主要是介绍2024.1.14~1.20 周内刷题总结，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

2024.1.14~1.20 周内刷题总结

[ABC158F] Removing Robots 题解
[ABC145F] Laminate 题解
[ABC254G] Elevators 题解（坑点总结）
[ARC160C] Power Up 题解
[ABC203F] Weed 题解
Shopping

[ABC158F] Removing Robots 题解

$\qquad$ 题面

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

$\qquad$ Code

[ABC145F] Laminate 题解

$\qquad$ 题面

$\qquad$ 首先，我们要明确一点：这 $K$ 根被改变的柱子一定不会给总代价带来贡献。所以我们可以视为删去了 $K$ 根柱子，留下了 $n - K$ 根柱子。至此，我们便可设计状态： $dp_{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\geq w_i$ ，那么是不是就能说明我们一定能坐到第 $w_i$ 层呢？这启发我们可以记录从第 $i$ 层出发，能坐到的最高的层数，记为 $f_i$ 。若 $f_{y_i}\geq w_i$ ，那就说明一定能坐到第 $w_i$ 层。

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

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

$\qquad$ Code

[ARC160C] Power Up 题解

$\qquad$ 题面

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

$\qquad$ Code

[ABC203F] Weed 题解

$\qquad$ 题面

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

$\qquad$ Code

Shopping

$\qquad$ 题面

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