递归

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 131072K，其他语言262144K
64bit IO Format: %lld

题目描述

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

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

1) T的根结点为R，其类型与串S的类型相同；

2) 若串S的长度大于1，将串S从中间分开，分为等长的左右子串S₁和S₂；由左子串S₁构造R的左子树T₁，由右子串S₂构造R的右子树T₂。

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

[1] 二叉树：二叉树是结点的有限集合，这个集合或为空集，或由一个根结点和两棵不相交的二叉树组成。这两棵不相交的二叉树分别称为这个根结点的左子树和右子树。

[2] 后序遍历：后序遍历是深度优先遍历二叉树的一种方法，它的递归定义是：先后序遍历左子树，再后序遍历右子树，最后访问根。

输入描述:

第一行是一个整数N（0 <= N <= 10）
第二行是一个长度为2^N的“01”串。

输出描述:

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

示例1

输入

复制

3
10001011

输出

复制

IBFBBBFIBFIIIFF

备注:

对于40%的数据，N <= 2；
对于全部的数据，N<= 10。

直接后序遍历加上递归即可，开一个全局的string，n没有啥用，按照题目翻译即可。

#pragma GCC target("avx,sse2,sse3,sse4,popcnt")
#pragma GCC optimize("O2,O3,Ofast,inline,unroll-all-loops,-ffast-math")
#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
const ll MOD = 1e9 + 7;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void write(ll x) { if (!x) { putchar('0'); return; } char F[40]; ll tmp = x > 0 ? x : -x; if (x < 0)putchar('-');    int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';        tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;    while (b) { if (b & 1)    ans *= a;        b >>= 1;        a *= a; }    return ans; }    ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
inline int lowbit(int x) { return x & (-x); }

int n;
string s;

void dfs(int l, int r) {
    if (l == r) {
        if (s[l] == '1')    cout << 'I';
        else if (s[l] == '0')    cout << 'B';
        return;
    }
    int flag1 = 0, flag2 = 0;
    int mid = l + r >> 1;
    dfs(l, mid), dfs(mid + 1, r);
    for (int i = l; i <= r; ++i) {
        if (s[i] == '0')    flag1 = 1;
        else if (s[i] == '1')    flag2 = 1;
    }
    if (flag1 and flag2)    cout << 'F';
    else if (flag1)    cout << 'B';
    else if (flag2)    cout << 'I';
}

int main() {
    js;
    cin >> n >> s;
    dfs(0, s.size() - 1);
    return 0;
}