Shopping Plans Trick

· · 个人记录

k 优解

形式化地,将一般的 k 优解问题定义为:

设最优化问题的解空间为 \Omega,代价函数 f:\Omega \to \mathbb{R}。给定 k,构造长为 k 的解序列 x_1,x_2,\cdots,x_k \in \mathbb{\Omega},满足如下条件:

  • 互异性:\forall 1 \le i<j \le k, x_i \ne x_j。
  • 有序性:f(x_1) \le f(x_2) \le \cdots \le f(x_k)。
  • 最优性:\forall x \in \Omega \setminus \{x_1,x_2,\cdots,x_k\}, f(x_k) \le f(x) 。

对于 \Omega 和 k 满足特定要求的情形,我们有专门的堆优化搜索算法,称作 Shopping Plans Trick,由使用该算法的经典题目 P6646 得名。

考察如下刻画:建立有向图 G=(\Omega,E),满足 \forall (x,y) \in E,f(x)<f(y),并且 \forall x \in \Omega,x_1 \to x 可达,找出 x_1 后,离 x_1 前 k 近的点列即为所求的解序列。

此处不妨设 f 值互不相同,对 f 值相同的情形,将节点编号作为第二关键字比较即可。这里的目的是得到 \Omega 上的严格全序。

注意到 G 必为一张 DAG。考虑如下搜索算法:

:::::info[算法 1]{open}

:::::

算法 1 等价于在 DAG 上进行 Dijkstra。

注意到算法 1 并不需要显式建出 G。观察算法 1 的复杂度瓶颈:

  1. 枚举 (x, y) \in E 的所有的 y。
  2. 判定 x \in S 是否成立,修改 S \gets S \cup \{x\}。

一般地,认为可以在 O(1) 内解决问题一。若问题二存在 O(\log |S|) 的高效算法,算法 1 的复杂度即为 O(k \log k)。

更一般地,认定问题二不存在高效算法。注意到 G 的形态是以 x_1 为根的外向树时,有如下算法成立:

:::::info[算法 2]{open}

:::::

这是 Shopping Plans Trick 的一般性算法。易知复杂度 O(k \log k)。

我们考察算法 2 的本质。形式化地,我们对全体 x \in \Omega 构造了转移集合 \text{trans}(x),且转移满足下列性质:

两种算法都需要满足最优性和覆盖性,算法 2 需要满足唯一性。

进一步,对覆盖性进行扩展:

若 \text{trans} 仍满足最优性和唯一性,有如下算法成立:

:::::info[算法 3]{open}

:::::

若 m=O(k) 则复杂度 O(k \log k)。从图论视角来看,G 的形态是以 x_1',x_2',\cdots,x_m' 为根的外向森林。

实际上,对 k 优解使用 Shopping Plans Trick 后往往转化成构造题。我们需要对每个可行解 x \in \Omega 构造状态 S(x),并构造 S 的转移 \text{trans}(S) 满足特定性质,然后使用对应算法解决。

::::::info[练习]{open}

给定两个长为 n 的单调不降序列 a_i,b_i。设 \Omega=\{a_i+b_j \mid i,j \in [1,n]\},求 \Omega 的前 n 小解。

::::success[答案 1]

对可行解 a_i+b_j 构造状态 S=(i,j),转移到 (i+1,j) 和 (i,j+1)。

此时 S(x_1)=(1,1),易证最优性和覆盖性成立。

由于上述构造不满足唯一性,使用算法 1 解决。使用 std::set 判重,复杂度 O(n \log n)。

::::

::::success[答案 2]

对可行解 a_i+b_j 构造状态 S=(i,j),若 j \ne 1 则仅转移到 (i,j+1),否则转移到 (i+1,j) 和 (i,j+1)。

显见最优性成立,下证覆盖性和唯一性成立:

使用算法 2 解决,复杂度 O(n \log n)。

::::

::::success[答案 3]

对可行解 a_i+b_j 构造状态 S=(i,j),仅转移到 (i,j+1)。

考察转移图的形态,可以发现转移图由 n 条链组成。记 x_i'=(i,1),则 x_1' \sim x_n' 满足广义覆盖性。易证最优性和唯一性成立,使用算法 3 解决。复杂度 O(n \log n)。

::::

::::::

P2541 [USACO16DEC] Robotic Cow Herd P

给定 n 个序列 a_i。对所有 p_1,p_2,\cdots,p_n 满足 \forall i, p_i \in [1,|a_i|],取 \sum \limits_{i=1}^n a_{p_i} 为一组解,求前 k 小解的和,保证有解。

:::::success[题解]

首先对所有 a_i 升序排序。

考虑 Shopping Plans Trick。直观的想法是将状态构造为 S=(p_1,p_2,\cdots,p_n),此时 S(x_1)=(1,1,\cdots,1)。

