题解 洛谷 P1185
Mitama
2020-07-28 18:01:54
~~被普及练习场 / 基础题单虐菜中 /kk~~
[**题目传送门**](https://www.luogu.com.cn/problem/P1185) [**博客查看**](https://www.luogu.com.cn/blog/236807/Solution-luogu-P1185)
本文中，带有上角标的地方可以在文末找到注释。本文主要面向初学者，建议面向提高的选手跳读。斜体字旨在消除一些可能的歧义。
考虑逐行输出。那么，不可避免地，我们需要知道根节点的位置。
我们定义 $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}.
$$
我们可以记录输出数据每行边 / 点的位置（此处不考虑删除），然后每次输出后，如果是左子树，位置自减；右子树位置自增。节点需要判断并更新数组（分别记录自减和自增，故此时数据数量会变为二倍）。
对于是否删除，我们可以判断父节点删除或节点本身删除。当从上向下扫描时，祖先是否有删除必然体现在父结点上，故不必考虑祖先。这里可以边做边递推或预处理，代码中采用的是预处理。
```cpp
# 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;
}
```
注释：
0. 本文中可能涉及的影响阅读符号：对于所有 $\forall$，向下取整 $\lfloor\rfloor$。
1. 子树的宽度指所占的横向距离。形式化地，定义 $\max$ 为子树内最右侧节点（显然为叶节点）的位置、$\min$ 为子树内最左侧节点（显然为叶节点）的位置，当不考虑删除节点时，子树的宽度即为 $\max - \min + 1$。恰好表示宽度是因为根节点左侧必然有*左子树宽度*个节点。
2. $\forall i \geqslant 2$，希望更优美解法的同学可以从该式中（可利用位运算推导、求值）推出如下式子：$r_i = 2^i - 2^{i - 2} - 1(i \geqslant 2)$。类似，$e_i = 2^i - \lfloor 2^{i - 2} \rfloor - 1$。