题解：P2541 [USACO16DEC] Robotic Cow Herd P

stripe_python · 2026-07-22 09:43:53 · 题解

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 的复杂度瓶颈：

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}

• 维护小根堆 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 小解的和。

首先对所有 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。