[CTSC2001] 排序二叉树

GitHub 跳转原题关系图返回列表

先把四个面的单位三角形按立体共边关系建成度数不超过 3 的图，再做带父边与值域边界的记忆化搜索，分别取当前节点左右子树的最优解。

OJ: luogu

题目 ID: P1267

难度:提高+/省选-

标签:树形dp图论递归构造

日期: 2026-06-21 00:07

题意

把正三棱锥四个面上的所有单位三角形看成点。

如果两个单位三角形在真实立体结构中共边，就认为它们相邻。

现在每个点上放了一个互不相同的数，要求从中选出尽量多的点，组成一棵二叉搜索树，并满足：

父子节点必须相邻
左子树所有值小于根
右子树所有值大于根

输出最大节点数。

思路

先看一个可以直接验证想法的朴素解：

cpp

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132#include <bits/stdc++.h>
using namespace std;

const int MAX_FACE = 5;
const int MAXN = 8;
const int MAXPOS = 20;
const int MAXV = 150;

int n;
int tot;
int mp[MAX_FACE][MAXN][MAXPOS];
int deg_cnt[MAXV];
int g[MAXV][4];
bool has_edge[MAXV][MAXV];

unordered_map<unsigned long long, int> memo;

void add_edge(int u, int v) {
    if (has_edge[u][v]) {
        return;
    }
    has_edge[u][v] = true;
    has_edge[v][u] = true;
    g[u][deg_cnt[u]++] = v;
    g[v][deg_cnt[v]++] = u;
}

void build_graph() {
    for (int face = 1; face <= 4; face++) {
        for (int row = 1; row <= n; row++) {
            for (int col = 1; col <= row * 2 - 1; col++) {
                cin >> mp[face][row][col];
            }
        }
    }

    for (int face = 1; face <= 4; face++) {
        for (int row = 2; row < n; row++) {
            for (int col = 2; col < row * 2 - 1; col++) {
                int u = mp[face][row][col];
                add_edge(u, mp[face][row][col - 1]);
                add_edge(u, mp[face][row][col + 1]);
                if (col & 1) {
                    add_edge(u, mp[face][row + 1][col + 1]);
                } else {
                    add_edge(u, mp[face][row - 1][col - 1]);
                }
            }
        }
    }

    if (n >= 2) {
        for (int face = 1; face <= 4; face++) {
            for (int col = 2; col <= n * 2 - 1; col += 2) {
                int u = mp[face][n][col];
                add_edge(u, mp[face][n][col - 1]);
                add_edge(u, mp[face][n][col + 1]);
                add_edge(u, mp[face][n - 1][col - 1]);
            }
        }
    }

    for (int col = 1; col <= n * 2 - 1; col++) {
        add_edge(mp[1][n][col], mp[4][n - col / 2][1]);
        add_edge(mp[2][n][col], mp[4][col / 2 + 1][(col / 2 + 1) * 2 - 1]);
        add_edge(mp[3][n][col], mp[4][n][n * 2 - col]);
    }

    for (int row = 1; row <= n; row++) {
        add_edge(mp[1][row][1], mp[3][row][row * 2 - 1]);
        add_edge(mp[2][row][1], mp[1][row][row * 2 - 1]);
        add_edge(mp[3][row][1], mp[2][row][row * 2 - 1]);
    }
}

unsigned long long encode_state(int u, int parent, int low, int high) {
    unsigned long long key = 0;
    key = (unsigned long long) u;
    key = key * 256ULL + (unsigned long long) parent;
    key = key * 256ULL + (unsigned long long) low;
    key = key * 256ULL + (unsigned long long) high;
    return key;
}

// brute.cpp：直接按 BST 定义搜索。
// 状态显式带上下界，写法更直观，但只适合小数据。
int dfs(int u, int parent, int low, int high) {
    unsigned long long key = encode_state(u, parent, low, high);
    unordered_map<unsigned long long, int>::iterator it = memo.find(key);
    if (it != memo.end()) {
        return it->second;
    }

    int best_left = 0;
    int best_right = 0;
    for (int i = 0; i < deg_cnt[u]; i++) {
        int v = g[u][i];
        if (v == parent) {
            continue;
        }
        if (v < low || v > high) {
            continue;
        }
        if (v < u) {
            best_left = max(best_left, dfs(v, u, low, u - 1));
        } else if (v > u) {
            best_right = max(best_right, dfs(v, u, u + 1, high));
        }
    }

    int res = best_left + best_right + 1;
    memo[key] = res;
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    tot = 4 * n * n;

    build_graph();

    int ans = 0;
    for (int root = 1; root <= tot; root++) {
        ans = max(ans, dfs(root, 0, 1, tot));
    }

    cout << ans << '\n';
    return 0;
}

这题最麻烦的其实是第一步：把四个面折叠后的真实邻接关系建成图。

图建好以后，问题就清楚很多了：

每个单位三角形只有 3 个相邻点
如果当前点已经确定了父亲，那么最多只剩 2 个方向可以继续选儿子

