首页 > 代码库 > Vijos P1114 FBI树【DFS模拟，二叉树入门】

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

2024-10-10 05:58:02   215人阅读

描述

我们可以把由“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

310001011

样例输出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     else38     {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 <cstring> 2 #include <cstdio> 3 #include <iostream> 4 using namespace std; 5 #define max(a,b) ((a>b)?(a):(b)) 6 int s[2000]={0}; 7 struct Node{ 8 bool have_value; 9 char v;10 Node *left,*right;11 Node():have_value(false),left(NULL),right(NULL){};12 };13 Node *newNode(){return new Node();}14 void addNode(Node *root,int top,int bottom){15 int sum=0;16 for(int i=top;i<=bottom;i++)sum+=s[i];17 if(sum==bottom-top+1)18     {root->v=‘I‘;}19 else if(sum==0)20      {root->v=‘B‘;}21 else22      {root->v=‘F‘;}23 root->have_value=http://www.mamicode.com/true;24 if(top<bottom){25 root->left=newNode();26 root->right=newNode();27 addNode(root->left,top,(top+bottom)/2);28 addNode(root->right,(top+bottom)/2+1,bottom);29 }30 else{31 root->left=NULL;32 root->right=NULL;33 }34 }35 void postOrder(Node *root){36 if(root==NULL)return;37 postOrder(root->left);38 postOrder(root->right);39 printf("%c",root->v);40 }41 int main(){42 int i=1,N;43 char c;44 Node *root;45 scanf("%d",&N);46 getchar();47 while((c=getchar())!=‘\n‘)s[i++]=c-‘0‘;48 root=newNode();49 addNode(root,1,i-1);50 postOrder(root);51 return 0;}

 

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


联系
我们