被迫无奈，在老师的一再要求下要把代码写在知乎专栏里投稿，既然为知乎写了一份，怎么能不在自己博客里放一份呢？
所以又开了一个新坑了——ACM
FBI Tree
题目描述
我们可以把由“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从中间分开，分为等长的左右子串S_1和S_2；由左子串S_1构造R的左子树T_1，由右子串S_2构造R的右子树T_2。
现在给定一个长度为2^N的“01”串，请用上述构造方法构造出一棵FBI树，并输出它的后序遍历序列。
输入格式
第一行是一个整数N(0≤N≤10)，
第二行是一个长度为2^N的“01”串。
输出格式
一个字符串，即FBI树的后序遍历序列。
输入输出样例
输入
3
10001011
输出
IBFBBBFIBFIIIFF
说明/提示
对于40%的数据， N≤2；
对于全部的数据， N≤10。
noip2004普及组第3题
题解
递归实现：
#include<stdio.h> int a; char c,t; char get(int n){ if(n){ if((t=get(n-1))!=get(n-1)) t='F'; } else{ do{ scanf("%c",&c); }while(c=='\n'||c=='\r'); if(c-48) t='I'; else t='B'; } printf("%c",t); return t; } int main(){ scanf("%d",&a); get(a); return 0; }
测试结果：
优点：
可以说是洛谷里时间最短、内存最小、代码量最少的 (“开挂”的除外)
1、运行时间短：洛谷测试耗时20ms，没有字符串的运算，处理速度更快。
2、占用内存小：洛谷测试消耗内存652Bytes，只定义了1个int，2个char和1个长度为3的char数组。
3、代码量少：只有340Bytes。
4、数据承受量大：没有开数组而是读一个字符处理一个，数据量越大，储存空间和字符串运算的时间开销相对越小，而且不用设置数组下标，所以只要不爆栈，对于N<231-1的所有数据都能应对自如。经测试N=20时，任务管理器监视内存消耗0.4MB，python监视时间消耗700ms左右。
缺点：
数据量大了之后可能会栈溢出
循环实现：
#include<stdio.h>
#include<stdlib.h>
int main(){
int n,length,i=0;
char h[3],*a=(char *)calloc(n,sizeof(char)),c;
scanf("%d",&n);
gets(h);
while(i<=n){
scanf("%c",&c);
if(c-48) c='I';
else c='B';
int j=0;
while(1){
printf("%c",c);
if(a[j]){
if(c-a[j]) c='F';
a[j++]=0;
}
else{
a[j++]=c;
break;
}
}
i=j>i?j:i;
}
return 0;
}
测试结果：
优点：
1、运行速度快、内存占用小、对大数据更友好
2、比递归实现更好的地方：不会爆栈
缺点：
代码没有递归实现简洁，数据量大时运行速度没有递归快