转移即为枚举 i \in [1,n],令 p_i \gets p_i+1。最优性和覆盖性成立,使用算法 1 解决。

我们发现 S 需要 O(n) 级别的信息,去重和转移的代价均不可接受。

为了避免维护解序列的形态,我们转而关注可行解关于最小解的增量。由于 |a_i|=1 的序列无法提供增量,故将其删去。由于维护增量的要求,初始入堆的状态值应当是 (2,1,1,\cdots,1)。

钦定转移的拓扑序,决策移动第 i 个指针后,之后只允许移动下标 \ge i 的指针。从而状态转为 S=(w,i,p_i,p_{i+1},\cdots,p_n),其中 w 为当前权值和。

为书写简便,记 \delta_i=a_{i,2}-a_{i,1},容易构造 S 的转移为:

观察上述转移,可以发现 (p_{i+1},\cdots,p_n) 这些信息无用,可以将其删去,状态改为 S=(w,i,p_i),转移为 S \to (w-a_{i,p_i}+a_{i,p_i+1},i,p_i+1) 和 S \to (w+\delta_j,j,2)。

不难自行验证最优性、覆盖性、唯一性满足。使用算法 2 解决,由 |\text{trans}(S)|=O(n) 得复杂度 O(nk \log k),无法通过。

视 -a_{i,p_i}+a_{i,p_i+1} 和 \delta_j 为出边权值。考察转移图 G 的形态,其构成以 \left(\sum \limits_{i=1}^n a_{i,1}-\delta_1,1,1\right) 为根的多叉外向树,节点出度达到 O(n)。

我们希望优化 S \to (w+\delta_j,j,2) 的转移,故拉出相关转移边的导出子图 G' 并在 G' 上思考问题。想象状态节点 x \in \Omega,我们将 x 的所有儿子按出边权值升序排序,并将出边形态改为左儿子右兄弟表示法,出边权值变为邻项差分,如图:

这里将儿子按出边权值排序的目的是,保证上述变换后边权非负,导出最优性成立。

我们所有节点同时做上述操作,转移图变为外向二叉树,节点出度为 O(1),容易说明两种转移图等效。

思考左儿子右兄弟优化在本题转移中的实际意义,就是将枚举 j \in (i,n] 的过程转化只考虑 j=i+1,通过兄弟指针平移到 i+2。

