P1087 [NOIP 2004 普及组] FBI 树

记录143#includebits/stdc.h using namespace std; // 使用标准命名空间std string s; // 存储01字符串 // 递归函数处理字符串区间 [l, r] void dfs(int l,int r) { // 1. 判断当前区间的类型 bool has0false,has1false; for(int il;ir;i) { if(s[i]0) has0true; else has1true; } char type; // 当前节点的类型 if(has0has1) typeF; // 既有0又有1 else if(has0) typeB; // 只有0 else typeI; // 只有1 // 2. 如果区间长度大于1继续递归切分左右子树 if(lr) { int mid(lr)/2; dfs(l,mid); // 递归左子树 dfs(mid1,r); // 递归右子树 } // 3. 后序遍历最后输出当前节点的类型 couttype; } int main() { // 主函数入口 ios::sync_with_stdio(false); // 关闭同步加速IO cin.tie(0); int n; cinns; // 读入N和01串 // 启动递归初始区间是整个字符串 [0, s.size()-1] dfs(0,s.size()-1); cout\n; // 输出换行 return 0; }题目传送门https://www.luogu.com.cn/problem/P1087前言我是一名专注信奥赛CSP-J/S、NOIP的教练。如果你觉得这篇题解对你有帮助欢迎点击关注我的CSDN账号我会持续更新高质量算法解析。我深知算法思维的构建远比单纯通过题目更重要本系列题解不局限于AC代码的堆砌而是致力于拆解题目背后的逻辑链条与核心知识点备赛路上若遇瓶颈欢迎随时评论或私信我将甄选典型疑难问题通过视频讲解或撰写专项文章的形式为你提供深度答疑。核心解题思路这道题是一道非常经典的递归分治与二叉树遍历问题。核心原理题目给出了 FBI 树的递归构造方法根节点的类型由当前字符串决定如果字符串长度大于 1则从中间一分为二分别构造左子树和右子树。这天然契合二叉树的结构。题目要求输出后序遍历序列即“左子树 - 右子树 - 根节点”的顺序。算法设计分治递归我们不需要真正地在内存中构建出树的结构即不需要定义节点类或结构体。只需要写一个递归函数传入当前处理的字符串区间[l, r]。在函数内部先判断当前区间对应的节点类型然后如果区间长度大于 1就递归处理左半区间和右半区间最后输出当前节点的类型。这种“先递归左右再输出自身”的操作恰好就是后序遍历。代码分块详细解释1. 头文件与全局变量定义#includebits/stdc.h using namespace std; // 使用标准命名空间std string s; // 存储01字符串详细分析题目中字符串的长度为 2N2N 当 N10N10 时字符串长度最多为 21010242101024 。使用string类型存储非常方便且可以像数组一样通过下标访问。将字符串定义为全局变量可以避免在递归函数中反复传递字符串提高运行效率。2. 核心逻辑分治递归函数dfs// 递归函数处理字符串区间 [l, r] void dfs(int l, int r) { // 1. 判断当前区间的类型 bool has0false, has1false; for(int il; ir; i) { if(s[i]0) has0true; else has1true; } char type; // 当前节点的类型 if(has0 has1) typeF; // 既有0又有1 else if(has0) typeB; // 只有0 else typeI; // 只有1 // 2. 如果区间长度大于1继续递归切分左右子树 if(l r) { int mid (lr)/2; dfs(l, mid); // 递归左子树 dfs(mid1, r); // 递归右子树 } // 3. 后序遍历最后输出当前节点的类型 cout type; }详细分析这是本题的灵魂所在完美体现了“分治”与“后序遍历”的结合。节点类型判定通过一个for循环遍历当前区间[l, r]内的所有字符用两个布尔变量has0和has1记录是否出现过 0 和 1。根据两者的组合情况确定当前节点是 F、B 还是 I。递归切分如果l r说明当前区间长度大于 1需要继续向下构造子树。计算中间位置mid (lr)/2然后分别对左半区间[l, mid]和右半区间[mid1, r]发起递归调用。后序输出注意代码的执行顺序是先调用dfs(l, mid)处理左子树再调用dfs(mid1, r)处理右子树最后才执行cout type输出根节点。这严格遵循了后序遍历“左右根”的规则保证了最终拼接出的字符串就是正确的后序遍历序列。3. 主函数输入处理与启动递归int main() { ios::sync_with_stdio(false); // 关闭同步加速IO cin.tie(0); int n; cin n s; // 读入N和01串 // 启动递归初始区间是整个字符串 [0, s.size()-1] dfs(0, s.size()-1); cout \n; // 输出换行 return 0; }详细分析主函数负责读取输入的 NN 和 01 串并启动递归。dfs(0, s.size()-1)表示最初我们要处理的是整个字符串左右边界分别是0和字符串长度-1。核心逻辑总结表代码模块核心变量/操作精炼作用解决的痛点节点类型判定has0与has1布尔标记遍历当前区间判断包含的字符种类准确确定当前递归层对应的节点是 F、B 还是 I递归切分int mid (lr)/2将当前区间从正中间一分为二完美契合 FBI 树“等长左右子串”的构造规则递归左子树dfs(l, mid)递归处理左半部分区间深入树的左侧分支遵循后序遍历“先左”的规则递归右子树dfs(mid1, r)递归处理右半部分区间深入树的右侧分支遵循后序遍历“后右”的规则根节点输出cout type在左右子树递归结束后输出当前类型遵循后序遍历“最后根”的规则直接拼接出最终答案递归终止if(l r)当区间长度为1时不再向下递归保证了递归在叶子节点处正确停止防止死循环