Vijos P1114 FBI树【DFS模拟,二叉树入门】-阿里云开发者社区

开发者社区> 大数据> 正文

Vijos P1114 FBI树【DFS模拟,二叉树入门】

简介: 描述 我们可以把由“0”和“1”组成的字符串分为三类:全“0”串称为B串,全“1”串称为I串,既含“0”又含“1”的串则称为F串。 FBI树是一种二叉树1,它的结点类型也包括F结点,B结点和I结点三种。

描述

我们可以把由“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普及组第三题

题目链接:https://vijos.org/p/1114

分析: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 }

 

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
大数据
使用钉钉扫一扫加入圈子
+ 订阅

大数据计算实践乐园,近距离学习前沿技术

其他文章