首页 > 代码库 > RNQOJ 21 FBI数

RNQOJ 21 FBI数

如果字符串全是0输出B,全是1输出I,01混合输出F,如果字符串分解到只剩下一个字符的时候我们可以很简单的判断出来是B串还是I串,如果处在父节点的位置,这里运用递归,通过子节点的返回值来判断子节点是混合还是单一的字符串,这里我用的是,如果全是0,return 0,全是1,return1,这样就可以在父节点进行判断,如果左右子节点的和是0或者2,当前字符串就是单一字符串(即B或I),否则就是F/

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
string s;
int FBI(int be,int en)
{
    if(be==en)
    {
        if(s[be]==0)
        {
            cout<<"B";
            return 0;
        }
        if(s[be]==1)
        {
            cout<<"I";
            return 1;
        }
    }
    int mid=(be+en)>>1;
    int lchild=FBI(be,mid);
    int rchild=FBI(mid+1,en);
    if(lchild+rchild==0)
     {
            cout<<"B";
            return 0;
     }
    else if(lchild+rchild==2)
      {
            cout<<"I";
            return 1;
      }
    else
       {
            cout<<"F";
            return 3;
       }
}
int main()
{
  int n;

  while(cin>>n)
  {
      cin>>s;
      int len=1<<n;
      FBI(0,len-1);
      cout<<endl;
  }
    return 0;
}

 

RNQOJ 21 FBI数