题目描述

我们可以把由“0”和“1”组成的字符串分为三类:全“0”串称为B串,全“1”串称为I串,既含“0”又含“1”的串则称为F串。

FBI树是一种二叉树,它的结点类型也包括F结点,B结点和I结点三种。由一个长度为2^N的“01”串S可以构造出一棵FBI树T,递归的构造方法如下:

1) T的根结点为R,其类型与串S的类型相同;

2) 若串S的长度大于1,将串S从中间分开,分为等长的左右子串S1和S2;由左子串S1构造R的左子树T1,由右子串S2构造R的右子树T2。

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

输入输出格式

输入格式:

第一行是一个整数N(0 <= N <= 10),第二行是一个长度为2^N的“01”串。

输出格式:

包括一行,这一行只包含一个字符串,即FBI树的后序遍历序列。

输入输出样例

输入样例#1:

3
10001011
输出样例#1:

IBFBBBFIBFIIIFF

说明

对于40%的数据,N <= 2;

对于全部的数据,N <= 10。

noip2004普及组第3题

思路

线段树的build建树操作;

代码实现

 #include<cstdio>
const int maxn=<<;
int n;
char t[maxn],ch[maxn];
void build(int k,int l,int r){
if(l==r){
t[k]=ch[l-]==''?'B':'I';
putchar(t[k]);
return;
}
int mid=l+r>>,ls=k<<,rs=ls+;
build(ls,l,mid);
build(rs,mid+,r);
if(t[rs]==t[ls]) t[k]=t[ls];
else t[k]='F';
putchar(t[k]);
}
int main(){
scanf("%d",&n);
scanf("%s",ch);
build(,,<<n);
return ;
}

最新文章

  1. golang语言构造函数
  2. HIbernate的property-ref属性
  3. SSAS 部署失败 总结
  4. Microsoft Visual C++ Compiler for Python 2.7
  5. jquery 上传图片即时预览功能
  6. 新颖的O2O商业模式,江水平和他的装修队
  7. PowerDesigner 根据NAME属性自动生成表和列注释(不用写脚本)
  8. WCF技术剖析之二十八:自己动手获取元数据[附源代码下载]
  9. shell中bash的常见命令
  10. JavaScript实现轮播图(隔3秒显示一张图)
  11. spring的核心组件及作用(一)
  12. 爱奇艺技术分享:爱奇艺Android客户端启动速度优化实践总结
  13. C#工具:Bootstrap WPF Style,Bootstrap风格的WPF样式
  14. ASP.NET MVC 3 Application Upgrader
  15. [转]MySQL查询缓存清空
  16. 2018牛客网暑假ACM多校训练赛(第四场)B Interval Revisited 动态规划
  17. TensorFlow函数教程:tf.nn.dropout
  18. yum节省安装时间
  19. postgresql逻辑结构--用户及权限管理(七)
  20. CentOS 7下搭建配置SVN服务器

热门文章

  1. C# 的占位符
  2. 关于Python多线程condition变量的应用
  3. Pro ASP.NET Core MVC 第6版 第二章(前半章)
  4. 继续C#开发or转做产品
  5. (转)全文检索技术学习(一)——Lucene的介绍
  6. POJ_2239_Selecting Courses
  7. 类似倒圆角方法输入半径选择实体 kword
  8. CAD插入图片
  9. Gitlab forbidden
  10. 数据导出为Excel(未完)