题解 | #[NOIP2004]FBI树#

可以用线段树来写，注意打印时是后序遍历：先左递归，后右递归，最后输出中间即可。 代码如下：

#include <bits/stdc++.h>
using namespace std;

#define MAXN 1025
char arr[MAXN];
char FBI[MAXN << 2];
string s;
void up(int i){
    int l = i << 1, r = i << 1 | 1;
    if(FBI[l] == FBI[r]){
        FBI[i] = FBI[l];
    }else{
        FBI[i] = 'F';
    }
}
void build(int l, int r, int i){
    if(l == r){
        FBI[i] = s[l] == '1' ? 'I' : 'B';
    }else{
        int mid = (l + r) >> 1;
        build(l, mid, i << 1);
        build(mid + 1, r, i << 1 | 1);
        up(i);
    }
}
void print(int l, int r, int i){
    if(l == r){
        printf("%c",FBI[i]);
    }else{
        int mid = (l + r) >> 1;
        print(l, mid, i << 1);
        print(mid + 1, r, i << 1 | 1);
        printf("%c",FBI[i]);
    }
}
int main(){
	int n;
    scanf("%d", &n);
    n = (1 << n);
    cin >> s;
    s = " " + s;
    build(1, n, 1);
    print(1, n, 1);
	return 0;
}