csp信奥赛C++高频考点专项训练之字符串 --【字符串综合】：[NOIP 2004 普及组] FBI 树

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输入 #13 10001011输出 #1IBFBBBFIBFIIIFF说明/提示对于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) 完全可行。代码实现#includebits/stdc.husingnamespacestd;intn,len;// n:指数, len:串长string s;// 01串voiddfs(intl,intr){// 递归处理区间[l,r]if(lr){// 叶子结点if(s[l]0)coutB;// 全0elsecoutI;// 全1return;}intm(lr)/2;// 中间分割点dfs(l,m);// 左子树dfs(m1,r);// 右子树// 统计当前区间内是否有0和1boolhas0false,has1false;for(intil;ir;i){if(s[i]0)has0true;elsehas1true;if(has0has1)break;// 已同时存在}if(has0has1)coutF;// 混合elseif(has0)coutB;// 全0elsecoutI;// 全1}intmain(){cinns;// 输入len1n;// 2^ndfs(0,len-1);// 从整个串开始递归coutendl;// 换行洛谷一般允许末尾换行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 点击跳转各种学习资料助力大家一站式学习和提升#includebits/stdc.husingnamespacestd;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标准模板库STLhttps://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 点击跳转· 文末祝福 ·#includebits/stdc.husingnamespacestd;intmain(){cout跟着王老师一起学习信奥赛C;cout 成就更好的自己 ;cout csp信奥赛一等奖属于你! ;return0;}