P8293 [省选联考 2022] 序列变换

Alex_Wei · 2022-04-19 19:43:37 · 题解

*VI. P8293 [省选联考 2022] 序列变换

感谢 chenxia25 和 Kubic 的指教。

题目希望我们将原括号序列转化为形如 ((((...)))) 嵌套的括号序列。

自然考虑抽象题意，解剖两个操作的本质是什么。因为光看括号上的变换似乎没有什么眉目。

将括号序列建树，我们发现操作 1 形如将树上某个节点的两个儿子 a 和 b 进行如下变换：将 b 的所有儿子挂到 a 上，并将 b 挂到 a 上（指将 b 变成 a 的儿子），代价即 xv_a + yv_b（一个节点的权值即其对应的括号的权值）。而操作 2 说明对于某个节点的若干儿子，我们可以以任意顺序执行该操作，即同层节点之间顺序无关。最终我们希望将这棵树变成一条链。

第一步贪心是从浅到深进行所有这样的操作，因为操作 1 使得一些当前层的节点被下调至下一层，最终仅在当前层留下一个节点。也就是说在节点被不断下调的过程中，先操作上面的节点，再操作下面的节点的自由度最大。

显然，对于不同的 x, y，策略也是不同的。或者说，由于 x, y 的情况数很少，我们不妨分类讨论以简化问题。

当 x = y = 0 时，答案显然为 0。
当 x = 0，y = 1 时，合并代价为被解剖的节点的权值。我们知道被解剖的节点会下放到下一层，因此代价可以看做当前层所有节点权值之和，减去留在当前层的节点的权值。很显然，在当前层留下权值最大的节点即可。通过 multiset 维护。
当 x = 1，y = 1 时，合并代价为被解剖的节点的权值，加上接受被解剖的节点的权值。仍然是考虑留下一个节点。当被留下的节点已经定下来时，为使代价最小，当留下的权值非本层最小值时，最优方案为先把丢到下一层的非本层最小值的节点挂到本层最小值上面，再把本层最小值挂到被留下的节点上，否则留下的权值为本层最小值，下放的节点全部挂上去。无论是哪种情况，代价均为本层最小值乘以 sz_i - 2（sz_i 是第 i 层的节点个数，这个是不为我们下放了什么节点而改变的，在括号树的形态固定下来时就已经确定了，因为每一层下放的节点个数是确定的），加上本层所有节点的和。显然，在当前层留下权值最大的节点即可。
当 x = 1，y = 0 时，当被留下的节点已经定下来时，策略和上一种情况是一致的。因此，不难分析得到代价为本层最小值乘以 sz_i - 2 加上本层被留下的节点的权值。单看一层的贡献似乎有些不好考虑，因为我们可以尝试将一个最大值不断下放直到最后一层，使得它对答案不会有贡献。但总体来看，由于所有除了被下放至最后一层的节点均会以某一层被留下的节点的形式贡献至答案，所以总贡献即所有节点权值的和减去被下放至最后一层的节点权值，再加上每一层的权值最小值乘以 sz_i - 2。这意味着我们希望 既能下放最小值，也能下放最大值（本题的关键结论）。

当 sz_i = 1 时，没有能够下放的节点，所以忽略一开始的极长的连续的 1。

当 sz_i > 2 时，我们可以留下非最小值且非最大值。

当 sz_i = 2 时有些难办。注意到最终 sz 形如 2, 2, \cdots, 2, \geq3, \cdots, \geq 3, 2, 1（当 sz 下降时，原树该层已经没有节点，所以最终有且只会有一个 2，对于这一层我们的策略显然是下放最大值），并且 sz = 2 的层的代价为该层留下的节点，所以对于开头的极长的 2，这些层的总代价为所有涉及到的节点权值之和，减去唯一（显然）一个下放的节点的权值。直接枚举这个下放节点的权值，可以得到一个 \mathcal{O}(n ^ 2) 的做法，但是不够优秀。

通过从小到大枚举下放节点的权值可以做到 n\log n，是排序的线性对数，剩下来只需维护一个指针 p 表示如果当前节点 v 下放，那么它最后一次作为最小值是在哪一层（可以通过预处理 \geq 3 的权值前缀 \min 实现），然后通过 sz 的前缀和快速求出结果，同时容易判断 v 是否会成为最大值下放至最后一层，从而快速计算这种方案的贡献，更新答案。但是还是不够优秀。

既然我们希望能下放最小值或最大值，那么对于 2 段而言，它也仅会下放最小值或最大值。因为下放最小值能让 3 段的最小值尽量小，而下放最大值能让留在最后一层的数尽量大。因此直接模拟下放最小值或最大值即可。时间复杂度线性。

综上，对于 x = y = 0，时间复杂度 \mathcal{O}(1)。对于 x = 1 且 y = 0，时间复杂度线性。剩下来两种情况时间复杂度线性对数。

代码很好写。

#include <bits/stdc++.h>
using namespace std;
const int N = 4e5 + 5;
int n, x, y, v[N], stc[N];
char s[N << 1];
vector <int> buc[N];
multiset <int> t;
long long ans, sum;
int main() {
    cin >> n >> x >> y >> s + 1;
    for(int i = 1; i <= n; i++) scanf("%d", &v[i]);
    for(int i = 1, top = 0, cnt = 0; i <= n << 1; i++)
        if(s[i] == '(') stc[++top] = ++cnt;
        else buc[top].push_back(v[stc[top]]), top--;
    if(x == 0 && y == 0) ;
    else if(x == 0 && y == 1) {
        for(int i = 1; i < n; i++) {
            for(int it : buc[i]) t.insert(it), sum += it;
            ans += sum -= *--t.end(), t.erase(--t.end());
        }
    }
    else if(x == 1 && y == 1) {
        for(int i = 1; i < n; i++) {
            for(int it : buc[i]) t.insert(it), sum += it;
            ans += *t.begin() * (t.size() - 2) + sum;
            sum -= *--t.end(), t.erase(--t.end());
        }
    }
    else {
        static int sz[N] = {1}, mx[N], mn[N], p = 1, q = 1;
        memset(mx, 0, sizeof(mx)), memset(mn, 0x3f, sizeof(mn));
        for(int i = 1; i <= n; i++) sz[i] = sz[i - 1] + buc[i].size() - 1;
        while(p <= n && sz[p] == 1) p++, q++;
        while(q <= n && sz[q] == 2) q++;
        for(int i = p; i < n; i++) {
            if(i != q) mn[i] = mn[i - 1], mx[i] = mx[i - 1];
            for(int it : buc[i]) mn[i] = min(mn[i], it), mx[i] = max(mx[i], it), sum += it;
        }
        long long res1 = sum - mx[n - 1], res2 = sum - max(mx[q - 1], mx[n - 1]); // res1 是下放最小值，res2 是下放最大值
        for(int i = q; i < n; i++) res1 += 1ll * (sz[i] - 2) * min(mn[q - 1], mn[i]), res2 += 1ll * (sz[i] - 2) * mn[i];
        ans = min(res1, res2);
    }
    cout << ans << endl;
    return 0;
}