一年补一题，一题补一年（1）| [省选联考 2024] 迷宫守卫

· · 个人记录

题目链接

求出答案序列的第一个数是容易的。设 dp_{i,j} 表示以 i 为根的子树内要第一个数 \ge j 的最小代价，处理出每个子树内有的数，离散化一下，合并的时候使用归并排序这部分就可以做到 O(n2^n)。

考虑模拟求答案的过程。考虑设计 \operatorname{dfs}(v,w) 表示当前在 v 为根的子树，可以用 w 的代价，这个函数要求出这个子树内的答案，以及返回剩下的代价。

首先，如果子树内要走的第一个点在右子树，那显然两边都至少要用 dp 的代价。设左子树至少要用 q 的代价，那右子树可以用的代价就有 w-q，即调用 p=\operatorname{dfs}(r_v,w-q)，然后再返回 \operatorname{dfs}(\ell_v,p+q) 即可。

否则，设右子树要用 q 的代价，而可以花费 c 的代价禁止先去右子树走。那么首先左子树还能用的代价是 w-\min(c,q)。调用 p=\operatorname{dfs}(\ell_v,w-\min(c,q))。然后，如果剩下的代价 p+\min(c,q)<q，那就说明一开始只能通过禁止的方式（也就是 c 的代价）避免走到右子树，现在只剩 p 的代价，返回 \operatorname{dfs}(r_v,p)。否则，说明本身就可以把右子树改得使得最小走的比左子树大，因此剩下来了 p+\min(c,q) 的代价。返回 \operatorname{dfs}(r_v,p+\min(c,q))。

直接模拟，复杂度 O(n2^n)。

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0,del##i##verme=int(n);i<del##i##verme;++i)
#define rep1(i,n) for(int i=1,parano##i##a=int(n);i<=parano##i##a;++i)
#define per(i,n) for(int i=int(n)-1;i>=0;--i)
#define per1(i,n) for(int i=int(n);i>=1;--i)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define y0 LingLuo
#define y1 VividCycle
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
using namespace std;
const ll mod1=998244353;
const ll mod2=1000000007;
unsigned time_related_rand()
{
    return unsigned(std::chrono::steady_clock::now().time_since_epoch().count());
}
const ll INF=0x3f3f3f3f3f3f3f3fll;
int t,n;
int q[131072];
ll w[131072];
vector<int> val[131072];
vector<ll> dp[131072];
void solve(int ver)
{
    if(ver>=(1<<n))
    {
        val[ver].pb(q[ver]);val[ver].pb(20120712);
        dp[ver].pb(0);dp[ver].pb(INF);
    }
    else
    {
        int L=ver<<1,R=ver<<1|1;
        solve(L);solve(R);
        int s=int(val[L].size())-1;
        int l=0,r=0;
        while(l!=s||r!=s)
        {
            if(val[L][l]<val[R][r])
            {
                val[ver].pb(val[L][l]);
                dp[ver].pb(min(INF,min(w[ver],dp[R][r])+dp[L][l]));
                ++l;
            }
            else
            {
                val[ver].pb(val[R][r]);
                dp[ver].pb(min(INF,min(w[ver],dp[R][r])+dp[L][l]));
                ++r;
            }
        }
        val[ver].pb(20120712);
        dp[ver].pb(INF);
    }
}
vector<int> answer;
ll dfs(int ver,ll rem)
{
    if(ver>=(1<<n))
    {
        answer.pb(q[ver]);return rem;
    }
    int L=ver<<1,R=ver<<1|1;
    int target=*(upper_bound(dp[ver].begin(),dp[ver].end(),rem)-1-dp[ver].begin()+val[ver].begin());
    ll vl=*(upper_bound(val[L].begin(),val[L].end(),target)-val[L].begin()+dp[L].begin()),
    vr=*(upper_bound(val[R].begin(),val[R].end(),target)-val[R].begin()+dp[R].begin());
    if(binary_search(val[L].begin(),val[L].end(),target))
    {
        ll vval=dfs(L,rem-min(w[ver],vr));
        if(vval+min(w[ver],vr)>=vr) return dfs(R,vval+min(w[ver],vr));
        return dfs(R,vval);
    }
    return dfs(L,dfs(R,rem-vl)+vl);
}
ll s;
void Q()
{
    cin>>n>>s;
    rep1(i,(1<<n)-1) cin>>w[i];
    rep1(i,(1<<n)) cin>>q[i+(1<<n)-1];
    rep1(i,(2<<n)-1)
    {
        val[i].clear();dp[i].clear();
    }
    solve(1);
    answer.clear();
    dfs(1,s);
    for(int x:answer) cout<<x<<" ";
    cout<<'\n';
}
int main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cin>>t;while(t--)Q();
    return 0;
}
/* things to check
1.  int overflow or long long memory need
2.  recursion/array/binary search/dp/loop bounds
3.  precision
4.  special cases(n=1,bounds)
5.  delete debug statements
6.  initialize(especially multi-tests)
7.  = or == , n or m ,++ or -- , i or j , > or >= , < or <=
8.  keep it simple and stupid
9.  do not delete, use // instead
10. operator priority
11. is there anything extra to output?
12. ...
*/

/* something to think about
1. greedy? dp? searching? dp with matrix/ segment tree? binary search?
2. If contains "not", why not ?????? or few affect?
*/