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

题目：

BZOJ2944

分析：

首先明确：

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

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

左子树大小$sl$右子树大小$sr$根节点对应名次对应代码数量$C_{sl}\ast C_{sr}$03a1~55 (abcd 、abdc、 acbd、 adbc、 adcb)$1\ast 5=5$12b6~72 (bacd、 badc)$1\ast 2=2$21c8~92 (cabd、 cbad)$2\ast 1=2$30d10~145 (dabc、 dacb、 dbac、 dcab、 dcba)$5\ast 1=5$

（先不管最后一列）我们发现左子树大小决定了根节点的字母，并将这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}\ast 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}$个右子树中的排名是$nmod{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; }