|
|
#include <bits/stdc++.h>
|
|
|
|
|
|
using namespace std;
|
|
|
|
|
|
|
|
|
//说白了，一切递归都是通过这个字符串进行构建树的，只不过在一直玩子串
|
|
|
string s;
|
|
|
|
|
|
// 还需要反复思考，体会其中的意思
|
|
|
// 本题目录入错误，不是2N，应该是2^N
|
|
|
|
|
|
/**
|
|
|
* 功能：递归构建的核心函数
|
|
|
* @param x 从第几个开始
|
|
|
* @param y 到第几个结束
|
|
|
*/
|
|
|
void BuildTree(int x, int y) {
|
|
|
//cout << "x=" << x << ",y=" << y << endl;
|
|
|
//如果一样，代表是叶子节点,就是同一个位置,这个是递归的终点，也可以理解为出口
|
|
|
if (x == y) {
|
|
|
if (s[x] == '0')
|
|
|
cout << "B";
|
|
|
else
|
|
|
cout << "I";
|
|
|
} else {
|
|
|
//进入这里，代表子串还够长，需要继续递归下去~
|
|
|
|
|
|
// 找到字符串的中点,注意这里面二分法的起止点选择办法
|
|
|
// x是从0开始的，y是长度-1
|
|
|
// 数字：1 2 3 4 5 6 7 8
|
|
|
// 索引：0 1 2 3 4 5 6 7
|
|
|
// 上面的序列是偶数个，那么 (y-x-1)/2= (7-0-1)/2=3,即索引为3的是一半的位置，0-3，4-7,这是真正的一家一半
|
|
|
int mid = (y - x - 1) / 2;
|
|
|
|
|
|
//构建前一半
|
|
|
BuildTree(x, x + mid); // 0+3=3,0--->3 就是 0,1,2,3，正好是4个。
|
|
|
|
|
|
//构建后一半
|
|
|
BuildTree(x + mid + 1, y); // 7-3=4,4--->7 就是 4,5,6,7，也是正好4个。
|
|
|
|
|
|
// 如果是奇数个数字的序列
|
|
|
// 数字： 1 2 3 4 5 6 7 8 9
|
|
|
// 索引： 0 1 2 3 4 5 6 7 8
|
|
|
// 那么 (y-x-1)/2= (8-0-1)/2=3,即索引为3的是一半的位置，0-3，4-8
|
|
|
// x---> x+mid 0--->3
|
|
|
// x+mid+1---->y 0+3+1--->8 4--->8
|
|
|
|
|
|
// 后序遍历开始，其实是要输出了，那么需要怎么输出呢？这取决于它的左右孩子是不是省心！
|
|
|
// 啥样是省心呢？1孩子数和0孩子数一样就是省心，否则就是不省心。
|
|
|
// 那怎么才能知道左边的孩子数和右边的孩子数呢？这个也不掌握啊~，这需要从原始的、已有的信息中获取了，在递归中无法知道，原始已有的信息是那个字符串s~~~
|
|
|
|
|
|
//中间节点最后输出，也就意味着是后序输出
|
|
|
int cnt0 = 0, cnt1 = 0; //cnt0:0的个数 cnt1:1的个数,
|
|
|
//计算这段子串中有几个0，几个1
|
|
|
for (int i = x; i <= y; ++i) {
|
|
|
if (s[i] == '0')
|
|
|
cnt0++;
|
|
|
else
|
|
|
cnt1++;
|
|
|
}
|
|
|
//全是1，那么输出I
|
|
|
if (cnt0 == 0)
|
|
|
cout << "I";
|
|
|
else if (cnt1 == 0) //如果全是0，那么输出B
|
|
|
cout << "B";
|
|
|
else //都有的话，输出F
|
|
|
cout << "F";
|
|
|
}
|
|
|
}
|
|
|
|
|
|
int main() {
|
|
|
int n; //这个n是个废物
|
|
|
//读入多组数据,以0为截止符
|
|
|
cin >> n >> s;
|
|
|
//调用递归函数进行构建,x->y代表字符串的起止位置,因为用到了折半递归，一般的思路是写一个递归函数，将开始和结束的索引号传入，在递归中折半进行。
|
|
|
BuildTree(0, s.size() - 1);
|
|
|
return 0;
|
|
|
} |
