这题在网上找不到题解，硬写一下午终于写出来了……

题目：

BZOJ2944

分析：

首先明确：

比较两棵节点数相同的二叉树时，根节点是第一关键字，左子树是第二关键字，右子树是第三关键字；

然后我们分析一下题目中那个4个节点，14种代码的例子

（由于博客园的Markdown似乎不支持表格，此图截自我的CSDN博客）

（先不管最后一列）我们发现左子树大小决定了根节点的字母，并将这14种二叉树形态分成了长度为5、2、2、5的四“段”。因此，我们知道要求第多少名，就可以根据它在哪一段求出左子树的大小（比如样例中的第11名在第4段，因此左子树大小为3，代码一定以‘d‘开头）。并且这个过程可以递归下去，求出树的形态。代码如下

    void dfs(ll n, int k, int tmp)
    {
        int sizel = 0, sizer = k - 1;
        /*算出左子树的大小*/
        printf("%c", (char)(sizel + tmp + ‘a‘));
        if (sizel > 0)
            dfs(/*左子树的名次*/, sizel, tmp);
        if (sizer > 0)
            dfs(/*右子树的名次*/, sizer, tmp + sizel + 1);
    }

有一个结论，如果用\(C_n\)表示\(Catalan\)数的第n项，则\(n\)个结点的二叉树有\(C_n\)种不同的形态
（证明见Catalan number - Wikipedia，相关公式推导见【知识总结】卡特兰数 (Catalan Number) 公式的推导）
那么当根节点的字母固定，左右子树大小随之固定，以该字母开头的代码的数量就是\(C_{sl}*C_{sr}\)，也就是上表最后一列。
根据这个性质，可以暴力算出根节点的字母和左右子树的大小，代码如下

        while (n)
        {
            if (n > Catalan[sizel] * Catalan[sizer])
            {
                n -= Catalan[sizel] * Catalan[sizer];
                sizel++, sizer--;
            }
            else
                break;
        }

这段代码执行后，\(n\)就是当根节点固定时该代码的排序（比如样例中dacb是以‘d‘开头的第二个，此时\(n=2\)）
此时的排序是以左子树为第一关键字，右子树为第二关键字的。可以想象成一个两位数，个位满\(C_{sr}\)向十位进一。所以此时所求左子树在\(C_{sl}\)个左子树中的排名是\(\lceil \frac{n}{C_{sr}}\rceil\)，所求右子树在\(C_{sr}\)个右子树中的排名是\(n\ mod\ C_{sr}\)（注意特判\(0\)的情况）
代码：
=
注意不是每一棵子树所代表的字母集合都是从‘a‘开始的，所以要有\(tmp\)变量

#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
namespace zyt
{
    typedef long long ll;
    ll Catalan[20];
    void dfs(ll n, int k, int tmp)
    {
        int sizel = 0, sizer = k - 1;
        while (n)
        {
            if (n > Catalan[sizel] * Catalan[sizer])
            {
                n -= Catalan[sizel] * Catalan[sizer];
                sizel++, sizer--;
            }
            else
                break;
        }
        printf("%c", (char)(sizel + tmp + ‘a‘));
        if (sizel > 0)
            dfs(ceil((double)n / Catalan[sizer]), sizel, tmp);
        if (sizer > 0)
        {
            int x = n % Catalan[sizer];
            dfs(x ? x : Catalan[sizer], sizer, tmp + sizel + 1);
        }
    }
    void work()
    {
        ll n;
        int k;
        scanf("%lld%d", &n, &k);
        Catalan[0] = 1;
        for (int i = 1; i <= k; i++)
            Catalan[i] = Catalan[i - 1] * (4 * i - 2) / (i + 1);
        dfs(n, k, 0);
    }
}
int main()
{
    zyt::work();
    return 0;
}

【BZOJ2944】[Poi2000]代码(卡特兰数)

原文：https://www.cnblogs.com/zyt1253679098/p/9615091.html