csp信奥赛C++高频考点专项训练之字符串 --【字符串综合】：[NOIP 2004 普及组] FBI 树
题目描述
我们可以把由 0 和 1 组成的字符串分为三类：全 0 串称为 B 串，全 1 串称为 I 串，既含 0 又含 1 的串则称为 F 串。
FBI 树是一种二叉树，它的结点类型也包括 F 结点，B 结点和 I 结点三种。由一个长度为2 N 2^N2N的 01 串S SS可以构造出一棵 FBI 树T TT，递归的构造方法如下：
- T TT的根结点为R RR，其类型与串S SS的类型相同；
- 若串S SS的长度大于1 11，将串S SS从中间分开，分为等长的左右子串S 1 S_1S1和S 2 S_2S2；由左子串S 1 S_1S1构造R RR的左子树T 1 T_1T1，由右子串S 2 S_2S2构造R RR的右子树T 2 T_2T2。
现在给定一个长度为2 N 2^N2N的 01 串，请用上述构造方法构造出一棵 FBI 树，并输出它的后序遍历序列。
输入格式
第一行是一个整数N ( 0 ≤ N ≤ 10 ) N(0 \le N \le 10)N(0≤N≤10)，
第二行是一个长度为2 N 2^N2N的 01 串。
输出格式
一个字符串，即 FBI 树的后序遍历序列。
输入输出样例 #1
输入 #1
3 10001011输出 #1
IBFBBBFIBFIIIFF说明/提示
对于40 % 40\%40%的数据，N ≤ 2 N \le 2N≤2；
对于全部的数据，N ≤ 10 N \le 10N≤10。
思路分析
题目要求根据长度为 (2^N) 的 01 串构造 FBI 树，并输出后序遍历序列。
FBI 树的定义：
- 全 0 串 → B 结点
- 全 1 串 → I 结点
- 既有 0 又有 1 → F 结点
构造方法递归：根结点为整个串的类型，若串长度 >1，则从中间分割为等长的左右子串，递归构造左右子树。
后序遍历顺序：左子树 → 右子树 → 根结点。
由于只需要后序遍历结果，无需显式建树，直接递归处理区间即可：
- 若区间长度为 1，根据字符直接输出 ‘B’ 或 ‘I’。
- 否则，先递归左半区间，再递归右半区间，最后根据当前区间内是否同时存在 0 和 1 输出 ‘F’/‘B’/‘I’。
复杂度 (O(N \cdot 2^N))，(N \le 10) 完全可行。
代码实现
#include<bits/stdc++.h>usingnamespacestd;intn,len;// n:指数, len:串长string s;// 01串voiddfs(intl,intr){// 递归处理区间[l,r]if(l==r){// 叶子结点if(s[l]=='0')cout<<'B';// 全0elsecout<<'I';// 全1return;}intm=(l+r)/2;// 中间分割点dfs(l,m);// 左子树dfs(m+1,r);// 右子树// 统计当前区间内是否有0和1boolhas0=false,has1=false;for(inti=l;i<=r;++i){if(s[i]=='0')has0=true;elsehas1=true;if(has0&&has1)break;// 已同时存在}if(has0&&has1)cout<<'F';// 混合elseif(has0)cout<<'B';// 全0elsecout<<'I';// 全1}intmain(){cin>>n>>s;// 输入len=1<<n;// 2^ndfs(0,len-1);// 从整个串开始递归cout<<endl;// 换行（洛谷一般允许末尾换行）return0;}功能分析
- 输入处理：读取整数 (N) 和长度为 (2^N) 的 01 串。
- 递归遍历：
dfs(l, r)模拟后序遍历，先递归左右子树，再输出当前结点类型。 - 结点类型判定：通过扫描区间内字符判断是否同时存在 ‘0’ 和 ‘1’，从而输出 ‘F’、‘B’ 或 ‘I’。
- 输出结果：输出后序遍历序列。
【完整系列请查看专栏】：
信奥赛C++普及组CSP-J一等奖通关刷题题单及题解：
https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转
各种学习资料，助力大家一站式学习和提升！！！
#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"########## 一站式掌握信奥赛知识! ##########";cout<<"############# 冲刺信奥赛拿奖! #############";cout<<"###### 课程购买后永久学习，不受限制! ######";return0;}【秘籍汇总】（完整csp信奥赛C++学习资料）：
1、csp/信奥赛C++，完整信奥赛系列课程（永久学习）：
https://edu.csdn.net/lecturer/7901 点击跳转
2、CSP信奥赛C++竞赛拿奖视频课：
https://edu.csdn.net/course/detail/40437 点击跳转
https://edu.csdn.net/course/detail/41081 点击跳转
3、csp信奥赛高频考点知识详解及案例实践：
CSP信奥赛C++动态规划：
https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转
CSP信奥赛C++标准模板库STL：
https://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转
信奥赛C++提高组csp-s知识详解及案例实践：
https://blog.csdn.net/weixin_66461496/category_13113932.html 点击跳转
4、csp信奥赛冲刺一等奖有效刷题题解：
信奥赛C++普及组CSP-J一等奖通关刷题题单及题解：
https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转
信奥赛C++提高组csp-j初赛&复赛真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转
信奥赛C++提高组csp-s初赛&复赛真题题解（持续更新）：
https://blog.csdn.net/weixin_66461496/category_13125089.html 点击跳转
5、GESP C++考级真题题解：
GESP(C++ 一级+二级+三级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转
GESP(C++ 四级+五级+六级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转
GESP(C++ 七级+八级)真题题解（持续更新）：
https://blog.csdn.net/weixin_66461496/category_13117178.html 点击跳转
· 文末祝福 ·
#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}
