Shopping Plans Trick
stripe_python
·
·
个人记录
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}
- 维护小根堆 Q 和集合 S,初始时令 x_1 入堆。
- 重复以下流程,直到解序列的长度达到 k。
- 弹出 Q 的堆顶元素 x。若 \mathbf{x \notin S} 则将 x 加入解序列。
- 令 S \gets S \cup \{x\}。
- 枚举 (x,y) \in E,令 y 加入 Q。
:::::
算法 1 等价于在 DAG 上进行 Dijkstra。
注意到算法 1 并不需要显式建出 G。观察算法 1 的复杂度瓶颈:
- 枚举 (x, y) \in E 的所有的 y。
- 判定 x \in S 是否成立,修改 S \gets S \cup \{x\}。
一般地,认为可以在 O(1) 内解决问题一。若问题二存在 O(\log |S|) 的高效算法,算法 1 的复杂度即为 O(k \log k)。
更一般地,认定问题二不存在高效算法。注意到 G 的形态是以 x_1 为根的外向树时,有如下算法成立:
:::::info[算法 2]{open}
- 维护小根堆 Q,初始时令 x_1 入堆。
- 重复以下流程 k 轮。
- 弹出 Q 的堆顶元素 x。直接将 x 加入解序列。
- 枚举 (x,y) \in E,令 y 加入 Q。
:::::
这是 Shopping Plans Trick 的一般性算法。易知复杂度 O(k \log k)。
我们考察算法 2 的本质。形式化地,我们对全体 x \in \Omega 构造了转移集合 \text{trans}(x),且转移满足下列性质:
- 最优性:\forall x \in \Omega, \forall y \in \text{trans}(x) , f(y) > f(x)。
- 覆盖性:\forall x \in \Omega,x_1 \to x 可达。
- 唯一性:\forall x,y \in \Omega \land x\ne y, \text{trans}(x) \cap \text{trans}(y)=\varnothing。
两种算法都需要满足最优性和覆盖性,算法 2 需要满足唯一性。
进一步,对覆盖性进行扩展:
- 广义覆盖性:\exists x_1',x_2', \cdots, x_m' \in \Omega,\forall x \in \Omega,\exists 1 \le i \le m,x_i' \to x 可达。
若 \text{trans} 仍满足最优性和唯一性,有如下算法成立:
:::::info[算法 3]{open}
- 维护小根堆 Q,初始时令 x_1',x_2',\cdots,x_m' 入堆。
- 重复以下流程 k 轮。
- 弹出 Q 的堆顶元素 x。直接将 x 加入解序列。
- 枚举 (x,y) \in E,令 y 加入 Q。
:::::
若 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)。
显见最优性成立,下证覆盖性和唯一性成立:
- 覆盖性:\forall (i,j) \in \Omega,构造 (1,1) \to (i,j) 的路径为,先使用 i-1 次 (i,j) \to (i+1,j) 的规则到达 (i,1),再使用 j-1 次 (i,j) \to (i,j+1) 的规则到达 (i,j)。
- 唯一性:只要证转移图是以 (1,1) 为根的外向树,即 \forall (i,j) \in \Omega \land (i,j) \ne (1,1),其存在唯一前驱。
- 若 j=1 \land i>1,仅有 (i-1,1) \to (i,1)。
- 若 j>1,由于 j \ne 1 不存在 (i-1,j) 的转移,从而仅有 (i,j-1) \to (i,j)。
使用算法 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,S \to (w-a_{i,p_i}+a_{i,p_i+1},i, p_i+1,\cdots)。
- 枚举指针 j \in (i,n] 并决策移动指针 p_j,S \to (w+\delta_j,j,2,p_{j+1},\cdots)。
观察上述转移,可以发现 (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;
}
```
:::::