[CF1311E] Construct the Binary Tree

Solution

预处理出 \(i\) 个点组成的二叉树的最大答案和最小答案

递归做，由于只需要构造一种方案，我们让左子树大小能小就小，因此每次从小到大枚举左子树的点数并检验，如果检验通过就选定之

现在还需要确定左右子树各分配多少答案上去，一种构造性的想法是，要么让左子树选最小，要么让右子树选最大。对于任意一种其它方案，我们可以通过把左子树上的答案不断移到右子树上，直到某一边达到界限，故等价。

打错变量名查半天……

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 5005;

int T,n,d,mx[N],mn[N],f[N];

void dfs(int tot,int off,int sum) {

    for(int i=0;i<tot;i++) {

        int lsiz=i, rsiz=tot-1-i;

        int vmin=mn[lsiz]+mn[rsiz]+tot-1;

        int vmax=mx[lsiz]+mx[rsiz]+tot-1;

        if(vmin<=sum && sum<=vmax) {

            int tmp=mn[lsiz];

            if(mn[lsiz]+mx[tot-1-lsiz]+tot-1<sum) tmp=sum-tot+1-mx[tot-1-lsiz];

            if(lsiz) {

                f[off+1]=off;

                dfs(lsiz,off+1,tmp);

            }

            if(rsiz) {

                f[off+1+lsiz]=off;

                dfs(rsiz,off+1+lsiz,sum-tot+1-tmp);

            }

            return;

        }

    }

}

signed main() {

    ios::sync_with_stdio(false);

    for(int i=1;i<=5000;i++) {

        mx[i]=i*(i-1)/2;

        mn[i]=mn[i-1]+(int)(log2(i)+1e-7);

    }

    cin>>T;

    while(T--) {

        cin>>n>>d;

        if(d<mn[n] || d>mx[n]) cout<<"NO"<<endl;

        else {

            cout<<"YES"<<endl;

            dfs(n,1,d);

            for(int i=2;i<=n;i++) cout<<f[i]<<" ";

            cout<<endl;

        }

    }

}

巴特西

[CF1311E] Construct the Binary Tree - 构造

Solution

最新文章

热门文章