P2274 [HNOI2002]树的排序 题解

· · 题解

upd 20220901：叕修正了一些格式问题。

前置芝士

Catalan 数

这篇文章的第三个应用指出：给定 n 个点，能构成 h_n 种不同的二叉树（记 h_n 为第 n 项 Catalan 数）。

证明很简单，文章里也有，这里不再赘述。

所以可以打个表得到前 20 项 Catalan 数（多打了几个），发现已经超过数据规模了。

正文

这题的关键是给定二叉树编号，分别求出左子树和右子树的编号。

数学方法我不会，考虑枚举并验证。

对于一个结点数为 x 的子树，我们枚举左子树的结点数量 i，自然右子树的的结点数量为 x-i-1。

设 y 表示右子树剩余的编号。如果 y 大于所有左子树的结点数量为 i，右子树的的结点数量为 x-i-1 的二叉树种类数量。y 就减去这个数量 h[i]×h[x-i-1]（乘法原理）。

如果不够减就意味着我们已经找到了合法的左右结点数量了。递归求解左右子树即可。

注意：左子树的编号是 \lfloor \frac{y-1}{h[x-i-1]} \rfloor+1，原因是右边可能数每加一组，左子树就要多一个编号（类似于进位），y-1 是因为从 1 开始（要求的是加在右边的步数），+1 同理。

细节很多，代码加了注释方便食用（注释非解法思路，仅是把各个步骤的意义注明便于对照查看）。

code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,v,flag;
ll h[25]={1,1,2,5,14,42,132,429,1430,4862,16796,58786,208012,742900,2674440,9694845,35357670,129644790,477638700,1767263190,6564120420,24466267020};
void dfs(ll x,ll y)
{
    if(!x)  return;//结点数为0，不用管了 

    //在这以后y是右子树剩余的编号（因为要减它加到左子树）
    for(int i=0;i<=x-1;i++)//枚举左子树大小 
    {
        //i是左子树结点数，x-i-1是右子树结点数（加起来是x-1正好去掉了根结点）
        if(y>h[i]*h[x-i-1])//够减就减掉 
        {
            y-=h[i]*h[x-i-1];
        }
        else//不够减，得到了左右子树的大小了 
        {
            if(flag)//已经输出过全树的根结点，这是子树
            {
                cout<<"(";
                dfs(i,(y-1)/h[x-i-1]+1);//左边数量，左边编号数
                cout<<"X";
                dfs(x-i-1,(y-1)%h[x-i-1]+1);//右边数量，右边编号数
                cout<<")";
            }
            else//没输出全树的根结点时flag==0
            {   //输出根结点，不用打括号
                flag=1;
                dfs(i,(y-1)/h[x-i-1]+1);
                cout<<"X";
                dfs(x-i-1,(y-1)%h[x-i-1]+1);
            }
            break;
        }
    }
}

int main()
{
    cin>>n;
    flag=0;//没有输出过根结点
    for(int i=1;i<=20;i++)
    {
        if(n<=h[i])
        {
            dfs(i,n);//i是结点数，n是在相同结点数的树中的编号
            break;
        }
        n-=h[i];//减去之前的编号 
    }
    return 0;
}

附上打表的程序：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll h[25]; 
int main()
{
    h[1]=0;h[2]=1;
    cout<<"1,";
    for(int i=3;i<=23;i++)
    {
        for(int j=2;j<=i-1;j++)
            h[i]+=h[j]*h[i-j+1];
        cout<<h[i]<<",";
    }
}

首紫，纪念一下。