当前位置：首页 > news >正文

MYOJ_4342:(洛谷P1087)[NOIP 2004 普及组] FBI 树(二叉树实操，递归提高)

news 来源：原创 2025/9/6 10:28:11

题目描述

我们可以把由 “0” 和 “1” 组成的字符串分为三类：全 “0” 串称为 B 串，全 “1” 串称为 I 串，既含 “0” 又含 “1” 的串则称为 F 串。
FBI 树是一种二叉树，它的结点类型也包括 F 结点，B 结点和 I 结点三种。由一个长度为 2N 的 “01” 串 S 可以构造出一棵 FBI 树 T，递归的构造方法如下：

T 的根结点为 R，其类型与串 S 的类型相同；
若串 S 的长度大于 1，将串 S 从中间分开，分为等长的左右子串 S1 和 S2；由左子串 S1 构造 R 的左子树 T1，由右子串 S2 构造 R 的右子树 T2。

现在给定一个长度为 2N 的 “01” 串，请用上述构造方法构造出一棵 FBI 树，并输出它的后序遍历序列。

对于 40% 的数据，N≤2；

对于全部的数据，N≤10。

输入

第一行是一个整数 N(0≤N≤10)，

第二行是一个长度为 2N 的 01 串。

输出

一个字符串，即 FBI 树的后序遍历序列。

样例输入输出

输入：输出：

3 IBFBBBFIBFIIIFF
10001011

方法一：

构建二叉树，这样比较直观。

STEP 1:构建结点池，使用指针p来跟踪下一个可用节点

STEP 2:建树，

1.首先判断是否为叶子节点，字符1为"I",0为'B'

2.构建左右子树，并确定节点类型:左右都是B->B,都是I->I，其他F

STEP 3:后序遍历函数，背口诀：先左后右最后根

STEP 4:输入N(在一和二中都不做使用)及01字符串，输入，建FBI树，后序遍历输出，完成。

#include<bits/stdc++.h>
#define N 2505
using namespace std;
struct Node
{char val;Node*left,*right;
}node[N],*p=node;
//根据01串构建fbl 
Node*createTree(string s)
{Node*np=++p;if(s.length()==1){if(s=="1"){np->val='I';}else{np->val='B';}return np;}np->left=createTree(s.substr(0,s.length()/2));np->right=createTree(s.substr(s.length()/2));if(np->left->val=='B'&&np->right->val=='B'){np->val='B';}else if(np->left->val=='I'&&np->right->val=='I'){np->val='I';}else{np->val='F';}return np;
}
//后序遍历以r为根的子树 
void postOrder(Node*r)
{if(r==NULL){return;}postOrder(r->left);postOrder(r->right);cout<<r->val;
}
int main()
{int a;string s;cin>>a>>s;Node*root=createTree(s);postOrder(root);return 0;
}

方法二：

递归，代码短，推荐使用。为了读者朋友有更好的收获，请先把方法一读完，更好理解方法二。

STEP 1:跟方法1一样，长度为1(即叶子节点)直接判断。

STEP 2:把字符串分成左右两部分进行递归，合并所得结果并确定类型，确定类型的方法与方法一一样，只不过改一下类型。

STEP 3:输入，调用。

#include<bits/stdc++.h>
using namespace std;
string FBL(string str)
{if(str.length()==1){if(str=="1"){cout<<"I";return"I";}else{cout<<"B";return "B";}}else{string left=FBL(str.substr(0,str.length()/2)),right=FBL(str.substr(str.length()/2,str.length()/2));string child=left+right;if(child=="II"){cout<<"I";return "I";}else if(child=="BB"){cout<<"B";return "B";}else{cout<<"F";return"F";}}
}   
int main()
{int n;string s;cin>>n>>s;FBL(s);return 0;
}

MYOJ_4342:(洛谷P1087)[NOIP 2004 普及组] FBI 树(二叉树实操，递归提高)

