【NOIP2004】【Luogu1087】FBI树

problem

solution

codes

#include<stdio.h>
#define maxn 1<<12
using namespace std;
struct node{
    char t;
    int l, r;
    node():t('*'),l(0),r(0){}
}tree[maxn];
char s[maxn];
int top = -1;
char check(int le, int ri){
    int l=0, b=0;
    for(int i = le; i <= ri; i++){
        if(s[i]=='1')l=1;
        if(s[i]=='0')b=1;
    }
    if(l==1&&b==1)return 'F';
    if(l)return 'I';
    if(b)return 'B';
}
int build(int l, int r){
    if(l >= r){
        tree[++top].t = check(l,r);
        return top;
    }
    tree[++top].t = check(l,r);
    int now = top;
    int root = (l+r)/2;
    tree[now].l = build(l,root);
    tree[now].r = build(root+1,r);
    //printf("root:%d  top:%d\n",root,top+1);
    //printf("now:%d  lch:%d  rch:%d\n",now, tree[now].l,tree[now].r);
    return now;
}
void dfs(int root){
    //printf("root:%d %d %d\n",root,tree[root].l,tree[root].r);
    if(tree[root].l)dfs(tree[root].l);
    if(tree[root].r)dfs(tree[root].r);
    printf("%c",tree[root].t);
}
int main(){
    //freopen("data.in","r",stdin);
    int n;  scanf("%d%s",&n,s+1);
    n = 1<<n;
    build(1,n);
    dfs(0);
    return 0;
}
  

 

  
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
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
 

文章来源: gwj1314.blog.csdn.net，作者：小哈里，版权归原作者所有，如需转载，请联系作者。

原文链接：gwj1314.blog.csdn.net/article/details/80601411