#include<iostream>
using namespace std;
char a[1024 + 5];
int n;
char fun(char *s, int L){
if(L == 1){
if(*s == '0'){
cout<<'B';
return 'B';
}else{
cout<<'I';
return 'I';
}
}else{
char ch1, ch2;
ch1 = fun(s, L/2);
ch2 = fun(s + L/2, L/2);
if(ch1 == ch2){
cout<<ch1;
return ch1;
}else{
cout<<'F';
return 'F';
}
}
}
int main(){
//freopen("test.txt", "r", stdin);
cin>>n;
int i;
n = (1<<n);
cin>>a;
fun(a, n);
return 0;
}

#不知为啥代码都那么长~~~~
cpp
#include<bits/stdc++.h>
using namespace std;
char a[1040];
int n;
char FBITREE(int l,int r){
if (l == r) if (a[l] == '1') return 'I'; else return 'B';
char fl = FBITREE(l,(l+r)/2); cout<<fl;
char fr = FBITREE((l+r)/2+1,r); cout<<fr;
if (fl == fr) return fl; else return 'F';
}
int main(){
cin>>n>>a;
int al = strlen(a);
cout<<FBITREE(0,al-1)<<endl;
}


python 递归

class node:
    def __init__(self, mark):
        self.mark = mark
        self.left = None
        self.right = None

def str_type(string):
    if not '0' in string:
        return 'I'
    if not '1' in string:
        return 'B'
    return 'F'

