首页 > [NOIP2004]FBI树
开通博客写题解
头像 Tianxn
发表于 2021-01-11 16:19:46
因为长度是偶数，所以二分很容易想到，很多树上的东西其实不需要建树的。 #include <iostream> #include <string> using namespace std; char FBI(string s) { if (s.length() > 展开全文
去ta的博客 赞 (16) 回复(0) 收起
头像 HGDB
发表于 2020-05-31 09:38:22
思路 1、T的根结点为R，其类型与串S的类型相同 2、若串S的长度大于1，将串S从中间分开，分为等长的左右子串S1和S2；由左子串S1构造R的左子树T1，由右子串S2构造R的右子树T2 意思就是如果这个串都是0那根节点就是B，都是1根结点就是I，有0也有1根节点就是F 树的遍历通常都是用递归实现，这 展开全文
去ta的博客 赞 (6) 回复(0) 收起
头像 savage
发表于 2019-08-21 16:41:51
题目描述 我们可以把由“0”和“1”组成的字符串分为三类：全“0”串称为B串，全“1”串称为I串，既含“0”又含“1”的串则称为F串。 FBI树是一种二叉树[1]，它的结点类型也包括F结点，B结点和I结点三种。由一个长度为的“01”串S可以构造出一棵FBI树T，递归的构造方 展开全文
去ta的博客 赞 (4) 回复(0) 收起
头像 微澜尛雨
发表于 2021-05-16 17:50:42
题目考点：分治（二分） 题目内容：给出一个01串，将其不断二分成一颗二叉树，求后序遍历；遍历过程中，若某一节点儿子均为1，输出‘I’，若均为0，输出‘F’，否则输出‘F’； 题目分析：如题目样例：3 10001011则有： #include<iostream> #include< 展开全文
去ta的博客 赞 (4) 回复(0) 收起
头像 在刷题的单身狗很开心
发表于 2023-09-01 16:04:15
题目中给的数据范围明确说明了长度是偶数，偶数的长度更容易分隔。题目中有要求后序遍历，那么可以从下向上进行是FBI的输出，又易知根是FBI的哪一种取决于子树的类型是否相同。 这样只需要让子节点将类型返回就可以简单地得到当前节点是什么类型。 #include <bits/std 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 ziuch
发表于 2020-08-23 21:59:36
题目描述 我们可以把由“0”和“1”组成的字符串分为三类：全“0”串称为B串，全“1”串称为I串，既含“0”又含“1”的串则称为F串。 FBI树是一种二叉树[1]，它的结点类型也包括F结点，B结点和I结点三种。由一个长度为2N的“01”串S 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 QAQ天战QAQ
发表于 2020-01-13 13:14:51
include include using namespace std;char s[(1<<10)+10];int work(int l,int r){ if(l==r) { if(s[l]=='0') cout<<"B"; else 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 威风镰鼬
发表于 2021-06-16 15:23:06
思路 题目要求的是后序遍历，我们可以从根结点出发，查找左右子树，达到叶子结点时返回类型flag，然后决定父节点的类型。 代码 #include<bits/stdc++.h> using namespace std; int len,n; string s; void f(string 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 savage
发表于 2019-09-11 14:14:51
题目描述 我们可以把由“0”和“1”组成的字符串分为三类：全“0”串称为B串，全“1”串称为I串，既含“0”又含“1”的串则称为F串。 FBI树是一种二叉树[1 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 吃花椒的妙酱
发表于 2021-01-30 15:30:27
#include <iostream> #include <vector> #include <bits/stdc++.h> #define minn -10000 using namespace std; typedef long long ll; int 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”