- 左儿子:$(w,i,p_i) \to (w+\delta_{i+1},i+1,2)$。 - 右兄弟:若 $\textcolor{red}{p_i=2}$ 有 $(w,i,p_i) \to (w_i-\delta_i+\delta_{i+1},i+1,2)$。 注意到右兄弟的转移边权为 $-\delta_i+\delta_{i+1} \ge 0$,需要按 $\delta_i$ 将所有序列升序排序。 注意原转移 $(w,i,p_i) \to (w-a_{i,p_i}+a_{i,p_i+1},i,p_i+1)$ 仍成立。 再使用算法 2,我们得到了 $O(\sum |a_i| \log |a_i|+n \log n+k \log k)$ 的做法,可以通过本题。 ::::: :::::info[代码] ```cpp line-numbers const int N = 1e5 + 5; int n, m, k; vector<int> a[N]; i64 delta(int i) {return a[i][2] - a[i][1];} using state = tuple<i64, int, int>; // (w, i, p_i) priority_queue<state, vector<state>, greater<state>> q; void _main() { cin >> m >> k; i64 sum = 0, res = 0; for (int i = 1, l; i <= m; i++) { cin >> l; vector<int> vec; for (int x; l--; ) cin >> x, vec.emplace_back(x); sort(vec.begin(), vec.end()), res += vec[0]; if (vec.size() == 1) sum += vec[0]; else vec.insert(vec.begin(), -1), a[++n].swap(vec); } if (n == 0) return cout << sum, void(); sort(a + 1, a + n + 1, [](vector<int>& a, vector<int>& b) -> bool { return a[2] - a[1] < b[2] - b[1]; }); q.emplace(res + delta(1), 1, 2); while (--k) { auto [w, i, pi] = q.top(); q.pop(); res += w + sum; if (pi+1 < (int)a[i].size()) q.emplace(w + a[i][pi+1] - a[i][pi], i, pi+1); if (i < n) q.emplace(w + delta(i+1), i+1, 2); if (i < n && pi == 2) q.emplace(w - delta(i) + delta(i+1), i+1, 2); } cout << res; } ``` ::::: ## [P6646 [CCO 2020] Shopping Plans](https://www.luogu.com.cn/problem/P6646) > 给定 $n$ 个多重集 $S_i$ 和 $n$ 个区间 $[l_i,r_i]$,对所有 $c_1 \sim c_n$ 满足 $\forall c_i \in [l_i,r_i]$,从 $S_i$ 中选取恰好 $c_i$ 个元素作为一组解,权值为选取的元素之和。求前 $k$ 小解,或报告无解。 > > $n,k,\sum |S_i| \le 2 \times 10^5$,2 秒,512 MB。 :::::success[题解] 假定对于多重集 $S_i$,我们得到特定算法,可以不重不漏地生成该集合上第 $1,2,3,\cdots$ 小合法方案的权值,记作序列 $a_i$。问题等价于从 $n$ 个序列中各取一个元素,求前 $k$ 小权值和,这正是上一题 [P2541](https://www.luogu.com.cn/problem/P2541)。 套用 [P2541](https://www.luogu.com.cn/problem/P2541) 的解法。由于我们只求全局前 $k$ 小,多重集上被索取次优解的总次数不会超过 $O(k)$。从而问题转化为: 给定不降序列 $a_1 \sim a_m$,对 $c \in [l,r]$ 选取恰好 $c$ 个元素作为一组解,在线查询第 $k'$ 小解,且每次操作的 $k'$ 必然比上一轮多 $1$。 将问题弱化到 $l=r$。考虑 Shopping Plans Trick,将状态视作 $S=(p_1,p_2,\cdots,p_l)$,其中 $p_1 < p_2<\cdots<p_l$,表示权值为 $\sum \limits_{i=l}^r a_{p_i}$ 的一组解。初始解是 $(1,2,\cdots,l)$。 钦定转移的拓扑序。我们找到最小的 $i$ 使得 $p_i<p_{i+1}$ 并枚举 $\delta \in [1,p_{i+1}-p_i)$ 令 $p_i \gets p_i+\delta$ 作为 $\text{trans}$,易证最优性、覆盖性、唯一性满足。由于 $|\text{trans}(S)|=O(n)$,复杂度 $O(nk \log k)$ 无法接受。 套路地考察转移图的形态为外向多叉树,对其做左儿子右兄弟优化,转化为外向二叉树。 对应到状态设计上,可以将状态改为 $(w,i,p_i,p_{i+1})$,其中 $w$ 为当前解权值,且我们钦定 $p_1 \sim p_{i-1}$ 未移动。在二叉树上的转移为: - 左儿子:$(w,i,p_i,p_{i+1}) \to (w-a_{i-1}+a_i,i-1,i,p_i)$。要求 $p_i>i$。 - 右兄弟:$(w,i,p_i,p_{i+1}) \to (w+a_{p_i+1}-a_{p_i},i,p_i+1,p_{i+1})$。要求 $p_i<p_{i+1}$。 可以说明转移图的等效性,进而使用算法 2 解决 $l=r$ 的情形。 考虑一般情形。直观的想法是使用算法 3,将所有 $(w,i,i,n+1)$ 入堆,但初始化代价不可接受。 观察算法 3 的本质是将外向树森林的根入堆。不妨建一个超级源点,连向所有 $(w,i,i,n+1)$,并对超级源点的儿子做左儿子右兄弟优化。这样仍可以用算法 2 解决问题,且复杂度正确。注意实现时要在状态中再加一个维度,表示节点是否为虚点。 至此,我们通过套两个 Shopping Plans Trick 的方法解决了此问题,复杂度 $O(\sum |S_i| \log |S_i|+n \log n+k \log k)$。 ::::: :::::info[代码] ```cpp line-numbers const int N = 2e5 + 5; const i64 inf = 1e18; int n, m, k; struct box { using state = tuple<i64, int, int, int, int>; // (w, i, p_i, p_{i+1}, type) priority_queue<state, vector<state>, greater<state>> q; int l, r, n; vector<i64> a, sol; box() : l(-1), r(-1) {sol.emplace_back(-1);} i64 operator[] (int k) const {return k >= (int)sol.size() ? -1 : sol[k];} void add(i64 x) {a.emplace_back(x);} void init(int _l, int _r) { l = _l, r = _r, n = a.size(); if (l > r || l > n) return; sort(a.begin(), a.end()); q.emplace(accumulate(a.begin(), a.begin() + l, 0LL), l-1, l-1, n, 1); } i64 kth(int k) { while ((int)sol.size() <= k && !q.empty()) { auto [w, i, pi, nxt, t] = q.top(); q.pop(); sol.emplace_back(w); if (t && i+1 < r && i+1 < n) q.emplace(w + a[i+1], i+1, i+1, n, 1); if (i > 0 && pi > i) q.emplace(w - a[i-1] + a[i], i-1, i, pi, 0); if (i >= 0 && pi+1 < nxt) q.emplace(w - a[pi] + a[pi+1], i, pi+1, nxt, 0); } return this->operator[](k); } } a[N]; i64 delta(box& b) {return b[2] == -1 ? inf : b[2] - b[1];} using state = tuple<i64, int, int>; // (w, i, p_i) priority_queue<state, vector<state>, greater<state>> q; void _main() { cin >> n >> m >> k; for (int i = 1, t, c; i <= n; i++) cin >> t >> c, a[t].add(c); i64 sum = 0; for (int i = 1, l, r; i <= m; i++) { cin >> l >> r, a[i].init(l, r), a[i].kth(2); if (a[i][1] == -1) { while (k--) cout << -1 << '\n'; return; } sum += a[i][1]; } cout << sum << '\n'; sort(a + 1, a + m + 1, [](box& a, box& b) -> bool { return delta(a) < delta(b); }); if (delta(a[1]) != inf) q.emplace(sum + delta(a[1]), 1, 2); while (--k) { if (q.empty()) { cout << -1 << '\n'; continue; } auto [w, i, pi] = q.top(); q.pop(); cout << w << '\n'; if (a[i].kth(pi+1) != -1) q.emplace(w + a[i][pi+1] - a[i][pi], i, pi+1); if (i < m && delta(a[i+1]) != inf) { q.emplace(w + delta(a[i+1]), i+1, 2); if (pi == 2) q.emplace(w - delta(a[i]) + delta(a[i+1]), i+1, 2); } } } ``` ::::: ## [P2048 [NOI2010] 超级钢琴](https://www.luogu.com.cn/problem/P2048) > 给定长为 $n$ 的序列 $a_i$ 和正整数 $L,R$。对区间 $[l,r]$ 满足 $r-l+1 \in [L,R]$,将 $\sum \limits_{i=l}^r a_i$ 作为一组解。求前 $k$ 大解的和,保证有解。 > > $n,k \le 5 \times 10^5$,2 秒,500 MB。 :::::success[题解] 记 $s_i$ 为 $a_i$ 的前缀和。合法区间 $(l,r]$ 的取值被刻画为 $s_r-s_l$,且 $r-l \in [L,R] \implies l \in [r-R,r-L]$。 构造状态 $S=(w,l_{\min},l_{\max},r)$,$w$ 是当前状态的最优子段和,即 $w=s_r-\min \limits_{l \in [l_{\min},l_{\max}]} s_l$。 设 $p$ 为 $s_i$ 中 $[l_{\min},l_{\max}]$ 区间 $\min$ 的下标。我们将区间分裂成 $[l_{\min},p)$ 和 $(p,l_{\max}]$ 进行转移: $$ S \to \left(s_r-\min_{l \in [l_{\min},p)} s_l, l_{\min},p-1,r\right)\\ S \to \left(s_r-\min_{l \in (p,l_{\max}]} s_l,p+1,l_{\max},r\right) $$ 最优性显然满足。下面考察转移图的形态,从而说明覆盖性和唯一性。 考察初始状态 $S_r=(w, r-R,r-L, r)$,上述转移的实质是,对 $s_{r-R} \sim s_{r-L}$ 不断从区间 $\min$ 处断开递归。从而转移图是以 $s_{r-R} \sim s_{r-L}$ 的小根笛卡尔树,则转移图恰为以 $S_r$ 为根的外向树。 进一步,整个转移图的形态是以 $S_1 \sim S_n$ 为根的外向树森林,每棵树都是 $s_i$ 的某个特定区间的小根笛卡尔树。 这满足广义覆盖性,可以使用算法 3 解决。 ST 表优化 $p$ 的查找,复杂度 $O(n \log n+k \log k)$。 ::::: :::::info[代码] ```cpp line-numbers const int N = 5e5 + 5; int n, k, L, R, a[N]; using node = pair<int, int>; node st[20][N]; node ask(int l, int r) { int k = lg(r - l + 1); return min(st[k][l], st[k][r - (1<<k) + 1]); } using state = tuple<int, int, int, int>; // (w, l_min, l_max, r) priority_queue<state> q; void _main() { cin >> n >> k >> L >> R; for (int i = 1; i <= n; i++) cin >> a[i], a[i] += a[i - 1]; for (int i = 0; i <= n; i++) st[0][i] = {a[i], i}; for (int i = 1; (1 << i) <= n; i++) for (int j = 0; j <= n; j++) st[i][j] = min(st[i-1][j], st[i-1][j + (1<<(i-1))]); for (int r = L; r <= n; r++) { int lo = max(0, r - R), hi = r - L; q.emplace(a[r] - ask(lo, hi).fi, lo, hi, r); } i64 res = 0; while (k--) { auto [w, lo, hi, r] = q.top(); q.pop(), res += w; int p = ask(lo, hi).se; if (lo < p) q.emplace(a[r] - ask(lo, p-1).fi, lo, p-1, r); if (p < hi) q.emplace(a[r] - ask(p+1, hi).fi, p+1, hi, r); } cout << res; } ``` :::::