首页 > itarticle > codevs1094 fbi tree

codevs1094 fbi tree

admin 11月 12, 2020 0

Problem Description

Problem URL:FBI Tree
Here is a definition:Strings which only contains ‘1’ is called I char-sequence;Strings which only contains ‘0’ is called ‘B’ char-sequence;Strings which contains both ‘1’ and ‘0’ is called ‘F’ char-sequence.Now,give out a 0-1 sequence ‘S’ which means there is only 1 and 0 in this sequence with the length of 2N,and give a rule of building a tree:
(1)T is the root node of the tree contains the sequence whose content is the same as ‘S’;
(2)If the length of the sequence is greater than 1,break the left half(S1) and right half(S2) to create left child and right child.
After building the tree,you need to return the Post-Traverse of types of nodes of the tree.
SAMPLE INPUT:
3
10001011
SAMPLE OUTPUT:
IBFBBBFIBFIIIFF

Problem Analysis

Actually it isn’t a hard work.We just follow the description and build up the tree.And figure out the type of the node when traversing.
We can simply use recursive algorithm to build up the tree.(Shows in AC CODE)

AC CODE

Time Consumption:AVERAGE 1.5ms

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

#define ls(x) x<<1
#define rs(x) (x<<1)+1

string tree[100001];
int N;

void build(int i){
    if(tree[i].size()==1){
        return;
    }
    int len = tree[i].size()>>1;
    tree[ls(i)]=tree[i].substr(0,len);
    tree[rs(i)]=tree[i].substr(len,len);
    build(ls(i));
    build(rs(i));
}

inline int judge(string s){
    bool have1,have0=false;
    have1=have0;
    for(int i=0;i<s.size();i++){
        if(s[i]=='1') have1=true;
        else have0=true;
    }
    if(have0 && have1) return 2;
    else if(have1) return 1;
    else return 0;
}

void post(int x){
    if(!tree[x].size()) return;
    post(ls(x));
    post(rs(x));
    switch(judge(tree[x])){
        case 1: putchar('I');break;
        case 0: putchar('B');break;
        case 2: putchar('F');break;
    }
}

int main(){
    cin>>N;
    cin>>tree[1];
    build(1);
    post(1);
    return 0;
}