题目描述我们可以把由 “0” 和 “1” 组成的字符串分为三类：全 “0” 串称为 B 串，全 “1” 串称为 I 串，既含 “0” 又含 “1” 的串则称为 F 串。 FBI 树是一种二叉树，它的结点类型也包括 F 结点，B 结点和 I 结点三…...

编程日记 2025/9/6 10:28:11

LLM(13)：词编码后的位置

原则上，token 嵌入是大型语言模型（LLM）的合适输入。然而，LLM 的一个小缺点是它们的自注意力机制无法指导序列中 token 的位置或顺序。在前面介绍的嵌入层的工作方式中，无论 token ID 在输入序列中的位置如何&#xff0…...

编程日记 2025/9/3 7:47:16

MINIQMT学习课程Day4

聚宽的模拟/实盘跟单系统，已经全部介绍完毕，上传完毕了，相信大家已经可以进行聚宽的miniqmt的交易了。如果还有疑问，私信我进行沟通。现在开始进入新的课题，如何学习python，我不教那些乱七八糟的&#xff…...

编程日记 2025/9/6 10:25:08

AWS云服务：大数据公司实现技术突破与商业价值的核心引擎

在数据驱动决策的时代，大数据公司面临着海量数据存储、实时计算、复杂分析及安全合规等核心挑战。如何高效构建弹性、可扩展且低成本的技术架构，成为企业能否在竞争中胜出的关键。亚马逊云科技（AWS）作为全球云计算领域的领导者&am…...

编程日记 2025/9/5 22:24:20

Openpyxl使用教程(包含处理大数据量案例)

文章目录一、简介功能特性应用场景使用优势二、常用方法1、工作簿wb2、工作表ws 三、案例1、创建新工作簿2、将Excel数据存入list中3、按行读取文件(适合大文件)4、按指定行读取文件(适合大文件) 一、简介在 Python 数据处理领域，openpyxl 凭借其卓越的功能与易…...

编程日记 2025/9/6 8:29:42

蓝桥杯15届宝石组合

问题描述在一个神秘的森林里，住着一个小精灵名叫小蓝。有一天，他偶然发现了一个隐藏在树洞里的宝藏，里面装满了闪烁着美丽光芒的宝石。这些宝石都有着不同的颜色和形状，但最引人注目的是它们各自独特的 “闪亮度” 属性。每颗宝…...

编程日记 2025/9/1 22:38:20

THE UNIVERSITY OF MANCHESTER-NUMERICAL ANALYSIS 1-3.4数值积分-复合积分公式

3.4.1 复合梯形法则梯形法则仅使用两个点来近似积分，显然对于大多数应用来说，这不足够。为了提高精度，有多种方法可以利用更多的点和函数值。正如我们刚才在Newton-Cotes方法和辛普森法则中所看到的，一种方法是使用更高阶的插值函数。另一种方法是将区间划分为更小的区间…...

编程日记 2025/9/5 22:55:35

嵌入式系统应用-拓展-相关开发软件说明

这里以STM32的系列产品为例子，利用MDK的集成开发平台进行开发过程中，所有相关软件安装说明。 1 集成开发环境安装 1.1 MDK 下载 1.1.1 官网下载官方下载地址： https://www.keil.com/download/product/ 选择MDK-ARM ，填写一些…...

编程日记 2025/9/3 10:42:38

react实现上传图片到阿里云OSS以及问题解决（保姆级）

一、优势提高上传速度：前端直传利用了浏览器与 OSS 之间的直接连接，能够充分利用用户的网络带宽。相比之下，后端传递文件时，文件需要经过后端服务器的中转，可能会受到后端服务器网络环境和处理能力的限制，…...

编程日记 2025/9/4 15:24:15

嵌入式学习笔记——ARM-中断与异常

文章目录中断与异常的区别中断与 DMA 的区别中断能否睡眠？下半部能否睡眠？1. 中断处理程序不能睡眠2. 下半部（SoftIRQ、Tasklet、Workqueue） 中断处理注意点1. 快进快出2. 避免阻塞3. 正确返回值4. 如何处理大量任务5. 避免竞态问…...

