一些前 k 优解问题

· · 个人记录

群友几个月之前天天在群里研究 Shopping Plans 这个神秘题目。

当时看了一下就放到 Todo list 里吃灰了啊，后面开学之后某个周末没事情干就做了一下不过忘记写总结了。

今天联考 T4 做到这个题，感觉很神秘，怎么开始往联考里面传播 shopping 邪教了。

昨晚 fst 群是不是还在讨论 shopping 的另一个扩展来着，k 短路啥的，我没仔细看。

神秘，是不是群友搬的，但是群里也没 cqbz 人啊，唉唉给 cftm 大神和怪兽叠磕头了啊啊啊啊。

部分参考了 cftm 大神博客 啊啊。

以下主要探讨一类“求前 k 优解”的问题。

这种问题的做法一般基于一种类似 Dijkstra 的堆贪心。

记状态集合为 T，每个状态 i \in T 的权值为 val(i)。

我们考虑对于每一个状态 i，建立形如 i \to \text{trans}(i) 的转移。

其中 \text{trans}(i) 为 O(1) 个可以通过对 i 进行一次调整得到的状态，并保证 val(i) \le val(\text{trans}(i))。

并且需要满足，若记 I \in T\text{ s.t. }val(I) = \min\limits_{i \in T}\{val(i)\}，则对于任意一个状态 i \in T，从初始状态 I 有一条唯一的简单路径能够到达它。

可以发现这构成了一颗外向树，于是我们只需要使用一个堆，每次取出堆顶的状态并构建 \text{trans} 加入堆中就能得到前 k 优解，时间复杂度为 O(k \log k)。

所以这类问题的重点通常在于如何构建唯一的不漏转移，最基本的一种考量是贪心地扩展代价差尽量小的，再有就是考虑进行一些钦定来去重之类的。

Shopping Plans on Multiset

你有一个可重集合 S，你需要从里面选一些数构成子集，要求选 [l, r] 之间的个数个。

你需要求出前 k 大的子集和，|S| \le 2 \times 10^5, V \le 10^9。

显然我们应该对 S 排序。

一个比较暴力的状态设计是考虑直接二进制记录状态，这样只能做指数级别的，你可能会再折半，不过没救。

初始状态显然是选最左边的 l 个物品，我们考虑进行调整构造 \text{trans}。

考虑每次把某个已选的指针向后挪一步；不妨记录 (p, nw, nxt) 表示前缀 p 没有移动，当前我们考虑 nw，nw 右边已选的物品为 nxt。

转移就是移动当前，或者是考虑把前面某一个还没挪动的向后挪动，或者是考虑用新的前缀转移。

转移为 (p, nw, nxt) \to (p, nw + 1, nxt),nw + 1 < nxt，以及 (p, nw, nxt) \to (p - 1, nw + 1, nxt - 1)。

使用新的前缀则只需要在开头 nxt = \text{NULL} 的时候做一个转移就好，这样就可以做到不重不漏。

