[NOIP2004-普及] FBI 树

题目描述

由 0/1 组成的串分三类：全 0 为 B，全 1 为 I，两者都有为 F。给定长度 $2^N$ 的 01 串，递归构造 FBI 树：根类型等于整串类型；长度大于 1 时从中间对半分为左右子串，分别递归构造左右子树。输出后序遍历序列。

输入：第一行 $N(0\le N\le 10)$ ，第二行长度为 $2^N$ 的 01 串。输出：后序字符串。

样例输入：

text

1
23
10001011

样例输出：IBFBBBFIBFIIIFF。

思路

递归处理子串 [l,r]：先递归左半 [l,mid]，再递归右半 [mid+1,r]，返回前把当前子串类型追加进答案。调用顺序即后序遍历，不必显式建树。类型判断只看该子串里是否同时出现 0 和 1。

参考代码

Python 版：

python

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#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-02 05:40
# update_at: 2026-10-02 05:40

import sys


def build(seg: str, out: list[str]) -> None:
    """递归构造 seg 这一段的 FBI 子树，把它的后序遍历字符追加到 out。"""
    # 串段类型只看 0/1 是否同时出现：缺 1 全 0 为 B，缺 0 全 1 为 I，否则 F
    node = 'B' if '1' not in seg else 'I' if '0' not in seg else 'F'
    if len(seg) > 1:  # 题目保证串长是 2 的幂，对半分后两段等长
        mid = len(seg) // 2
        build(seg[:mid], out)
        build(seg[mid:], out)
    out.append(node)  # 后序：先左右子树，最后才记根


def solve() -> None:
    data = iter(sys.stdin.buffer.read().split())
    n = int(next(data))       # 串长为 2**n；构造只依赖串本身，n 仅用于校对格式
    s = next(data).decode()   # 01 串按原样读入，不做数值转换
    out: list[str] = []
    build(s, out)
    print(''.join(out))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 13:11
 * update_at: 2026-10-06 13:11
 */

#include <cstdio>
#include <iostream>
using namespace std;

typedef long long ll;

const int MAXN = 1 << 10 | 5; // N <= 10，串长最多 2^10

char s[MAXN]; // 输入 01 串
char ans[MAXN * 2]; // 后序序列，长度 2^(N+1) - 1
ll ans_len; // 当前已写入 ans 的字符数

// 判断 [l, r] 区间内子串类型：全 0 为 B，全 1 为 I，都有为 F
char node_type(ll l, ll r) {
    bool has0 = false, has1 = false;
    for (ll i = l; i <= r; i++) {
        if (s[i] == '0') has0 = true;
        else has1 = true;
    }
    if (!has1) return 'B';
    if (!has0) return 'I';
    return 'F';
}

// 递归处理子串 [l, r]，先左右子树，返回前把本结点字符写入 ans
void build(ll l, ll r) {
    if (l == r) {
        ans[ans_len++] = s[l] == '0' ? 'B' : 'I';
        return;
    }
    ll mid = (l + r) >> 1;
    build(l, mid);      // 左子树
    build(mid + 1, r);  // 右子树
    ans[ans_len++] = node_type(l, r); // 根
}

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

    ll n;
    cin >> n >> (s + 1);
    ll m = 1LL << n; // 串长 2^N
    ans_len = 0;
    build(1, m);
    ans[ans_len] = '\0';
    cout << ans << "\n";
    return 0;
}

[NOIP2004-普及] FBI 树

目录

题目描述

思路

参考代码