[省选联考 2024] 迷宫守卫

· · 题解

考虑 Bob 只选一个叶子时怎么做。

那么 Alice 每选择一个点，就相当于把右子树删掉，最后要使剩下数中的最小值最大。

考虑 DP 记 f_{u,j} 表示使 u 子树内最小值大于等于 j 的最小代价。

转移有 f_{u,j}=f_{ls_u,j}+\min(f_{rs_u,j},w_u)。

直接记录状态是 O(4^n)，因为树是满二叉树，可以对 j 这一维离散化，这样状态就是 O(n 2^n) 的。

转移可以用归并排序做到 O(n 2^n)。

求出 f 后，找到最大的 j 使得 f_{1,j}\le K，这就是 Bob 选的叶子。

考虑如何利用 f 求出所有答案，直接模拟 Bob 在树上行走。

设计函数 \operatorname{dfs}(u,K) 表示 Bob 走到了 u 节点，Alice 还有 K 的魔力值，函数返回 Alice 在 u 子树内花费的魔力值。

一样找到最大的 j 使得 f_{u,j}\le K，则 Bob 下一个叶子会走向 j。

如果 j 在右子树，说明 Alice 一定不会选 u，那么依次调用 g=\operatorname{dfs}(rs_u,K-f_{ls_u,j})，\operatorname{dfs}(ls_u,K-g) 即可。

如果 j 在左子树，先调用 g=\operatorname{dfs}(ls_u,K-\min(w_u,f_{rs_u,j}))。

这时候我们要考虑 Alice 是否选择 w_u，请注意，并不是 w_u\le f_{rs_u,j} 就会选择 w_u。

因为我们选择了 w_u 会使得 Alice 在右子树的选择更少，只有在我们不选 w_u 的情况下，左子树答案会改变才会选。

具体的，只有 g\gt K-f_{rs_u,j} 时，我们才会选 w_u。

判断出是否选 w_u 后，剩下的过程和 j 在右子树的情况类似。

时间复杂度 O(n2^n)。

参考代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=(1<<17)+5;
const ll inf=1e13;
int T,n,tn,a[N],rv[N],b[N],cb,c[18][N];
ll w[N],m,f[18][N],fl[18][N],fr[18][N];
bool vw[18][N];
#define ls(x) ((x)<<1)
#define rs(x) ((x)<<1|1)
void dfs(int x,int l,int r,int d){
    if(x>=tn){
        f[d][l]=0,c[d][l]=a[x];
        return;
    }
    int mid=l+r>>1;
    dfs(ls(x),l,mid,d+1),dfs(rs(x),mid+1,r,d+1);
    int i=l,j=mid+1,k=l;
    ll vl=0,vr=0;
    while(i<=mid&&j<=r){
        if(c[d+1][i]<c[d+1][j]){
            c[d][k]=c[d+1][i];
            vl=f[d+1][i];
            vr=f[d+1][j];
            ++i;
        }else{
            c[d][k]=c[d+1][j];
            vr=f[d+1][j];
            vl=f[d+1][i];
            ++j;
        }
        fl[d][k]=vl,fr[d][k]=vr;
        if(w[x]<vr)vw[d][k]=true;
        else vw[d][k]=false;
        f[d][k]=min(inf,fl[d][k]+min(w[x],fr[d][k]));
        ++k;
    }
    while(i<=mid){
        c[d][k]=c[d+1][i];
        vl=f[d+1][i];
        vr=inf;
        ++i;
        fl[d][k]=vl,fr[d][k]=vr;
        if(w[x]<vr)vw[d][k]=true;
        else vw[d][k]=false;
        f[d][k]=min(inf,fl[d][k]+min(w[x],fr[d][k]));
        ++k;
    }
    while(j<=r){
        c[d][k]=c[d+1][j];
        vr=f[d+1][j];
        vl=inf;
        ++j;
        fl[d][k]=vl,fr[d][k]=vr;
        if(w[x]<vr)vw[d][k]=true;
        else vw[d][k]=false;
        f[d][k]=min(inf,fl[d][k]+min(w[x],fr[d][k]));
        ++k;
    }
}
ll calc(int x,int l,int r,ll rs,int d){
    if(l==r){
        b[++cb]=a[x];
        return 0;
    }
    int mid=l+r>>1;
    int j=r;
    while(j>l&&fl[d][j]+min(w[x],fr[d][j])>rs)--j;
    ll res=0;
    if(rv[c[d][j]]<=mid){
        res=calc(ls(x),l,mid,rs-min(w[x],fr[d][j]),d+1);
        if(vw[d][j]&&rs-fr[d][j]<res)res+=w[x];
        rs-=res;
        res+=calc(rs(x),mid+1,r,rs,d+1);
    }else{
        res=calc(rs(x),mid+1,r,rs-fl[d][j],d+1);
        rs-=res;
        res+=calc(ls(x),l,mid,rs,d+1);
    }
    return res;
}
void solve(){
    scanf("%d%lld",&n,&m);
    tn=1<<n,cb=0;
    for(int i=1;i<tn;++i)scanf("%lld",&w[i]);
    for(int i=0;i<tn;++i){
        scanf("%d",&a[i+tn]);
        rv[a[i+tn]]=i;
    }
    dfs(1,0,tn-1,0);
    calc(1,0,tn-1,m,0);
    for(int i=1;i<=tn;++i)printf("%d%c",b[i]," \n"[i==tn]);
}
int main(){
    scanf("%d",&T);
    while(T--)solve();
    return 0;
}