本文共 1449 字，大约阅读时间需要 4 分钟。

$$\mathrm{FBI树}$$

题目链接：

题目

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

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

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

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

输入

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

第二行是一个长度为 $2^N$ 的“ $01$ ”串。

输出

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

样例输入

310001011

样例输出

IBFBBBFIBFIIIFF

数据范围

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

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

思路

这道题就是直接模拟。

就直接模拟啊，一个字符串先看是全 $0$ ，全 $1$ ，还是都有。接着如果这个字符串不知一个字符就要分开两半再处理。

代码

#include
   
    using namespace std;int n;char a[1051];void work(int l, int r) {   	int check = a[l] - '0';//看字符串是怎样的	for (int i = l + 1; i <= r; i++)		if ((a[i] - '0') != check) {   			check = -1;			break;		}		if (l < r) {   //不是一个字符，还要分		int mid = (l + r) >> 1;		work(l, mid);		work(mid + 1, r);	}		if (check == -1) printf("F");//输出		else if (check == 0) printf("B");			else printf("I");}int main() {   	scanf("%d", &n);//读入	for (int i = 1; i <= (1 << n); i++) {   		a[i] = getchar();		while (a[i] != '0' && a[i] != '1') a[i] = getchar();	}		work(1, 1 << n);		return 0;}