描述
我们可以把由“0”和“1”组成的字符串分为三类：全“0”串称为B串，全“1”串称为I串，既含“0”又含“1”的串则称为F串。
FBI树是一种二叉树1，它的结点类型也包括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树，并输出它的后序遍历2序列。
格式
输入格式
输入的第一行是一个整数N(0<=N<=10)，第二行是一个长度为2^N的“01”串。
输出格式
输出包括一行，这一行只包含一个字符串，即FBI树的后序遍历序列。
样例1
样例输入1
3
10001011
样例输出1
IBFBBBFIBFIIIFF
限制
每个测试点1s
来源
NOIP2004普及组第三题
分析：DFS模拟，然后search_value(x,y)表示输出用x, y组成的树的后序遍历，返回0就是都是0，1就是都是1，2就是0，1都有。。
下面给出AC代码：
#include <bits/stdc++.h>
using namespace std;
char str[];
char write[]={'B','I','F'};
inline int read()
{
int x=,f=;
char ch=getchar();
while(ch<''||ch>'')
{
if(ch=='-')
f=-;
ch=getchar();
}
while(ch>=''&&ch<='')
{
x=x*+ch-'';
ch=getchar();
}
return x*f;
}
inline int search_value(int st,int ed)
{
if(st==ed)
{
printf("%c",write[str[st]-'']);
return str[st]-'';
}
int mid=(st+ed)/;
int x=search_value(st,mid);
int y=search_value(mid+,ed);
if(x==y)
{
printf("%c",write[x]);
return x;
}
else
{
printf("F");
return ;
}
}
int main()
{
int n;
n=read();
cin>>str;
search_value(,strlen(str)-);
return ;
}
貌似这题是二叉树的板子题，可以建立一棵二叉树，学习一下
#include <bits/stdc++.h>
using namespace std;
int s[];
struct Node
{
bool have_value;
char v;
Node *left,*right;
Node():have_value(false),left(NULL),right(NULL){};
};
Node *newNode()
{
return new Node();
}
void addNode(Node *root,int top,int bottom)
{
int sum=;
for(int i=top;i<=bottom;i++)
{
sum+=s[i];
}
if(sum==bottom-top+)
{
root->v='I';
}
else if(sum==)
{
root->v='B';
}
else
{
root->v='F';
}
root->have_value=true;
if(top<bottom)
{
root->left=newNode();
root->right=newNode();
addNode(root->left,top,(top+bottom)/);
addNode(root->right,(top+bottom)/+,bottom);
}
else
{
root->left=NULL;
root->right=NULL;
}
}
void postOrder(Node *root)
{
if(root==NULL)
return;
postOrder(root->left);
postOrder(root->right);
printf("%c",root->v);
}
int main()
{
int i=,N;
char c;
Node *root;
scanf("%d",&N);
getchar();
while((c=getchar())!='\n')
{
s[i++]=c-'';
}
root=newNode();
addNode(root,,i-);
postOrder(root);
return ;
}