题解：P14626 [2018 KAIST RUN Fall] Fake Plastic Trees

· · 题解

说一下我的广搜构造方法。

题意

我们要构造一棵叶子结点数为 N 的虚假塑料树，并满足所有中间构造的树都是虚假塑料树，且非空树节点不超过 125 个。

思路

对于一棵虚假塑料树 T = (T_1,T_2) 其大小 |T| = |T_1| + |T_2|，要满足 |T_1| = |T_2| 或 |T_1| = |T_2| + 1。\ 所以我们可以将 N 拆成 |T_1| = \lceil \frac{N}{2} \rceil 和 |T_2| = \lfloor \frac{N}{2} \rfloor。

我们可以先分解子树，存储子树大小。\ 然后将所有出现过的子树按大小从小到大排序，并用 map 映射，记录编号。\ 最后对于每一棵树，记录它的左右子树。

该方法的实际用到的非空树节点为 O(\log N)，远小于 125。\ 时间复杂度：O(\log N)。

具体实现可以看代码。 :::success[代码]

#include<bits/stdc++.h>
#define int long long
using namespace std;
int t,n,k,ans,sum1[130],sum2[130];
set<int> s;
vector<int> v;
map<int,int> mp;
signed main(){
    cin >> t;
    while(t--){
        cin >> n;
        k=0;
        ans=0;
        s.clear();
        v.clear();
        mp.clear();
        s.insert(n);
        v.push_back(n);
        while(k<v.size()){//收集子树大小
            int x=v[k++];
            if(x==1) continue;
            int a=(x+1)/2,b=x/2;
            if(s.find(a)==s.end()){
                s.insert(a);
                v.push_back(a);
            }
            if(s.find(b)==s.end()){
                s.insert(b);
                v.push_back(b);
            }
        }
        sort(v.begin(),v.end());//排序
        for(int i=0;i<v.size();i++){//建立映射
            if(v[i]==1){
                mp[v[i]]=ans++;
                continue;
            }
            mp[v[i]]=ans++;
        }
        for(int i=0;i<v.size();i++){//构建每棵树的左右指针
            if(v[i]==1){
                sum1[mp[1]]=sum2[mp[1]]=-1;
            }else{
                int a=(v[i]+1)/2,b=v[i]/2;
                sum1[mp[v[i]]]=mp[a];
                sum2[mp[v[i]]]=mp[b];
            }
        }
        cout << ans << '\n';
        for(int i=0;i<ans;i++) cout << sum1[i] << " " << sum2[i] << '\n';
        cout << mp[n] << '\n';
    }
    return 0;
}

:::