题解：P1814 数的序号 最后更新于 2025-05-01 15:28:36

本题要求根据给定的序号生成对应的二叉树结构，关键在于理解二叉树的标号规则。 我们可以利用卡特兰数来解决这个问题。卡特兰数 $C_{n}$ 表示具有 $n$ 个结点的不同二叉树的数量，其递推公式为 $C_n=\sum_{i=1}^{n-1}C_i \times C_{n-1-i}$ 。通过预处理卡特兰数及其前缀和，我们可以快速确定给定序号对应的结点数，然后递归地构造出对应的二叉树。 `maxn`：定义了最大可能的输入序号，这里是 $5 \times 10^8$。 `C`数组：用于存储卡特兰数，初始时 $C_0=1$，表示空树或只有一个节点的树的情况。 `S`数组：用于存储卡特兰数的前缀和，初始时 $S_0=1$，表示序号为 $0$ 的空树。 接下来,有以下几个要点: 1. 预处理卡特兰数和前缀和 预处理循环：通过双重循环计算卡特兰数和前缀和。外层循环 `m` 从 $1$ 开始递增，表示当前处理的结点数。内层循环根据卡特兰数的递推公式计算 $C_m$ ,并将其添加到 `C` 数组中。然后计算前缀和 $S_m=S_{m-1}+C_m$ ,并将其添加到 `S` 数组中。当 $S_m$ 超过 $maxn$ 时，停止预处理。 2. 找到序号对应的节点数 `find_m`函数:该函数接受一个序号 $n$ 作为参数，通过遍历前缀和数组`S`找到满足 $S_{m-1}\le n<S_m$ 的 $m$ ,即序号`n`对应的结点数。如果没有找到，返回`s.size()-1`。 3. 递归构建二叉树的字符串表示 `build`函数:该函数接受两个参数，`node_count` 表示当前二叉树的结点数，`k` 表示在具有 `node_count` 个结点的所有二叉树中的相对序号。 基本情况：如果 `node_count` 为 $0$ ，返回空字符串，表示空树。 递归情况：通过循环枚举左子树的结点数 $l$，则右子树的结点数 `r` = `node_count - 1 - l`。计算左子树和右子树的卡特兰数 `cl` 和 `cr`，以及它们的组合数量 `total` = `cl * cr`。 如果 `k` < `total`，说明当前序号对应的二叉树的左子树结点数为 `l`。计算左子树和右子树的相对序号 `left_k` = `k` $\div$ `cr` 和 `right_k` = `k` $mod$ `cr`，然后递归调用 build 函数构建左子树和右子树的字符串表示，并根据规则组合成完整的二叉树字符串。 如果 `k` >=`total`，说明当前序号对应的二叉树的左子树结点数大于 `l`，将 `k` 减去 `total`，继续枚举下一个 `l`。 4. 主函数处理输入 首先预处理。 对于每一个`n`,调用 `find_m` 函数找到对应的结点数 `m`，计算在具有 `m` 个结点的所有二叉树中的相对序号 $k = n - s_{m - 1}$，然后调用 `build` 函数构造并输出对应的二叉树字符串。 接下来就是蛋码时间! # ${\color{Green}}\Huge AC$ 代码 ```cpp #include <iostream> #include <vector> #include <string> using namespace std; const int maxn = 5e8; vector<int> C = {1}; vector<int> s = {1}; int find_m(int n) { for (int i = 1; i < s.size(); ++i) { if (s[i - 1] <= n && n < s[i]) { return i; } } return s.size() - 1; } string build(int node_count, int k) { if (node_count == 0) return ""; for (int l = 0; l < node_count; ++l) { int r = node_count - 1 - l; int cl = C[l]; int cr = C[r]; int total = cl * cr; if (k < total) { int left_k = k / cr; int right_k = k % cr; string left_part = l > 0 ? "(" + build(l, left_k) + ")" : ""; string right_part = r > 0 ? "(" + build(r, right_k) + ")" : ""; return left_part + "X" + right_part; } else k -= total; } return ""; } int main() { int m = 1; while (true) { int cm = 0; for (int i = 0; i < m; ++i) cm += C[i] * C[m - 1 - i]; C.push_back(cm); int sm = s.back() + cm; s.push_back(sm); if (sm > maxn) break; ++m; } int n; while (cin >> n && n != 0) { int m = find_m(n); int k = n - s[m - 1]; cout << build(m, k) << endl; } return 0; } ```