题目地址：BZOJ：Problem 2944. — [Poi2000]代码

题目描述

一棵二叉树要么为空，要么由一个结点和两棵与其相连的树组成。这两棵树分别称为左子树和右子树。每个结点处有一个英文字母。不包括在任何子树内的结点称为根结点。我们定义二叉搜索树(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。
代码(7,4)：badc，对应的BST如下图所示。
任务：
编写一个程序，完成下列工作：
●读入n，k；
●找出代码(n,k)；
●把它写入

题意简述

对于一棵k个结点的BST，每个节点上都有一个小写字母，且节点小写字母按照字母表顺序满足BST的有序性质。求所有可能的BST形态中，先序遍历序列字典序第n大的那个。

输入输出格式

输入格式：
仅一行，包括以空格分开的两个整数n和k(1≤K≤19)。n不超过BST代码的总数。

输出格式：
仅一行，是以小写字母给出的代码(n,k)。

输入输出样例

输入样例#1：

11

输出样例#1：

dacb

题解

BST的形态数可以预处理卡特兰数来计算，这是由于卡特兰数首尾配对相乘相当于在枚举右子树的节点数，将左右子树的方案数乘起来。我们自然可以用类似的想法写一个分治，每次分治到一个节点，枚举其右子树节点数，由于想让根节点对应的字母尽量靠前，也就是让右子树节点尽量多，所以应该从大向小枚举，并从k中减去被完全包含的方案，在不完全被包含的方案处停止。此时，根对应的字母可以确定，输出它，并且计算出左右子树的节点数和询问的k值即可，此处需要让左子树字典序尽量小。
复杂度O(n^2)。

代码

// Code by KSkun, 2018/6
#include <cstdio>
#include <cctype>
#include <cstring>

#include <algorithm>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
        ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1; register char c = fgc();
    for(; !isdigit(c); c = fgc()) if(c == '-') neg = -1;
    for(; isdigit(c); c = fgc()) res = (res << 1) + (res << 3) + c - '0';
    return res * neg;
}

const int MAXN = 20;

int n, k, cat[MAXN];

inline void solve(int n, int k, int t) {
    if(!n) return;
    int rsiz;
    for(rsiz = n - 1; rsiz >= 0; rsiz--) {
        if(cat[rsiz] * cat[n - rsiz - 1] < k) {
            k -= cat[rsiz] * cat[n - rsiz - 1];
        } else {
            break;
        }
    }
    putchar('a' + t + n - rsiz - 1);
    solve(n - rsiz - 1, (k - 1) / cat[rsiz] + 1, t);
    solve(rsiz, k % cat[rsiz] ? k % cat[rsiz] : cat[rsiz], t + n - rsiz);
}

int main() {
    k = readint(); n = readint();
    cat[0] = cat[1] = 1;
    for(int i = 2; i <= 19; i++) {
        for(int j = 0; j < i; j++) {
            cat[i] += cat[j] * cat[i - j - 1];
        }
    }
    solve(n, k, 0);
    return 0;
}