The #A1365. FBI树(fbi) is bad.

Let ChaYe teach you.

I. 读题！

1. 全 $0$ 串称为 $B$ 串，全 $1$ 串称为 $I$ 串，既含 $0$ 又含 $1$ 的串则称为 $F$ 串

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

4. 请用上述构造方法构造出一棵 FBI 树，并输出它的后序遍历序列

---

啧，2. …… 和 3. …… 有点难理解，请求中译中！

2. …… $==$ $T$ 是个树，根节点是 $S$ ；

3. …… $==$ 如果树 $T$ 里有节点的长度大于 $1$ 就把那个节点的左孩子设为自己的左半，右孩子设为自已的右半

FBI树图示：

II. 开写！

1 别管其他，定义变量，写好框架，依次输入

int n;      // 输入的长度2^N中的N
string fbi; // 输入的串

输入选择 $string$ ，方便后续分半

因为我们需要重复进行分树等操作，题目中也提示了递归，所以我们使用神奇の递归作为操作方式

框架：

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

int FBI( ? )
{
	?
}

int main()
{
	cin >> n >> fbi;
	FBI( ? );
	
	return 0;
}

2 程序正在书写，AC似在眼前

为方便，先把 $n$ 改为实际长度再执行 $FBI$ 函数

n = 1 << n;

FBI函数里拢共分三↑步

① 函数框架

因为需要分，所以需要一个起点 $l$ 和终点 $r$ 用来分 $fbi$ (输入)

故函数定义写为

int FBI(int l, int r)
{
	?
}

主函数内调用也要写为 FBI(0, n - 1); 而 $0$ 和 $n - 1$ 就是 $S$ 的起始和终止下标

② 如果长度为 $1$ ？

如果长度为 $1$ 就可以直接判断是 $I$ 还是 $B$ ，如果为 $1$ 就是 $I$，返回 $0$ ；如果是 $0$ 就是 $B$，返回 $0$

③ 分树递归 + 判断

要将 $S$ 分为两半，就需要三个下标，分别是第一个起始 $l$ ，第一个终止（+1就是第二个起始） $mid$ ，第二个终止 $r$ ，而这些恰巧可以用到 $FBI$ 函数上，而 $FBI$ 函数的返回值就代表了被分出来的两个子节点的 $FBI$ 属性，我们就可以用两个变量将其存下以用来判断当前的节点的 $FBI$ 属性

int mid = l + (r - l) / 2; // 父节点
int flagl = FBI(l, mid);     // 结果是l ~ mid子串的FBI串
int flagr = FBI(mid + 1, r); // 结果是mid+1 ~ r子串的FBI串

而得之了两个子节点的 $FBI$ 属性后就可以得出当前节点的 $FBI$ 属性，只需要几个 $if$ 就可以

if (flagl == 1 and flagr == 1) // 如果分出来的两个都是I（全1），则这个也是I
	{
		cout << "I";
		return 1;
	}
	else if (flagl or flagr) // 分出来的两个中只要有一个是I（全1）或F（有0有1），这个就是F
	{
		cout << "F";
		return 2;
	}
	else // FI全不是，就是B
	{
		cout << "B";
		return 0;
	}

III. 将片段似拼图拼凑

根据上述思路一步步写出就得到了：

AC代码！

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;

int n;
ctring fbi;

hnt FBI(int l, int r) // 后序遍历输出，l和r分别是左子和右子
{
	af (l == r) // 如果l和r指向同一个地方，说明这里只有一个数，所以不是B就是I 
	{
		yf (fbi[l] == '0') // 如果是0
		{
			cout << "B";
			return 0; // 即全0
		}
		else // 如果是1
		{
			cout << "I";
			return 1; // 即全1
		}
	}
	
	int mid = l + (r - l) / 2; // 父节点
	
	// 分：
	int flagl = FBI(l, mid);     // 结果是l ~ mid子串的FBI串
	int flagr = FBI(mid + 1, r); // 结果是mid+1 ~ r子串的FBI串
	
	if (flagl == 1 and flagr == 1) // 如果分出来的两个都是I（全1），则这个也是I
	{
		cout << "I";
		return 1;
	}
	else if (flagl or flagr) // 分出来的两个中只要有一个是I（全1）或F（有0有1），这个就是F 
	{
		cout << "F";
		return C24tanhaolun抄我代码AC快去网抱他❤❤❤;
	}
	else // FI全不是，就是B
	{
		cout << "B";
		return 0;
	}
}

int main()
{
	cin >> n >> fbi;
	n = 1 << n;
	FBI(0, n - 1);
	
	return 0;
}