我们可以把由“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树的后序遍历序列。
3
10001011
IBFBBBFIBFIIIFF
每个测试点1s
NOIP2004普及组第三题
分析:DFS模拟,然后search_value(x,y)表示输出用x, y组成的树的后序遍历,返回0就是都是0,1就是都是1,2就是0,1都有。。
下面给出AC代码:
1 #include <bits/stdc++.h>
2 using namespace std;
3 char str[2020];
4 char write[3]={'B','I','F'};
5 inline int read()
6 {
7 int x=0,f=1;
8 char ch=getchar();
9 while(ch<'0'||ch>'9')
10 {
11 if(ch=='-')
12 f=-1;
13 ch=getchar();
14 }
15 while(ch>='0'&&ch<='9')
16 {
17 x=x*10+ch-'0';
18 ch=getchar();
19 }
20 return x*f;
21 }
22 inline int search_value(int st,int ed)
23 {
24 if(st==ed)
25 {
26 printf("%c",write[str[st]-'0']);
27 return str[st]-'0';
28 }
29 int mid=(st+ed)/2;
30 int x=search_value(st,mid);
31 int y=search_value(mid+1,ed);
32 if(x==y)
33 {
34 printf("%c",write[x]);
35 return x;
36 }
37 else
38 {
39 printf("F");
40 return 2;
41 }
42 }
43 int main()
44 {
45 int n;
46 n=read();
47 cin>>str;
48 search_value(0,strlen(str)-1);
49 return 0;
50 }
貌似这题是二叉树的板子题,可以建立一棵二叉树,学习一下
1 #include <bits/stdc++.h>
2 using namespace std;
3 int s[2020];
4 struct Node
5 {
6 bool have_value;
7 char v;
8 Node *left,*right;
9 Node():have_value(false),left(NULL),right(NULL){};
10 };
11 Node *newNode()
12 {
13 return new Node();
14 }
15 void addNode(Node *root,int top,int bottom)
16 {
17 int sum=0;
18 for(int i=top;i<=bottom;i++)
19 {
20 sum+=s[i];
21 }
22 if(sum==bottom-top+1)
23 {
24 root->v='I';
25 }
26 else if(sum==0)
27 {
28 root->v='B';
29 }
30 else
31 {
32 root->v='F';
33 }
34 root->have_value=true;
35 if(top<bottom)
36 {
37 root->left=newNode();
38 root->right=newNode();
39 addNode(root->left,top,(top+bottom)/2);
40 addNode(root->right,(top+bottom)/2+1,bottom);
41 }
42 else
43 {
44 root->left=NULL;
45 root->right=NULL;
46 }
47 }
48 void postOrder(Node *root)
49 {
50 if(root==NULL)
51 return;
52 postOrder(root->left);
53 postOrder(root->right);
54 printf("%c",root->v);
55 }
56 int main()
57 {
58 int i=1,N;
59 char c;
60 Node *root;
61 scanf("%d",&N);
62 getchar();
63 while((c=getchar())!='\n')
64 {
65 s[i++]=c-'0';
66 }
67 root=newNode();
68 addNode(root,1,i-1);
69 postOrder(root);
70 return 0;
71 }