OI

【普及】FBI树

NOIP2004普及T3

由二叉树的性质，直接递归模拟了二分后序遍历过程，看起来也很清晰( • ̀ω•́ )✧

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<stdio.h>
#include<stdlib.h>
char ans[4000]={'\0'};
char s[2000]={'\0'};
void f2(int l,int r){
     int mid=(l+r)/2;
     if(l==r){
       if(s[l]=='1') printf("I");
       else printf("B");
       return;
     }
     f2(l,mid);
     f2(mid+1,r);
     int i,ff=1,fb=1,fi=1;
     for(i=l;i<=r;i++)
       if(s[i]=='1')fb=0;
       else fi=0;
     if(fi)printf("I");
     else if(fb)printf("B");
     else printf("F");
}
int main(){
    int n,x=1,i;
    scanf("%d",&n);
    scanf("%s",s);
    for(i=1;i<=n;i++)
      x*=2;  //length\
    f2(0,x-1);
    return 0;
}