### Shopping Plans on Arrays > 你有 $n$ 个数组，你每个数组里需要选恰好一个。 > > 你需要求出前 $k$ 大的方案，$n, k, \sum len \le 10^5$。 > > Source: [USACO16DEC] Robotic Cow Herd P. 考虑将所有数组排序，初始状态显然应当为全部取第一个。 考虑用状态描述，一个比较暴力的想法是考虑设一个 $n$ 元组，第 $i$ 个位置表示第 $i$ 个数组选了哪个数。 显然这样状态就存不下，而且你发现我们转移会算重，比如 $n = 4$，初始状态是 $(1,1,1,1)$，我们至少可以经由 $(1,2,1,1)$ 和 $(1,1,2,1)$ 走到 $(1,2,2,1)$，这就不满足我们所说的 $\text{trans}$ 的条件。 所以我们考虑按顺序确定，先确定好第 $i$ 个人的再确定第 $i + 1$ 个人的，具体来说我们假定前面已经算好就行。 于是状态设计为 $(sum, i, j)$ 表示考虑当前和为 $sum$，在第 $i$ 个数组选了第 $j$ 个，并且我们默认 $i + 1 \sim n$ 全部选第一个，不然你状态不是代表的某个完整的局面的。 转移分两种，一种是 $(sum, i, j) \to (sum + a(i, j + 1) - a(i, j), i, j + 1)$，一种是 $(sum, i, j) \to (sum, i + 1, 1)$。 前者就是调整一下，后者就是选定第 $i$ 行的状态。 但是你发现这样子 $(2, 1, 1, 1)$ 在 $(?, 2, 1), (?, 3, 1), (?, 4, 1)$ 都会被算到。 这怎么办，注意到问题关键在于 $j = 1$，形如 $(?, x, 1) \to (?, x + 1, 1)$ 的状态并不会有任何改变，于是我们强制考虑中的 $j > 1$ 且向下转移也保持。 然后真正要选第一个则从 $j = 2$ 撤回去就行，但是仍然需要保证单调性。 具体来说我们令 $(?, i, 2) \to (?, i + 1, 2)$ 存在两种转移，一种是本来就都选。 一种是代价为 $[a(i + 1, 2) - a(i + 1, 1)] - [a(i, 2) - a(i, 1)]$，前者为选择 $a(i + 1, 2)$ 的代价（因为默认之前选过 $a(i + 1, 1)$），后者为通过从选 $a(i, 2)$ 撤回到选 $a(i, 1)$ 的代价。 注意到这样可能会有负代价的转移，所以我们按照 $a(x, 2) - a(x, 1)$ 升序排序即可。 ### Shopping Plans > 有 $N$ 个商品，每个商品有个种类 $a_i$，有个价格 $c_i$。 > > 对于第 $j$ 个种类，必须购买个数位于 $[x_j,y_j]$ 的商品，即最少购买 $x_j$ 个，最多购买 $y_j$ 个该种类的商品。 > > 您需要求出前 $K$ 种便宜的方案所需的价钱，如果没有这样的方案，请输出 `-1`。 > > 特别的，如果有相同钱数，但是具体方案不相同的，算作两种方案。 > > $1\le N,M,K\le 2\times 10^5$，$1\le a_i\le M$，$1\le c_i\le 10^9$，$0\le x_j\le y_j\le N$。 > > Source: [CCO2020] Shopping Plans. 考虑把 Shopping Plans on Multiset 做法拿过来。 我们把这个当成一个黑盒，于是可以获取每一行里面的合法前 $k$ 优解。 于是把这个套用到 Shopping Plans on Arrays 就可以了！复杂度一个 $\log$。 ### Shopping Plans on Tree > 给定一棵 $n$ 个节点的带权无根树。 > > 你需要求树上权值前 $k$ 小的连通块。 > > $1 \le n, k \le 10^5, 1\le V \le 10^9$。 > > Source: IOI2019 国家集训队论文《浅谈树上分治算法》例题 2.2 by 张哲宇 首先我们考虑点分治，将问题转化为树上带根权值前 $k$ 小连通块。 这么做的原因是我们希望连通块和连通块之间的答案能通过扩展计算，而钦定一个根之后计算就方便多了。 考虑记录一个指针表示当前考虑“可能要扩展”的元素，每个位置的决策就是选，然后指针指向入栈时间戳（dfn）+ 1 的节点边权为这个节点点权，否则就是不选这个子树，指针指向出栈时间戳 + 1的节点，边权为 $0$。 然后对于 $n + 1$，将其作为终点，此时每个连通块和新图上的一条路径成一一对应关系，问题转化为 $1 \to n + 1$ 的 $k$ 短路问题。 我现在还比较菜，不知道咋规约到用“决策”考虑的办法上，具体来说现在的问题在于我们实际上是考虑从连通快的边缘扩展，扩展钦定了唯一的边界，就是 $dfn$ 最大的。 但是考虑的节点不一定会被选，这就很难受，转移会转移重，群友说这好像没法规约，哎哎，我再想想，感觉还是有可能。 ### Shopping Plans on Permutation 感觉是目前能找到的终极 Shopping Plans，等雷暴研发超级无敌炫酷元神大王 Shopping Plans 啊啊 > 给定一个长度为 $n$ 的排列 $p$ 和数组 $a$。 > > 定义一个排列 $q$ 的代价为 $\sum a_i \times q_i$，求代价前 $k$ 小的排列。 > > $1 \le n, k, \le 10^5$。