这非常适合做 BST 型记忆化搜索。

设当前节点是 $u$ ，父节点是 $parent$ ，再给一个边界 $bound$ 。

$parent$ 和 $bound$ 一起就能确定当前整棵子树允许出现的值域：

如果 $u < parent$ ，说明当前子树在父亲的左边，值域是某个左区间
如果 $u > parent$ ，说明当前子树在父亲的右边，值域是某个右区间

这样转移时只需要看 $u$ 的相邻点：

小于 $u$ 且落在合法区间里的，才可能当左儿子
大于 $u$ 且落在合法区间里的，才可能当右儿子

因为固定父边后最多只剩两个方向，所以左右子树可以独立取最优，然后加上当前节点。

于是做法就是：

先把所有真实共边关系建图
写 $dp(u, bound, parent)$ 表示一个带父边和区间边界的最优子树
枚举每个点作为整棵 BST 的根，取最大值

代码

cpp

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162#include <bits/stdc++.h>
using namespace std;

const int MAX_FACE = 5;
const int MAXN = 20;
const int MAXPOS = 40;
const int MAXV = 1305;

int n;
int tot;
int mp[MAX_FACE][MAXN][MAXPOS];
int deg_cnt[MAXV];
int g[MAXV][4];
bool has_edge[MAXV][MAXV];

// memo[u][pi][bound]：
// 当前根为 u，父亲是 g[u][pi]，另一个边界值是 bound 时，
// 能形成的最大 BST 节点数。
int memo[MAXV][4][MAXV];

void add_edge(int u, int v) {
    if (has_edge[u][v]) {
        return;
    }
    has_edge[u][v] = true;
    has_edge[v][u] = true;
    g[u][deg_cnt[u]++] = v;
    g[v][deg_cnt[v]++] = u;
}

int find_parent_index(int u, int parent) {
    for (int i = 0; i < deg_cnt[u]; i++) {
        if (g[u][i] == parent) {
            return i;
        }
    }
    return -1;
}

int dp(int u, int bound, int parent) {
    int pi = find_parent_index(u, parent);
    if (memo[u][pi][bound] != 0) {
        return memo[u][pi][bound];
    }

    int left_limit, right_limit;
    if (bound < parent) {
        left_limit = bound;
        right_limit = parent - 1;
    } else {
        left_limit = parent + 1;
        right_limit = bound;
    }

    int best_left = 0;
    int best_right = 0;

    // 父亲已确定后，剩下的最多两个相邻点里，
    // 只需分别挑一个最优左儿子和一个最优右儿子。
    for (int i = 0; i < deg_cnt[u]; i++) {
        int v = g[u][i];
        if (v == parent) {
            continue;
        }
        if (v < left_limit || v > right_limit) {
            continue;
        }
        if (v < u) {
            best_left = max(best_left, dp(v, left_limit, u));
        } else {
            best_right = max(best_right, dp(v, right_limit, u));
        }
    }

    memo[u][pi][bound] = best_left + best_right + 1;
    return memo[u][pi][bound];
}

