HydroOJ H1081. ‘Riliane Lucifen d’Autriche’ teafrogsf 和他的四面镜子
不妨对 \(a\) 从大到小排序。我们定义一个状态为选取 \(m\) 个数的一种方案。那么要求的就是价值第 \(k\) 大的状态的价值。
设状态 \(S=\{a_1,a_2,\ldots a_m\}\)。定义 \(\operatorname{suc}(S,i)=\{a_1,\ldots,a_{i-1},a_i+1,a_{i+1},\ldots,a_m\}\)，其中 \(i\) 满足条件 \(a_i+1\neq a_{i+1}\)。称一个合法的 \(\operatorname{suc}(S, i)\) 为 \(S\) 的一个后继状态，\(S\) 所有后继状态组成的集合为 \(S\) 的后继状态集合。显然状态 \(S\) 的后继状态集合大小是 \(\mathcal O(m)\) 的；若 \(T\) 是 \(S\) 的后继状态，那么 \(T\) 的价值一定 \(\le S\) 的价值。我们考虑一个类似于 \(\text{bfs}\) 的暴力：用一个堆维护当前候选状态集合，每一次取出当前集合中价值最大的状态，然后将其所有后继状态加入至当前候选状态集合中，这样重复 \(k\) 次后取出的状态即为答案，时间复杂度为 \(\mathcal O(mk)\)。该做法的正确性在于，我们可以利用后继状态转移不重不漏地枚举到所有的状态，而且转移时一定是从高价值的状态转移到低价值的状态。
考虑优化。注意到在刚刚的暴力做法中，后继状态转移确实可以不重不漏地枚举到所有的状态，但其枚举复杂度过高；我们需要一个更高效的转移方式。
对于一个状态 \(S\)，我们将其表示为若干个极大连续段 \(b_1,\ldots b_M\)。定义一次 \(S\) 上转移操作 \(\tau\) 为将 \(S\) 中最后那个极大连续段 \(b_M\) 的某个后缀向后挪一格。显然我们也可以仅通过转移操作 \(\tau\) 不重不漏地枚举出所有的状态，而且该操作也一定是从高价值的状态转移到低价值的状态。但对于一个合法的 \(S\)，操作 \(\tau\) 的数量级为 \(\mathcal O(|b_M|)\)，直接做的时间复杂度也是 \(\mathcal O(mk)\) 的。
设 \(b_M=\{a_l,a_{l+1},\ldots a_{r}\}\) 定义 \(S_i=\{b_1,b_2,\ldots, b'_M=\{a_l,\ldots,a_{i-1},a_{i+1},\ldots a_{r+1}\}\}\)。那么状态 \(S\) 可以通过操作 \(\tau\) 转移到 \(S_l,S_{l+1},\ldots S_r\)。更进一步地，我们发现 \(S_i\) 的价值单调不递减，即若 \(i<j\) 则 \(S_i\) 的价值 \(<S_j\) 的价值。因此我们可以隐隐约约地感觉到操作 \(\tau\) 的转移时多余的。
我们考虑建立一个 \(S_i\rightarrow S_{i-1}\) 的转移，因此可以定义操作 \(\tau'\) 为：
- 将 \(b_M\) 的最后一位向后挪一格，变为 \(b'_M=\{a_l,\ldots a_{r-1}\},\,b_{M+1}'=\{a_{r+1}\}\)；
- 若 \(b_{M-1}\) 和 \(b_M\) 中间只隔一位，则可以将 \(b_{M-1}\) 的最后一位向后挪一格，变为 \(b'_{M-1}=\{a_{l_1},\ldots,a_{r_1-1}\},\,b'_M=\{a_{r_1+1},a_{l_2=r_1+2},\ldots a_{r_2}\}\)。
其中第二种操作相当于是在 \(S_{i}\) 和 \(S_{i-1}\) 建立了转移关系。我们发现操作 \(\tau'\) 依然可以不重不漏地枚举出所有的状态，而且该操作也是从高价值的状态转移到低价值的状态。更进一步地，对于一个状态 \(S\)，其转移操作 \(\tau'\) 的数量级为 \(\mathcal O(1)\)。由于我们使用堆维护状态，因此时间复杂度为 \(\mathcal O(k\log n)\)。
具体的实现方式，我们注意到状态 \(S\) 有用的部分就是最后两个极大连续段，因此只需维护每个状态的最后两个极大连续段即可。
参考代码
#include <bits/stdc++.h>
using namespace std;
static constexpr int Maxn = 1e6 + 5;
int n, m, k;
int64_t a[Maxn], s[Maxn];
struct node {
int x, y, l;
int64_t s;
bool count;
node() = default;
node(int x, int y, int l, int64_t s, bool count)
: x(x), y(y), l(l), s(s), count(count) { }
friend bool operator < (const node &lhs, const node &rhs) {
return lhs.s < rhs.s;
} // <node>::operator <
};
int main(void) {
scanf("%d%d%d", &n, &m, &k);
for (int i = 1; i <= n; ++i) scanf("%lld", &a[i]);
sort(a + 1, a + n + 1, greater<>());
for (int i = 1; i <= n; ++i) s[i] = s[i - 1] + a[i];
priority_queue<node> pq; pq.emplace(1, m, m, s[m], true);
while (k && !pq.empty()) {
auto [x, y, l, S, c] = pq.top(); pq.pop();
if ((k -= c) == 0) return printf("%lld\n", S), 0;
if (y != l) pq.emplace(x + y + 1, l - y, l - y, S, false);
if (y != 1 && x + y <= n) pq.emplace(x, y - 1, l, S + a[x + y] - a[x + y - 1], true);
if (y == 1 && x + l <= n) pq.emplace(x + 1, l, l, S - a[x] + a[x + 1], true);
} puts("-1");
exit(EXIT_SUCCESS);
} // main