题解洛谷 P1185

KaguyaH · 2020-07-28 18:01:54 · 题解

~~被普及练习场 / 基础题单虐菜中 /kk~~

题目传送门 博客查看

本文中，带有上角标的地方可以在文末找到注释。本文主要面向初学者，建议面向提高的选手跳读。斜体字旨在消除一些可能的歧义。

考虑逐行输出。那么，不可避免地，我们需要知道根节点的位置。

我们定义 r_i 为 (m = i) 时根节点的位置。这里从 0 计数比较方便（恰好表示了左右子树的宽度{}^1），故选择从 0 开始。显然，有{}^2

r_i = \begin{cases} 0 & i = 1\\ 2 & i = 2\\ 2r_{i - 1} + 1 & i > 2\\ \end{cases}.

综上，我们得到了根节点的位置。

另一个很麻烦的点是，如何得到每个点到其母亲节点的距离。我们发现，该距离应该恰好跳过该点与母结点间的子树的宽度，与 r_i 的定义非常相似。故我们发现，当一条边下方有 i 个节点时，该边长度

e_i = \begin{cases} 1 & i = 1\\ r_i & i > 1\\ \end{cases}.

我们可以记录输出数据每行边 / 点的位置（此处不考虑删除），然后每次输出后，如果是左子树，位置自减；右子树位置自增。节点需要判断并更新数组（分别记录自减和自增，故此时数据数量会变为二倍）。

对于是否删除，我们可以判断父节点删除或节点本身删除。当从上向下扫描时，祖先是否有删除必然体现在父结点上，故不必考虑祖先。这里可以边做边递推或预处理，代码中采用的是预处理。

# define _CRT_SECURE_NO_WARNINGS
# include <cstdio>
# include <algorithm>
# include <vector>

typedef short unsigned int hu;
enum { M = 10 };

static hu m, n;
static bool e[M][1 << M - 1]; // 节点是(true)否(false)存在
static hu p[2][1 << M - 1]; // 节点位置

signed int main() {
    scanf("%hu%hu", &m, &n), p[0][0] = (1 << m) - (1 << m - 2); // 根节点位置 使用的是注释中的公式
    for (hu i(0); i < m; ++i)
        for (hu j(0); j < 1 << i; ++j)
            e[i][j] = true;
    for (hu i(0); i < n; ++i) {
        {
            static hu i, j; scanf("%hu%hu", &i, &j);
            e[i - 1][j - 1] = false;
        }
    }
    for (hu i(1); i < m; ++i)
        for (hu j(0); j < 1 << i; ++j)
            if (not e[i - 1][j >> 1])
                e[i][j] = false; // 预处理
    for (hu i(1); i < p[0][0]; ++i) putchar(' ');
    puts("o"); // 特殊处理根节点
    for (hu i(1); i < m; ++i) {
        for (hu j(0); j < 1 << i; ++j) p[1][j] = p[0][j >> 1] + (j & 1 ? 1 : -1);
        std::swap(p[0], p[1]); // 得到本层的边的最上面一行的位置 存入p[0]
        const hu t((1 << m - i) - (1 << m - i - 2));
        for (hu l(1); l < t; ++l) {
            for (hu j(1), k(0); k < 1 << i; ++j)
                if (j == p[0][k]) putchar(e[i][k] ? k & 1 ? '\\' : '/' : ' '), p[0][k] += k & 1 ? 1 : -1, ++k;
                else putchar(' ');
            putchar('\n'); // 依次输出每一行边
        }
        for (hu j(1), k(0); k < 1 << i; ++j)
            putchar(j == p[0][k] && e[i][k++] ? 'o' : ' ');
        putchar('\n'); // 输出节点
    }
    return 0;
}

注释：

本文中可能涉及的影响阅读符号：对于所有 \forall，向下取整 \lfloor\rfloor。
子树的宽度指所占的横向距离。形式化地，定义 \max 为子树内最右侧节点（显然为叶节点）的位置、\min 为子树内最左侧节点（显然为叶节点）的位置，当不考虑删除节点时，子树的宽度即为 \max - \min + 1。恰好表示宽度是因为根节点左侧必然有左子树宽度个节点。

题解 洛谷 P1185

题解洛谷 P1185