洛谷-P1087 FBI树（满二叉树下标关系）

题目描述

我们可以把由“00”和“11”组成的字符串分为三类：全“00”串称为B*B*串，全“11”串称为I串，既含“00”又含“11”的串则称为F串。

FBI*F**B**I*树是一种二叉树，它的结点类型也包括F*F*结点，B*B*结点和I结点三种。由一个长度为2^N2*N*的“0101”串S可以构造出一棵FBI*F**B**I*树T*T*，递归的构造方法如下：

1. T*T*的根结点为R*R*，其类型与串S*S*的类型相同；
2. 若串S*S*的长度大于11，将串S*S*从中间分开，分为等长的左右子串S_1*S*1和S_2*S*2；由左子串S_1*S*1构造R的左子树T_1*T*1，由右子串S_2*S*2构造R*R*的右子树T_2*T*2。

现在给定一个长度为2^N2*N*的“0101”串，请用上述构造方法构造出一棵FBI*F**B**I*树，并输出它的后序遍历序列。

输入格式

第一行是一个整数N(0 \le N \le 10)N(0≤N≤10)，

第二行是一个长度为2^N2*N*的“0101”串。

输出格式

一个字符串，即FBI*F**B**I*树的后序遍历序列。

输入输出样例

输入 #1

3
10001011

输出 #1

IBFBBBFIBFIIIFF

说明/提示

对于40%的数据，N \le 2*N*≤2；

对于全部的数据，N \le 10*N*≤10。

noip2004普及组第3题

---

#include <bits/stdc++.h>

using namespace std;

int n = 1 << 11;
int N;
vector<char> seq(n);

void build()
{
    for (int i = (1 << N) - 1; i >= 1; --i) {
        int left = 2 * i, right = 2 * i + 1;
        if (seq[left] == seq[right]) {
            switch(seq[left]) {
                case 'F': seq[i] = 'F'; break;
                case 'I': seq[i] = 'I'; break;
                default: seq[i] = 'B';
            }
        }
        else {
            seq[i] = 'F';
        }
    }
}

void postTraversal(int pos)
{
    if (pos > n) return;
    postTraversal(pos * 2);
    postTraversal(pos * 2 + 1);
    cout << seq[pos];
}


int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> N;
    n = (1 << (N + 1)) - 1; //总的节点个数
    for (int i = (1 << N); i <= n; ++i) {
        char ch; cin >> ch;
        seq[i] = (ch == '0') ? 'B' : 'I';
    }

    build();
    postTraversal(1);

    return 0;
}

发现输入的序列恰好可以构成一个满二叉树，那么就可以利用下标关系用数组进行模拟。