自动搬运

查看原文

来自洛谷，原作者为

	SUPERLWR Never gonna give you up. Never gonna say goodbye.

搬运于2025-08-24 21:35:50，当前版本为作者最后更新于2022-08-27 17:00:29，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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]<<",";
	}
}

首紫，纪念一下。