1094 FBI树

1094 FBI树

2004年NOIP全国联赛普及组

时间限制: 1 s

空间限制: 128000 KB

题目等级 : 白银 Silver

题目描述 Description

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

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

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

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

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

输入描述 Input Description

输入的第一行是一个整数N（0 <= N <= 10），第二行是一个长度为2N的“01”串。

输出描述 Output Description

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

样例输入 Sample Input

3

10001011

样例输出 Sample Output

IBFBBBFIBFIIIFF

数据范围及提示 Data Size & Hint

对于40%的数据，N <= 2；

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

分类标签 Tags 点此展开

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 string s;
 6 void f(int l,int r)
 7 {
 8     int mid;
 9     mid=(l+r)/2;
10     if(l!=r)
11     {
12         f(l,mid);
13         f(mid+1,r);
14         int flag1=0;
15         int flag0=0;
16         for(int i=l;i<=r;i++)
17         {
18             if(s[i]=='0')
19             flag0=1;
20             else if(s[i]=='1')
21             flag1=1;
22         }
23         if(flag1==1&&flag0==1)
24         cout<<"F";
25         else if(flag1==1)
26         {
27             cout<<"I";
28         }
29         else if(flag0==1)
30         {
31             cout<<"B";
32         }
33     }
34     else 
35     {int flag1=0;
36         int flag0=0;
37         for(int i=l;i<=r;i++)
38         {
39             if(s[i]=='0')
40             flag0=1;
41             else if(s[i]=='1')
42             flag1=1;
43         }
44         if(flag1==1&&flag0==1)
45         cout<<"F";
46         else if(flag1==1)
47         {
48             cout<<"I";
49         }
50         else if(flag0==1)
51         {
52             cout<<"B";
53         }
54         return;
55         /*if(s[l]=='0')
56         cout<<"B";
57         else
58         cout<<"I";
59         return;*/
60     }
61 }
62 int main()
63 {
64     int meiyong;
65     cin>>meiyong;
66     cin>>s;
67     f(0,s.length()-1);
68     return 0;
69  } 

暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力暴力