题解 | #[NOIP2004]FBI树#

思路

题目要求的是后序遍历，我们可以从根结点出发，查找左右子树，达到叶子结点时返回类型flag，然后决定父节点的类型。

代码

#include<bits/stdc++.h>
using namespace std;

int len,n;
string s;

void f(string str,int len){
    int flag1=0,flag0=0;
//    cout<<str<<" "<<len<<endl;
    if(len==1){
        if(str=="1") cout<<"I";
        if(str=="0") cout<<"B"; 
    }else{
        f(str.substr(0, len/2),len/2);
        f(str.substr(len/2, len),len/2);
        for(int i=0;i<len;i++){
            if(str[i]=='1') flag1=1;
            if(str[i]=='0') flag0=1;
        }
        if(flag1&&flag0) cout<<"F";
        if(flag1&&!flag0) cout<<"I";
        if(flag0&&!flag1) cout<<"B";
    }
    return;
}

int main(){
    cin>>n;
    len=pow(2,n);
     cin>>s;
    f(s,len);
    return 0;
}