编程日记 2025/8/31 20:58:15

OpenHarmony子系统开发 - 安全（十二）

OpenHarmony SELinux开发指导（五） 一、OpenHarmony SELinux常见问题 neverallow编译报错处理现象描述编译SELinux时会进行neverallow检查，当配置的策略不合理时，可能出现违反neverallow编译报错。 neverallow check failed…...

编程日记 2025/9/3 0:43:59

深入解析ARM与RISC-V架构的Bring-up核心流程

深入解析ARM与RISC-V架构的Bring-up核心流程作者：嵌入式架构探索者 | 2023年10月引言在嵌入式开发中，处理器的Bring-up（启动初始化）是系统运行的第一道门槛。ARM和RISC-V作为两大主流架构，其Bring-up流程既有共性…...

编程日记 2025/8/27 15:22:11

挺经典的回溯题的。 class Solution { public:vector<vector<int>> result;void recursion(vector<int>& nums,vector<int>& now){if(nums.size()0){result.push_back(now);return ;}for(int i0;i<nums.size();i){now.push_back(nums[i]);…...

编程日记 2025/9/3 13:16:34

vue中如何动态的绑定图片

在项目中遇到需要动态的改变图片路径，图片路径并非是从后台获取过来的数据。因此在data中必须用require加载，否则会当成字符串来处理。...

编程日记 2025/8/27 14:13:09

湖北师范大学计信学院研究生课程《工程伦理》12.6章节练习

1【单选题】下列哪个不是数字身份的特点？ A. 多样性 B. 唯一性 C. 可变性 D. 允许匿名和假名 2【单选题】下列哪项不是现代国家的基本职能。 A. 保护政权统一 B. 保护本国面对其他国家侵犯 C. 保护国内每个人免受他人侵犯 D. 承担发展国民经济 3【单选题】哪个国家在全球率先发…...

编程日记 2025/9/3 1:33:05

prism WPF 登录对话框登录成功后显示主界面

prism WPF 登录对话框登录成功后显示主界面项目结构 LoginUC.xaml <UserControl x:Class"PrismWpfApp.Views.LoginUC"xmlns"http://schemas.microsoft.com/winfx/2006/xaml/presentation"xmlns:x"http://schemas.microsoft.com/winfx/2006/xaml…...

编程日记 2025/9/3 13:05:21

MySQL统计信息

1. 什么是统计信息？ 统计信息就像是数据库的"地图"，它告诉优化器： 每个表有多大（有多少行数据） 每个索引的"区分度"（有多少不同的值） 数据分布情况（哪些值出…...

编程日记 2025/9/4 17:02:17

Spark，配置hadoop集群2

编写Hadoop集群启停脚本 1.建立新文件，编写脚本程序在hadoop101中操作，在/root/bin下新建文件：myhadoop，输入如下内容： 2.分发执行权限保存后退出，然后赋予脚本执行权限 [roothadoop101 ~]$ chmod x /r…...

编程日记 2025/9/2 14:34:55

⭐算法OJ⭐重建行程【哈密尔顿路径】（C++ 实现）Reconstruct Itinerary

You are given a list of airline tickets where tickets[i] [from_i, to_i] represent the departure and the arrival airports of one flight. Reconstruct the itinerary in order and return it. All of the tickets belong to a man who departs from “JFK”, thus, t…...

编程日记 2025/9/1 5:37:13

大模型如何优化数字人的实时交互与情感表达

标题:大模型如何优化数字人的实时交互与情感表达内容:1.摘要随着人工智能技术的飞速发展，数字人在多个领域的应用愈发广泛，其实时交互与情感表达能力成为提升用户体验的关键因素。本文旨在探讨大模型如何优化数字人的实时交互与情感表达。通过分析大模…...

编程日记 2025/9/4 14:27:50

【含文档+PPT+源码】基于SpringBoot+Vue旅游管理网站

项目介绍本课程演示的是一款基于SpringBootVue旅游管理网站，主要针对计算机相关专业的正在做毕设的学生与需要项目实战练习的 Java 学习者。 1.包含：项目源码、项目文档、数据库脚本、软件工具等所有资料 2.带你从零开始部署运行本套系统 3.该项目附…...

编程日记 2025/8/27 14:12:56

理解OSPF Stub区域和各类LSA特点

之前学习到OSPF特殊区域和各类类型LSA的分析后，一直很混乱，在网上也难找到详细的解释，在看了 HCNP书本内容后，对这块类容理解更加清晰，本次内容，我们使用实验示例，来对OSPF特殊区域和各类型LSA…...

编程日记 2025/9/5 19:38:59

AI智算-K8s如何利用GPFS分布式并行文件存储加速训练or推理

文章目录 GPFS简介核心特性存储环境介绍存储软件版本客户端存储RoCEGPFS 管理（GUI）1. 创建 CSI 用户2. 检查GUI与k8s通信文件系统配置1. 开启配额2. 启用filesetdf文件系统3. 验证文件系统配置4. 启用自动inode扩展存储集群配置1. 启用对根文件集（root fileset）配额2. igno…...

编程日记 2025/8/26 15:50:28

Linux如何设置bash为默认shell

大部分情况下，Linux的默认shell是bash，但某些Linux发行版，例如Kali，默认的终端是zsh，本文以Kali为例，将Kali的默认shell从zsh改为bash。其实Kali早期的shell也是bash，2020 版本之后&#xff1a…...

编程日记 2025/9/3 9:27:24

leetcode-代码随想录-链表-翻转链表

题目链接：206. 反转链表 - 力扣（LeetCode） 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。输入：head [1,2,3,4,5] 输出：[5,4,3,2,1]class Solution { public:ListNode* rev…...

编程日记 2025/9/4 11:34:29

CSS快速上手

第一章 CSS基础首先来回答2个问题。 1.CSS是什么？ CSS是用来控制网页外观的一门技术。 2.前端最核心的技术是什么？他们分别是用来干吗的？ 前端最核心的技术有：HTML、CSS、JavaScript。 HTML用于控制网页的结构，CSS…...

编程日记 2025/8/31 11:19:58

虚拟现实 UI 设计：打造沉浸式用户体验

VR UI 设计基础与特点虚拟现实技术近年来发展迅猛，其独特的沉浸式体验吸引了众多领域的关注与应用。在 VR 环境中，UI 设计扮演着至关重要的角色，它是用户与虚拟世界交互的桥梁。与传统 UI 设计相比，VR UI 设计具有显著的特点。传…...

编程日记 2025/8/31 13:15:07

搜索与图论树的广度优先遍历图中点的层次

适用性当边的权值相等时，使用广度优先遍历，往往是求图（树）的最短路径最优方法抽象理解伪代码建立队列添加第一个起始点到队列，标记其不可访问 while(队列不为空)//开始循环{获取队列中的队首元素，获…...

编程日记 2025/9/1 4:41:59

DHCP之报文格式

字段说明： op (op code): 表示报文的类型，取值为 1 或 2，含义如下 1:客户端请求报 2:服务器响应报文 Secs (seconds):由客户端填充，表示从客户端开始获得 IP 地址或 IP 地址续借后所使用了的秒数，缺省值为 3600s。 F…...

编程日记 2025/9/2 17:40:18

Docker安装、配置Redis

1.如果没有docker-compose.yml文件的话，先创建docker-compose.yml 配置文件一般长这个样子 version: 3services:redis:image: redis:latestcontainer_name: redisports:- "6379:6379"command: redis-server --requirepass "123456"restart: a…...

编程日记 2025/9/6 8:28:56

空中无人机等动态目标识别2025.4.4

* 一.无人机动态数据概述* 1.1 空中动态数据定义在无人机动态数据的范畴中， 空中动态数据是一个核心概念。它主要包括无人机在飞行过程中产生的各种实时信息，如位置、速度、高度、姿态等[1]。这些数据通过传感器系统采集，并以特定格式存…...

编程日记 2025/9/4 11:14:17

【AI论文】通过R1-Zero类似训练改进视觉空间推理

摘要：人们越来越关注提升多模态大型语言模型（MLLMs）的推理能力。作为在物理领域中运作的人工智能代理的基石，基于视频的视觉空间智能（VSI）成为MLLMs最为关键的推理能力之一。本研究首次深入探讨了通过R1-Ze…...

编程日记 2025/9/2 7:26:18

游戏引擎学习第203天

回顾当前情况在这里我将直播完成整个游戏的制作。我们现在面临一些技术上的困难，确实如此。我的笔记本电脑的电源接口坏了，所以我不得不准备了这台备用笔记本，希望它能够正常工作。我所以希望一切都还好，尽管我不完全确定是否一…...

编程日记 2025/9/1 21:34:28

从菜鸟到高手的提示词优化指南‌

如何用“说话的艺术”榨干AI潜力？ ——从菜鸟到高手的提示词优化指南‌ 一、什么是好的提示词？ 核心公式‌：精准提问明确需求限定条件示范案例好比让AI帮你买咖啡—— ❌ 差提示：“帮我买杯咖啡”（AI可能随便…...

编程日记 2025/9/5 20:29:42

应对高并发的根本挑战：思维转变【大模型总结】

以下是对这篇技术总结的详细解析，以分步说明的形式呈现，帮助理解亿万并发场景下的核心策略与创新思维： 一、应对高并发的根本挑战：思维转变 1. 传统架构的局限问题：传统系统追求零故障和强一致性，但在海…...

编程日记 2025/9/5 11:37:38

【Java集合】单列集合List详解

参考笔记： java 单列集合List 万字详解（通俗易懂）_java singlelist-CSDN博客目录前言： 一、概述二、特点三、使用集合的经典四部曲四、List接口常用的方法五、List接口实现类——ArrayList 六、List接口实现类——Ve…...

编程日记 2025/9/5 0:03:56

蓝桥刷题note13（排序)

1.冒泡排序适用场景： 数据量较小：适用于数据量较小的情况，例如数组长度在 10 以内。优点稳定性：冒泡排序是一种稳定的排序算法，相同元素的相对顺序不会改变。缺点时间复杂度高：平均和最坏时间复杂度为…...

编程日记 2025/9/5 21:48:46

【AI模型核心流程】(一)大语言模型输入处理机制详解与常见误解辨析

一、引言大语言模型（LLM）如GPT、BERT、LLaMA等，已成为自然语言处理领域的核心技术。然而，许多开发者对其底层输入处理机制存在误解，尤其是从自然语言文本到模型可理解的向量表示这一过程。本文将从技术细节出发&…...

编程日记 2025/9/3 19:02:32

如何完整迁移 Git 仓库？

Git 已经成为软件开发中版本控制和协作的事实上的标准。有时，开发人员可能需要将整个 Git 存储库 (包括其历史记录、分支和标记) 移动到新的位置或托管服务。在这个全面的指南中，我们将讨论在不丢失任何关键数据或历史记录的情况下无缝地重新定位完整 Gi…...

编程日记 2025/9/6 0:30:30

《在 Ubuntu 22.04 上安装 CUDA 11.8 和 Anaconda，并配置环境变量》

安装 CUDA 11.8 和 Anaconda 并配置环境变量在本教程中，我们将介绍如何在 Ubuntu 22.04 上安装 CUDA 11.8 和 Anaconda，并配置相应的环境变量。我们还将配置使用阿里云镜像源来加速软件包更新。以下是具体步骤。步骤 1：更新软件源首先…...

编程日记 2025/9/2 7:15:52

残差神经网络（ResNet）概念解析与用法实例：简洁的图像处理任务

目录 1. 前言 2. ResNet的核心思想 2.1 残差学习 2.2 跳跃连接 3. ResNet的架构 3.1 残差块 3.2 ResNet的整体架构 4. ResNet实例：随便处理处理图像 5. 总结 1. 前言随着深度学习的发展，神经网络的层数不断增加，但随之而来的是梯度…...

编程日记 2025/9/1 1:22:29

家里网络访问Github有时候打不开，解决办法

1、修改Hosts文件修改法通过DNS查询工具（如）获取最新GitHub域名解析IP修改系统hosts文件（路径：C:\Windows\System32\drivers\etc\hosts），添加：20.205.243.166 github.com 20.27.177.113 github…...

编程日记 2025/8/27 11:36:17

VirtualBox 配置双网卡（NAT + 桥接）详细步骤

在 VirtualBox 中为 CentOS 虚拟机配置双网卡（NAT 桥接），使其既能访问外网（NAT），又能与宿主机（Windows 10）或局域网通信（桥接）。步骤 1：关闭虚…...

编程日记 2025/9/3 4:33:56

【2023】ORIGIN或MATLAB 颜色图，等高图，颜色条——需要拟合补全中间的颜色

前言不是我疯了，就是世界疯了。我不知道究竟是哪一个疯了。瓶口和瓶盖尺寸不符。也许该怪瓶子，也许该怪盖子。但不管怎样，尺寸不符的事实不容动摇——《1Q84》 \;\;\;\;\;\; 有十几二十个导出的曲线数据，其中第一列是频率点，大约1001个，第二列是某种数据，都在0~1之间…...

编程日记 2025/9/6 8:42:15

flutter 专题七十三Flutter打包未签名的ipa

在Flutter项目开发完成之后，需要把iOS项目拿给第三方（如打包机）进行签名，那我们首先就需要准备打包好未签名的的ipa包。打包之前，需要先从第三方获取到iOS证书(.p12)和描述文件(.mobileprovision)，然后然…...

编程日记 2025/8/31 20:25:18

ngx_get_full_name

定义在 src\core\ngx_file.c ngx_int_t ngx_get_full_name(ngx_pool_t *pool, ngx_str_t *prefix, ngx_str_t *name) {size_t len;u_char *p, *n;ngx_int_t rc;rc ngx_test_full_name(name);if (rc NGX_OK) {return rc;}len prefix->len;#if (NGX_WIN32)if (…...

编程日记 2025/8/27 11:36:08

leetcode-代码随想录-链表-链表总结篇

理论基础链表： 每个节点由两部分组成：数据域和指针域（存放指向下一个节点的指针）；入口节点称为头节点；最后一个节点的指针域指向NULL（空指针）。分类： 单链表双链表&…...

编程日记 2025/9/3 7:10:59

如何用Python轻松实现快速复制或剪切文件列表中的所有文件呢？

在程序开发的过程中，处理文件是我们日常工作中一个很重要的环节。想象一下，当你需要把一大堆文件从一个文件夹移动到另一个文件夹时，手工操作真的会让人觉得烦躁对吧？这时，用代码来处理这些烦恼，真是太方便…...

编程日记 2025/9/4 20:18:48

【棒垒球规则】全国幼儿软式棒垒球比赛规则（二）·棒球1号位

幼儿棒垒球设备 2.01 球棒球棒使用组委会提供的泡棉发泡安全球棒，以安全环保材料制成；球棒规格：长度为 53 厘米，重量为 200 克（10 克），棒头直径为 7 厘米，握把直径为 3 厘米。 2…...

编程日记 2025/8/30 12:37:51

在MacOS 10.15上使用MongoDB

这次是在MacOS 10.15上使用MongoDB。先在豆包问支持MacOS 10.15的MongoDB最新版是什么，答案是MongoDB 5.0。抱着谨慎怀疑的态度去官方网站查询了一下，答案如下 MongoDB 7.x支持的最低版本MacOS是11MongoDB 6.x支持的最低版本MacOS是10.14 又找deepsee…...

编程日记 2025/9/1 11:01:11

题目描述

输入

输出

样例输入输出

方法一：

方法二：

相关文章：