Solution. LG10220 [省选联考 2024] 迷宫守卫

Description

给一棵 $n+1$ 层的完全二叉树（共 $2^{n+1}-1$ 个结点，$2^n$ 个叶子），结点从上到下，从左到右编号为 $1\sim 2^{n+1}-1$，每个非叶结点有一个激活代价 $w_i$，每个叶子有一个权值 $q_i$，所有 $q_i$ 构成 $1\sim 2^n$ 的排列。Alice 和 Bob 在这棵树上玩游戏，Alice 可以用不超过 $K$ 的代价激活一些结点，随后 Bob 会对这棵树进行 dfs。对于 Alice 激活的结点，Bob 必须先走左儿子再走右儿子；其余时候，Bob 可以任意决定 dfs 顺序。

按照 Bob 访问叶子的顺序将所有 $q_i$ 排成序列 $Q$，Alice 希望 $Q$ 的字典序最大，Bob 希望 $Q$ 的字典序最小，问最终的 $Q$ 是什么。

$T$ 组数据。

$1\le T\le 100,1\le n\le 16,1\le \sum 2^n\le 10^5,0\le K\le10^{12},0\le w_i\le 10^{12}$

Solution

令 $N\gets 2^n$。

Alice 想让 $Q$ 的字典序最大，所以首先会希望最大化 $Q$ 中的第一个数。考场上我认为直接 dp 求解第一个数最大能是多少比较困难，虽然事实是这样做也可以，但是我们还是来考虑二分。

这样我们得到了一个判定性问题，只需判断 $Q$ 的第一个数能否 $\ge mid$ 即可。为了达成这一点，Alice 需要封锁所有 $< mid$ 的位置。考虑 dp 解决这一问题，设 $f_u$ 表示封锁 $u$ 子树内所有 $< mid$ 的位置的最小代价。转移时，首先可以分别封锁 $u$ 的左右儿子，$f_u\gets f_{ls}+f_{rs}$；其次可以激活 $u$，使得 Bob 第一次到达 $u$ 时不能走向右儿子，仅封锁左儿子即可，$f_u\gets f_{ls}+w_u$。初始状态为，所有 $\ge mid$ 的叶子为 $0$，$< mid$ 的叶子为 $\infty$。

求出 $Q$ 第一个数的最大值 $x$ 后，我们定位出根到 $x$ 的路径，这将是 Bob 第一次到达叶子的路径，这条路径将整棵树分成了 $O(\log N)$ 棵子树，Bob 将会按照从深到浅的顺序访问这些子树，这样就递归出了 $O(\log N)$ 个规模更小的子问题。

这里注意，在得到这些子问题的可用代价时，设令 $Q$ 第一个数为 $x$ 的最小代价为 $K_0$，我们并不能简单的从 $K$ 中减去 $K_0$。

考虑 $x\rightsquigarrow root$ 上除 $x$ 外的某个点 $u$，设 $x$ 在 $u$ 的左子树中。若 $f_u$ 是从 $f_{ls}+f_{rs}$ 转移而来，那么在递归 $u$ 右子树时，$f_{rs}$ 作为封锁右子树的代价需要被交还到 $K$ 中；若 $f_u$ 从 $f_{ls}+w_u$ 转移而来，这种决策在我们希望最大化右子树字典序时实际上不优，我们考虑剩余的 $K$ 是否允许 $f_u$ 从 $f_{ls}+f_{rs}$ 转移，换言之是在判断右子树访问到的第一个叶子能否 $>x$，若可行，则将 $w_u$ 交还给 $K$，注意若 $x$ 在 $u$ 右子树中时不存在这种情况。

容易说明总复杂度为 $O(N\log N)$，或 $O(n2^n)$。

代码十分简洁。

Code

namespace Main{
    const int N = 200005;
    int t, n, q[N]; ll k, w[N], f[N];
    inline bool is_leaf(int u) { return u >= (1 << n); }
    void dfs(int u, const int &mid){
        if(is_leaf(u)){
            if(q[u] < mid) f[u] = 1e18;
            else f[u] = 0;
            return;
        }
        dfs(u << 1, mid), dfs(u << 1 | 1, mid);
        f[u] = min(f[u << 1] + f[u << 1 | 1], f[u << 1] + w[u]);
    }
    vector<int> solve(int u){
        if(is_leaf(u)) return {q[u]};
        vector<int> all;
        int d = 31 - __builtin_clz(u);
        for(int i = u << (n - d); i < (u + 1) << (n - d); i++){
            all.push_back(q[i]);
        }
        sort(all.begin(), all.end());
        int L = 0, R = all.size() - 1, res = 0;
        while(L <= R){
            int mid = L + R >> 1;
            dfs(u, all[mid]);
            if(f[u] <= k) L = mid + 1, res = mid;
            else R = mid - 1;
        }
        vector<int> ans = {all[res]};
        int p = -1;
        for(int i = u << (n - d); i < (u + 1) << (n - d); i++){
            if(q[i] == all[res]) { p = i; break; }
        }
        dfs(u, all[res]);
        // cerr << u << ' ' << k << ' ' << f[u] << endl;
        k -= f[u];
        for(int i = p; i != u; i >>= 1){
            if(i & 1) k += f[i ^ 1];
            else if(f[i] + f[i ^ 1] - f[i >> 1] <= k) k += min(f[i ^ 1], w[i >> 1]);
            vector<int> tmp = solve(i ^ 1);
            ans.insert(ans.end(), tmp.begin(), tmp.end());
        }
        return ans;
    }
    void Main(){
        input(t);
        while(t--){
            input(n, k);
            for(int i = 1; i < (1 << n); i++) input(w[i]);
            for(int i = (1 << n); i < (1 << (n + 1)); i++) input(q[i]);
            vector<int> ans = solve(1);
            for(int x: ans) write(x), putchar(' ');
            puts("");
        }
        return;
    }
}

本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。