Catalan.

Table of Contents

  1. Description
  2. Solution

Description

一棵二叉树要么为空，要么由一个结点和两棵与其相连的树组成。这两棵树分别称为左子树和右子树。每个结点处有一个英文字母。不包括在任何子树内的结点称为根结点。我们定义二叉搜索树(BST)为：若按字母表中的先后顺序排列，则二叉树的任一个结点均满足，其左子树上的所有字母均在该结点字母之前，而其右子树上所有字母均在该结点字母之后。

于是，一棵BST的代码为：

如果是一棵空树，则代码中不包括任何字母，即为空串；

如果不是空树，则代码为：根结点上的字母，紧跟着左子树的代码和右子树的代码。

一棵含$k$个结点的BST，其代码会有$k$个小写英文字母，按照字母顺序排列它所有可能的代码，并用$(n,k)$表示其中的第$n$条代码。

例如，一棵有4个结点的BST共有14个不同的代码，按字母顺序列出：abcd 、abdc、 acbd、 adbc、 adcb、 bacd、 badc、 cabd、 cbad、 dabc、 dacb、 dbac、 dcab、 dcba。

Solution

$n$个节点的二叉树个数有卡塔兰数个, 那么当根确定时, 我们就可以递归地做左右子树. 当树的规模确定时, 我们可以枚举左右子树的规模来计算排名.

递归边界是某棵树为空.

当我们计算出排名对应当前左子树规模的第$i$名时, 我们有:

考虑排名是一个$Catalan_{r}$进制的数字, 那么右子树每完成一轮排名, 左子树就+1, 且初始为1, 所以对应左右子树的排名分别是: $\lceil \frac{i}{C_r} \rceil, i \% C_r$, 注意如果余数为$0$, 实际上是$C_r$.

记得向右子问题传一个字符的偏移量$\Delta+l+1$.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>

using namespace std;

typedef long long ll;

int k;
ll n, c[20];

void dfs(ll N, int K, int delta) {
  int ls = 0, rs = K - 1;
  while (N) {
    if (N > c[ls] * c[rs]) {
      N -= c[ls] * c[rs];
      ls++; rs--;
    }
    else break;
  }
  printf("%c", char(ls + delta + 'a'));
  if (ls) dfs((N - 1) / c[rs] + 1, ls, delta);
  if (rs) {
    ll newrank = N % c[rs];
    if (!newrank) newrank = c[rs];
    dfs(newrank, rs, delta + ls + 1);
  }
}

int main() {
  c[0] = 1;
  for (int i = 1; i <= 19; ++i) c[i] = c[i - 1] * (4 * i - 2) / (i + 1);//, printf("%lld\n", c[i]);
  scanf("%lld%d", &n, &k);
  dfs(n, k, 0);
  return 0;
}