省选联考 2024 D2T1 题解

· · 题解

省选联考 2024 D2T1

前言

Day1 发挥不完全，Day2 完全不发挥。

Day2 场上写这题写了 4h 25min，并且最终也只写了个假做法，最后两分钟在 T2 输出了 1 ，并获得了总分 5 分的好成绩。

赛后又瞪了两个小时终于做出来了这题，但是只能来写个题解了，只能说菜就多练。

这是本蒟蒻的第一篇洛谷题解，写此题解纪念这道葬送了我一整场省选 Day2 的题。

第一篇题解，表达能力不佳，请见谅。

题解

首先题目要访问序列的字典序最小，意思就是直接让你从前往后贪心。

下文中用选择一个点表示唤醒这个点的石像守卫。

所以 Bob 显然会先让第一个数最小，然后第二个，然后再是后面的。Alice 要做的是把 Bob 卡到最大。

先考虑第一个数怎么选。

首先发现答案具有单调性，所以可以二分第一个数是 x，然后 Alice 要做的就是使所有的 <x 的数全部不能让 Bob 第一次作为叶子访问到。

那么 Alice 能做到的充要条件是能够使对于每一个 y<x 的叶子，其到根的路径上的所有点中需至少选择一个使得 y 是这个点的右子树中的点。

可以使用一次树形 dp 在 O(siz) 的复杂度内求出每一次二分的最小代价。

因为优先使第一个最大，所以我们二分出代价 \le m 的最大可能取到的值，设此时的最终结果的叶子为 p。

然后题目要求 Bob 是以 dfs 的方式访问整个树，所以下一步肯定是访问 p 的兄弟节点（即 p 的父节点的另一个子节点）的子树，然后是 p 的父节点的兄弟节点，以此类推。

因为是二分，所以 p 到当前子树的根的路径上一定可以走。

还是因为在前面的优先，所以当访问 p 的兄弟节点时，p 的祖先的兄弟节点子树内部的选择方案先按照当前子树决策，使得代价最小。

而 p 的兄弟节点内部因为会有其他的节点选择，所以当前子树的决策方案不一定是最优的，需要整个重做。所以先把 m 减去当前子树需要的代价，然后再加上 p 的兄弟按照当前子树方案所需的代价，进入 p 兄弟的子问题。

对于 p 兄弟的子问题，需要分 p 的父节点选不选，选的话就需要加上其代价，不选的话还需要求兄弟节点子树内第一个访问的叶子上的数要大于 p 上的数，只需直接把 p 的数和二分的数取 max 即可，树形 dp 会自动判掉非法情况。

（好好理解一下这里，赛场上就是没想明白这里然后就寄了，做这种题一定要彻底想明白再开始写）。

然后把 p 变成 p 的父节点，继续执行上述子问题（加上 p 的兄弟按照当前子树方案所需的代价，进入 p 兄弟的子问题）直到 p 变为当前子树的根。

到这里这题就做完了，下面是时间复杂度的证明。

设 T(n) 为高度为 n 的子树所需要的时间，显然子树内的操作（除去子问题递归外）需要的时间为 O(siz\log siz)=O(2^nn) ，则

T(n)=O(2^nn)+\sum_{i=0}^{n-1}T(i)

设 S(n)=\sum_{i=0}^nT(i)，则

S(n)-S(n-1)=O(2^nn)+S(n-1) S(n)=2S(n-1)+O(2^nn)=\sum_{k=0}^nO(2^kk)\times 2^{n-k}=O(2^nn^2) T(n)=S(n)-S(n-1)=O(2^nn^2)

证毕。

时间复杂度 O(2^nn^2) 。

500ms不知道在卡什么

代码

非常好写，但是真的难想。

#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define pb push_back
#define pii pair<ll,ll>
#define fi first
#define se second
using namespace std;
const ll N=2e5+2,P=1e12+1;
ll T,n,m,k,a[N],b[N];
pii c[N];
ll dfs(ll x,ll h){
    if(x>=(1<<n))return(a[x]<h?P:0);
    ll p=dfs(x<<1,h),q=dfs(x<<1|1,h);
    return p+min(a[x],q);
}
void Dfs(ll x,ll h){
    if(x>=(1<<n)){
        if(a[x]<h)m-=a[x>>1];
        return b[++k]=a[x],void();
    }
    ll l=x,r=x,f=0;
    while(l<(1<<n))l<<=1;
    while(r<(1<<n))r=(r<<1|1);
    for(ll i=l;i<=r;i++)c[++f]={a[i],i};
    sort(c+1,c+f+1),l=1,r=f;
    ll p=0,s=0;
    while(l<=r){
        ll mid=l+r>>1;
        ll v=dfs(x,max(c[mid].fi,h));
        if(x&(x>1&&c[mid].fi<h))
            v=min(v,dfs(x,c[mid].fi)+a[x>>1]);
        if(v>m)r=mid-1;
        else l=mid+1,p=c[mid].se,s=v;
    }
    m-=s,b[++k]=h=a[p];
    do
        m+=min(p&1?P:a[p>>1],dfs(p^1,h)),
        Dfs(p^1,h),p>>=1;
    while(p!=x);
}
void slv(){
    cin>>n>>m,k=0;
    for(ll i=1;i<(1<<n+1);i++)cin>>a[i];
    Dfs(1,0);
    for(ll i=1;i<=k;i++)cout<<b[i]<<' ';
    cout<<'\n';
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>T;
    while(T--)slv();
    return 0;
}