def build_tree(string):
    root = node(str_type(string))
    if len(string) == 1:
        return root
    root.left = build_tree(string[:len(string)//2])
    root.right = build_tree(string[len(string)//2:])
    return root

def generate_post_seq(tree):
    if not tree:
        return ''
    return generate_post_seq(tree.left) + generate_post_seq(tree.right) + tree.mark

_ = input()
string = input().strip()
print(generate_post_seq(build_tree(string)))

用了个栈数组，代码短了点

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<stack>
#include<map>
using namespace std;
int n,bit=1,k=0,j;
char a,b;
map<char,char> mark;
stack<char> s[11];
int main(){
    scanf("%d",&n);
    getchar();
    mark['0'] = 'B'; mark['1'] = 'I'; mark['2'] = 'F';
    for(int i=0;i<n;i++) bit <<= 1;
    for(int i=0;i<bit;i++){
        scanf("%c",&a);
        //cout<<"i="<<i<<"\ta="<<a<<endl;
        j = 0;
        s[j].push(a);
        printf("%c",mark[a]);
        while(s[j].size()==2){
            a = s[j].top();s[j].pop();
            b = s[j].top();s[j].pop();
            if(a!=b) s[j+1].push('2');
            else s[j+1].push(a);
            printf("%c",mark[s[j+1].top()]);
            j++;
        }
    }
    return 0;
}

拼死写了个非递归
这是位运算用的最熟的一次

#include<iostream>
#include<cstdio>
using namespace std;
int a[(1<<11)],ans[(1<<12)],ceng[(1<<12)],f[(1<<12)],zong[11];
int n;
int main()
{
    int i,now=0,k,j,now1,now2,shi,c,b,has;
    cin>>n;
    getchar();
    for(i=1;i<=(1<<n);i++)
     {
      a[i]=getchar()-'0';
      ceng[i]=n;
     if(a[i]==0)
      ans[i]='B';
    else
      ans[i]='I';
     }
    now=0;
    for(k=n;k>=0;k--)
     {
        shi=(1<<k);
        has=0;
        for(i=1;i<=(1<<k);i++)
        {
            now++;
            has++;
            if(now&1)
            f[now]=now+(1<<(k))-has/2;
            else
            f[now]=now+(1<<(k))-has/2;
        }
     } 
     now=1<<n;
     for(k=n-1;k>=0;k--)
    {
     shi=now;
     has=0;
     for(i=1;i<=(1<<k);i++)
     {
       has++;
       now++;
       ceng[now]=k;
       now1=shi-(1<<(k+1))+has*2-1;
       now2=shi-(1<<(k+1))+has*2;
       if(ans[now1]=='B'&&ans[now2]=='B')
        ans[now]='B';
        else
         {
         if(ans[now1]=='I'&&ans[now2]=='I')
          ans[now]='I';
          else
          ans[now]='F';
        }
     }
    }
   
    now=0;
    for(i=1;i<=(1<<n);i++)
    {
        c=i;b=i;    
        cout<<char(ans[c]);
        zong[ceng[c]]++;
        while(zong[ceng[c]]%2==0)
        {
          b=c;
          c=f[b];
         cout<<char(ans[c]);
          zong[ceng[c]]++;
        }
    }
    return 0;
}

用数组建树，递归遍历。

#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false)
#define what_is(x) cerr << #x << " is " << x << endl
#define rep(i, a, n) for (int i = a; i < n; i++)
#define per(i, a, n) for (int i = n - 1; i >= a; i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int, int> PII;
int s[5000];
int n;
char t[5000];
char check(int lo, int hi) {
    int one = 0;
    rep(i, lo, hi+1)
        if (s[i]) ++one;
    if (one == (hi-lo+1)) return 'I';
    if (one == 0) return 'B';
    return 'F';
}
void probe(int root, int lo, int hi) {
    t[root] = check(lo, hi);
    if (lo == hi) return;
    int mid = (lo+hi)>>1;
    int lc = root<<1|1;
    int rc = lc + 1;
    probe(lc, lo, mid);
    probe(rc, mid+1, hi);
}
void solve(int root) {
    if (t[root] == '\0') return;
    int lc = root<<1|1;
    int rc = lc + 1;
    solve(lc);
    solve(rc);
    printf("%c", t[root]);
}
int main() {
//    freopen("test.in", "r", stdin);
    scanf("%d", &n);
    string input;
    cin >> input;
    rep(i, 0, 1<<n)
        s[i+1] = input[i] - '0';
    probe(0, 1, 1<<n);
    solve(0);
    printf("\n");
}

比较懒，直接用的二分判断输出

#include<iostream>
#include<string>
using namespace std;
string index;
void judge(int _begin,const int _end){
    bool flag1=0,flag2=0;
    do{
        if(index[_begin]=='1'){
            flag1=1;
            if(flag2){
                cout<<'F';
                return;
            }
        }
        else if(index[_begin]=='0'){
            flag2=1;
            if(flag1){
                cout<<'F';
                return;
            }
        }
        _begin++;
    }while(_begin<=_end);
    if(flag1){
        cout<<'I';
    }
    else{
        cout<<'B';
    }
    return;
}
void print(const int begin,const int end){
    if(end==begin){
        judge(begin,end);
    }
    else{
        print(begin,(begin+end)/2);
        print((begin+end)/2+1,end);
        judge(begin,end);
    }
}
int main(void){
    int n;
    cin>>n;
    cin>>index;
    print(0,index.size()-1);
}

一个ansistring加简单的搜索，一遍AC，题目较水。不要抄哦！

var
st:ansistring;
n:integer;
procedure try(n:integer; ss:ansistring);
var
i,j:integer;
s:char;
begin
i:=pos('0',ss);
j:=pos('1',ss);
if i=0 then s:='I' else
if j=0 then s:='B' else
s:='F';
if n>1 then
begin
n:=n div 2;
try(n,copy(ss,1,n));
try(n,copy(ss,n+1,n));
end;
write(s);
end;
begin
readln(n);
n:=1 shl n;
readln(st);
try(n,st);
writeln;
end.

很笨的方法，递归建立树，子树用fbi直接替换，长度到1回溯
大牛勿喷。。。。。。。

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <cstring>

using namespace std;

struct point {
    char data[2000];
    point *rchild, *lchild;
};


void renew(point* &t,char nows1[])
{
    int i, x, y;
    x = 0;
    y = 0;

    int len = strlen(nows1);
    for (i = 0;i <= len;i++)
    {
        if (nows1[i] == '0') ++x;
        if (nows1[i]=='1')++y;
    }
    if (x == len)
    {
        t->data[0] = 'B';
        t->data[1] = '\0';
    }
    else if (y == len)
    {
        t->data[0] = 'I';
        t->data[1] = '\0';
    }
    else
    {
        t->data[0] = 'F';
        t->data[1] = '\0';
    }
    return;
}


void tree(point* &t, char nows[])
{

    int i;
    t = new point;
    int len = strlen(nows);
    for (i = 0;i <= len;i++)
        t->data[i] = nows[i];
    
    
char nows1[2000];
    if (len >1)
    {
        
        len = strlen(t->data);
        for (i = 0;i <= len / 2 - 1;i++)
            nows1[i] = nows[i];
        nows1[i] = '\0';
    
        tree(t->lchild, nows1);
        for (i = len / 2;i <= len - 1;i++)
            nows1[i - len / 2] = nows[i];
        nows1[i - len / 2] = '\0';
        
        tree(t->rchild, nows1);
        renew(t, nows);
    }
    
    if (strlen(t->data) == 1)
    {
        if (t->data[0]=='1' || t->data[0]=='0')
        renew(t,t->data);
        printf("%c", t->data[0]);
        return;
    }
    return;
}


int main()
{
    int n;
    char s[2000];
        scanf("%d", &n);
    scanf("%s", &s);
    point *t;
    t = new point;
    tree(t, s);

    system("pause");
    return 0;
}

//一开始没懂题意, 看了CSDN 某dalao后的递归算法
#include <iostream>         //FBI树
#include <algorithm>
#include <string>
#include <cmath>
using namespace std;

int n;
string str;

void FBI(int left, int right)                   //不建树, 递归算法
{
    if (left > right) return;
    int mid = (left + right) / 2, B = 0, I = 0;
    if (left != right)
    {
        FBI(left, mid);
        FBI(mid + 1, right);
    }
    //printf("%d - %d\n", left, right);         //由left, right之间的01决定FBI
    while (left <= right)
    {
        if (str[left++] == '0')
            B++;
        else
            I++;
    }
    if (B != 0 && I != 0)
        cout << "F";
    else if (I == 0 && B != 0)
        cout << "B";
    else
        cout << "I";
}

int main()
{
    cin >> n >> str;
    FBI(0, (int)pow(2, n) - 1);
    cout << endl;
    system("pause");
    return 0;
}

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int l;
char s[2000];
char b[3000];
void search(int x)
{
if(x<l)
{
search(x*2);
search(x*2+1);
}
cout<<b[x];
}
int main()
{
int n,i;
cin>>n;
cin>>s;
l=strlen(s);
for(i=l;i<l*2;i++)
{
if(s[i-l]=='0')b[i]='B';
else b[i]='I';
}
for(i=l-1;i>=1;i--)
{
if(b[i*2]==b[i*2+1])b[i]=b[i*2];
else b[i]='F';
}
search(1);
return 0;
}

有没有更优美的递归法？
#include<stdio.h>

int n,a[1024],ans[2048],m,i,c;

int fbi(int x)
{
if(x=='I'+'I') return 'I';
if((x==('I'+'B'))||(x=='F'+'I'||x=='F'+'B'||x=='F'+'F')) return 70;
if(x=='B'+'B') return 'B';
}

int answer(int s,int e,int i)
{
if(i==n)
{
c++;
return ans[c-1]=a[s]*('I'-'B')+'B';
}
else
{
int j=fbi(answer(s,s+(e-s)/2,i+1)+answer(s+(e-s)/2,e,i+1));
ans[c]=j;
c++;
return ans[c-1];
}
}

int main()
{
scanf("%d",&n);
m=1;
for(i=0;i<n;i++) m*=2;
getchar();
for(i=0;i<m;i++) a[i]=getchar()-'0';
c=0;
answer(0,m,0);
for(i=0;i<c;i++) printf("%c",ans[i]);
return 0;
}

Var
        k,n,i:longint;
        s,q:ansistring;
Procedure dfs(l,r:longint; t:ansistring);
Begin
        if r<l then
                exit;
        if r-l=0 then
        begin
                if (pos('1',t)>0) and (pos('0',t)>0) then
                        q:=q+'F';
                if (pos('1',t)>0) and (pos('0',t)=0) then
                        q:=q+'I';
                if (pos('0',t)>0) and (pos('1',t)=0) then
                        q:=q+'B';
                exit;
        end;
        dfs(l,(l+r) div 2,copy(s,l,((l+r) div 2)-l+1));
        dfs((l+r) div 2+1,r,copy(s,(l+r) div 2+1,r-((l+r) div 2+1)+1));
        if (pos('1',t)>0) and (pos('0',t)>0) then
                q:=q+'F';
        if (pos('1',t)>0) and (pos('0',t)=0) then
                q:=q+'I';
        if (pos('0',t)>0) and (pos('1',t)=0) then
                q:=q+'B';
End;

Begin
        readln(k);
        n:=1;
        for i:=1 to k do
                n:=n*2;
        readln(s);
        dfs(1,n,s);
        writeln(q);
        readln;
End.

恩。我看了一天的题目终于看懂了。。。。。。。这题目真的拗口啊 。。。。。看不懂题目还以为是啥子高级别的题目。。看懂后，突然感觉自己好蠢。。。。

#include <cstdio>

int a[1200];

struct Tree
{
    char node;
    Tree* lson, *rson;
};

Tree* root;

char buildTree(Tree* &tr, int left, int right)
{
    tr = new Tree;
    if (left == right)
    {
        tr->node = (a[left] == 0 ? 'B' : 'I');
        tr->lson = NULL;
        tr->rson = NULL;
    }
    else
    {
        int mid = (left + right) / 2;
        char ln = buildTree(tr->lson,left,mid);
        char rn = buildTree(tr->rson,mid+1,right);
        if (ln == rn) tr->node = ln;
        else tr->node = 'F';
    }
    return tr->node;
}

void traverse(Tree *tr)//后序遍历
{
    if (tr == NULL) return;
    traverse(tr->lson);
    traverse(tr->rson);
    printf("%c",tr->node);
}



int main()
{
    int n;
    scanf("%d",&n);
    for (int i = 0; i < (1 << n);i++) scanf("%1d",&a[i]);
    buildTree(root,0,(1<<n)-1);
    traverse(root);
}

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
using namespace std;
int tree[3000];
void solve(int n,int i)//后序遍历
{
    if(2*i<n)
      {
       solve(n,2*i);
       solve(n,2*i+1);
      }
    if(tree[i]==-1)
      cout<<"B";
    if(!tree[i])
      cout<<"F";
    if(tree[i]==1)
      cout<<"I";
}
int main()
{
    int n,k,z;
    char s[2000];
    cin>>n;
    scanf("%s",s);
    k=pow(2,n);
    z=k*2-1;
    for(int i=k;i<=z;i++)//先求出叶子
      if(s[i-k]=='0')
        tree[i]=-1;
      else
        tree[i]=1;
    for(int i=k-1;i>0;i--)//判断父亲
      if(tree[2*i+1]*tree[2*i]==1)  
        tree[i]=tree[2*i];
      else
        tree[i]=0;
    solve(z,1);
    return 0;
}

#include<cstdio>
int x[2333],y;char s[6666];
char _get(int l,int r)
{int t=0;for(int i=l;i<=r;++i)t+=x[i];if(t==0)return 'B';if(t==r-l+1)return 'I';return 'F';}
void build(int c,int l,int r)
{s[c]=_get(l,r);int mid=(l+r)/2;if(l!=r)build(c*2,l,mid),build(c*2+1,mid+1,r);}
void work(int c){if(c<y)work(c*2),work(c*2+1);putchar(s[c]);}
int main()
{
    int n;scanf("%d",&n);y=1<<n;
    for(int i=1;i<=y;++i)scanf("%1d",&x[i]);
    build(1,1,y);work(1);
}

#include<cstdio>

using namespace::std;
    int l[5010];
    int n;
    int m[12]={1,2,4,8,16,32,64,128,256,512,1024,2048};
int SCECS(int i)//form i=n to start
{
    for(int j=m[i-1];j<m[i];j++){
            if(l[j*2]==l[j*2+1]){
                l[j]=l[j*2];
            }
            if(l[j*2]==2){
                l[j]=2;
            }
            if(l[j*2+1]==2){
                l[j]=2;
            }
            if(l[j*2+1]!=l[j*2]){
                l[j]=2;
            }
    }
    if(i>1){
        SCECS(i-1);
    }
}

int HXBL(int i){//from i=1 to start
    if(i>m[n]){
        if(l[i]==1){
            printf("I");
        }
        else if(l[i]==0){
            printf("B");
        }
        else if(l[i]==2){
            printf("F");
        }
    }
    else{
        HXBL(i*2);
        HXBL(i*2+1);
        if(l[i]==1){
            printf("I");
        }
        else if(l[i]==0){
            printf("B");
        }
        else if(l[i]==2){
            printf("F");
        }
    }
}

int main()
{
    for(int i=0;i<=5009;i++){
        l[i]=-1;
    }
    char pp[1025];
    scanf("%d",&n);
    scanf("%s",pp+1);
    for(int i=1;i<=m[n];i++){
        l[m[n]+i-1]=pp[i]-'0';
    }
    SCECS(n);
    HXBL(1);
    return 0;
}

#include<iostream>
#include<iomanip>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
using namespace std;

int n,a[1050],m=1;

void work(int r,int l){
    int mid=(r+l)/2;
    if(r==l){
        if(a[r]==0){
            cout<<"B";
        }
        else
            cout<<"I";
    }
    else{
        work(r,mid);
        work(mid+1,l);
        bool t=false;
        for(int i=r+1;i<=l;i++){
            if(a[r]!=a[i]){
                t=true;
                cout<<"F";
                break;
            }
        }
        if(t==false){
            if(a[r]==0)
                cout<<"B";
            else
                cout<<"I";
        }
    }
}
int main(){
    cin>>n;
    getchar();
    for(int i=0;i<n;i++)
        m*=2;
    for(int i=1;i<=m;i++){
        char c;
        c=getchar();
        a[i]=c-'0';
    }
    work(1,m);
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
int n,t=0;
char a;
char dis[1026][1026],c[1026];
void search(int head,int tail)
{
    t++;c[t]=dis[head][tail];
    int lth=(tail-head+1)/2;
    if(head<tail)search(tail-lth+1,tail);
    if(head<tail)search(head,tail-lth);
}
int main()
{
    cin>>n;
    n=pow(2,n);
    for(int i=1;i<=n;i++)
    {
        cin>>a;
        if(a=='0')dis[i][i]='B';
        if(a=='1')dis[i][i]='I';
    }
    for(int i=1;i<=n-1;i++)
    {
        for(int j=i+1;j<=n;j++)
        {
            if(dis[i][j-1]=='B')
            {
                if(dis[j][j]=='B')dis[i][j]='B';if(dis[j][j]=='I')dis[i][j]='F';
            }
            if(dis[i][j-1]=='I')
            {
                if(dis[j][j]=='B')dis[i][j]='F';if(dis[j][j]=='I')dis[i][j]='I';
            }
            if(dis[i][j-1]=='F')dis[i][j]='F';
        }
    }
    t=1;search(1,n);
    for(int i=t;i>=1;i--)cout<<c[i];cout<<endl;
}

###code
c++
#include <algorithm>
#include <iostream>
#include <string>
using namespace std;
string str;
int n;
inline void dfs(int L,int R) {
if (L == R) { //走到叶节点
if (str[L] == '0') cout << 'B';
else cout << 'I';
return; //结束
}
int mid = (L+R)/2; //取中间值
dfs(L,mid); //左儿子
dfs(mid+1,R); //右儿子
bool zero = false,one = false;
for (int i = L;i <= R;i++)
if (str[i] == '1') one = true;
else if (str[i] == '0') zero = true;
if (one && zero) cout << 'F'; //既有0又有1
else if (one && !zero) cout << 'I'; //全1
else cout << 'B'; //全0
}
int main() {
ios :: sync_with_stdio(false);
cin >> n >> str;
dfs(0,str.length()-1); //后序遍历
return 0;
}