void build_graph() {
    // 每个面按行存：第 i 行有 2*i-1 个单位三角形。
    for (int face = 1; face <= 4; face++) {
        for (int row = 1; row <= n; row++) {
            for (int col = 1; col <= row * 2 - 1; col++) {
                cin >> mp[face][row][col];
            }
        }
    }

    // 面内相邻。
    for (int face = 1; face <= 4; face++) {
        for (int row = 2; row < n; row++) {
            for (int col = 2; col < row * 2 - 1; col++) {
                int u = mp[face][row][col];
                add_edge(u, mp[face][row][col - 1]);
                add_edge(u, mp[face][row][col + 1]);
                if (col & 1) {
                    add_edge(u, mp[face][row + 1][col + 1]);
                } else {
                    add_edge(u, mp[face][row - 1][col - 1]);
                }
            }
        }
    }

    // 最后一行的内部相邻。
    if (n >= 2) {
        for (int face = 1; face <= 4; face++) {
            for (int col = 2; col <= n * 2 - 1; col += 2) {
                int u = mp[face][n][col];
                add_edge(u, mp[face][n][col - 1]);
                add_edge(u, mp[face][n][col + 1]);
                add_edge(u, mp[face][n - 1][col - 1]);
            }
        }
    }

    // 三个侧面和底面的公共边。
    for (int col = 1; col <= n * 2 - 1; col++) {
        add_edge(mp[1][n][col], mp[4][n - col / 2][1]);
        add_edge(mp[2][n][col], mp[4][col / 2 + 1][(col / 2 + 1) * 2 - 1]);
        add_edge(mp[3][n][col], mp[4][n][n * 2 - col]);
    }

    // 三个侧面的公共棱。
    for (int row = 1; row <= n; row++) {
        add_edge(mp[1][row][1], mp[3][row][row * 2 - 1]);
        add_edge(mp[2][row][1], mp[1][row][row * 2 - 1]);
        add_edge(mp[3][row][1], mp[2][row][row * 2 - 1]);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    tot = 4 * n * n;

    build_graph();

    int ans = 0;

    // 枚举根节点。根最多选一个左儿子、一个右儿子。
    for (int root = 1; root <= tot; root++) {
        int best_left = 0;
        int best_right = 0;

        for (int i = 0; i < deg_cnt[root]; i++) {
            int v = g[root][i];
            if (v < root) {
                best_left = max(best_left, dp(v, 1, root));
            } else {
                best_right = max(best_right, dp(v, tot, root));
            }
        }

        ans = max(ans, best_left + best_right + 1);
    }

    cout << ans << '\n';
    return 0;
}

复杂度

总点数 $tot = 4n^2$ 。

状态数约为 $O(tot^2)$ ，每个状态只看常数个邻居。

所以时间复杂度：

$O(tot^2)$

空间复杂度：

$O(tot^2)$

总结

这题表面上是立体几何，真正的算法核心其实是：

先把几何问题翻译成小度数图
再利用 BST 的值域约束做区间型记忆化搜索

图一旦建对，后面的 DP 结构是很规整的。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

P1267 [CTSC2001] 排序二叉树

题目描述

一个边长为 $n$ 的正三角形可以被划分成 $n^2$ 个小的边长为 $1$ 的正三角形，称为单位三角形。边长为 $3$ 的正三角形被分成三层共 $9$ 个小的正三角形，我们把它们从顶到底，从左到右以 $1\sim 9$ 编号，见下图。

四个这样的边长为 $n$ 的正三角形可以组成一个三棱锥。我们将正三棱锥的三个侧面依顺时针次序（从顶向底视角）编号为 $A,B,C$ ，底面编号为 $D$ 。侧面的 $A,B,C$ 号三角形以三棱锥的顶点为顶，底面的 $D$ 号三角形以它与 $A,B$ 三角形的交点为顶。

其中 $\tt .$ 表示这个三角形面的 $1$ 号三角形位置，并依次编号下去。

上图为三棱锥展开后的平面图，每个面上标有圆点的是该面的顶，该图中侧面 $A,B,C$ 分别向纸内方向折叠即可还原成三棱锥。我们把这 $A,B,C,D$ 四个面各自划分成 $n^2$ 个单位三角形。

对于任意两个单位三角形，如有一条边相邻，则称它们为相邻的单位三角形。显然，每个单位三角形有三个相邻的单位三角形。现在，把 $1\sim 4n^2$ 里的所有整数分别随机填入四个面总共 $4n^2$ 个单位三角形中。

现在要求你编程求由单位三角形组成的最大二叉搜索树。所谓最大二叉搜索树，是指在所有由单位三角形组成的二叉搜索树中节点最多的一棵树。要求当 $i$ 作为二叉搜索树的一个节点时， $i$ 的儿子（如果有的话）和 $i$ 的父亲（如果有的话）必须与 $i$ 有邻边（三棱锥状态下的邻边，而非展开图的邻边）。

一棵二叉搜索树满足这个节点的左子树得每个值全部小于这个节点，这个节点的右子树的每个值全部大于这个节点。

输入格式

输入的第一行为一个整数 $n$ ，表示展开图中每个面的三角形边长，也就是这个面有 $n^2$ 个单位三角形。

接下来每行 $n^2$ 个整数，一共四行，第一行表示 $A$ 面的单位三角形中填入的数，第二行表示 $B$ 面，以此类推。

输出格式

输出仅一行一个整数，表示最大二叉搜索树的节点个数。

输入输出样例 #1

输入 #1

text

1
2
3
4
53 
19 33 32 31 29 3 5 4 30 
22 25 20 21 12 24 23 34 35 
14 13 15 26 18 17 8 16 27 
11 10 9 1 28 7 2 6 36

输出 #1

text

说明/提示

样例解释

以下以 $A$ 面为例。记 $f(A,x)$ 表示 $A$ 面的第 $x$ 个单位三角形，以此类推。

$f(A,9)$ 与 $f(D,1)$ 有邻边， $f(A,7)$ 与 $f(D,2)$ 有邻边， $f(A,5)$ 与 $f(D,5)$ 有邻边。

$f(A,1)$ 与 $f(B,1)$ 有邻边， $f(A,4)$ 与 $f(B,2)$ 有邻边， $f(A,9)$ 与 $f(B,5)$ 有邻边。

$f(A,1)$ 与 $f(C,1)$ 有邻边， $f(A,2)$ 与 $f(C,4)$ 有邻边， $f(A,5)$ 与 $f(C,9)$ 有邻边。

以数字 $1$ 为二叉搜索树的根，可以得到节点最多的二叉搜索树为：

数据范围

对于 $100\%$ 的数据， $1\leqslant n\leqslant 18$ ，保证四个面所有单位三角形上填入的数互不相同且都取自 $[1,4n^2]$ 。

[CTSC2001] 排序二叉树

目录

题意

思路

代码

复杂度

总结

一图流解析