/ Vijos / 题库 / FBI树 /

# 157 条题解

• @ 2017-09-03 21:46:15

#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;
}

• @ 2017-08-20 22:16:38

#不知为啥代码都那么长~~~~
```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; } ```

• @ 2020-05-02 11:40:21

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)))

``````
• @ 2019-02-13 16:48:55

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

``````#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;
}

``````
• @ 2017-11-01 15:46:47

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

``````#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;
}
``````
• @ 2017-09-10 15:44:25

用数组建树，递归遍历。

``````#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");
}
``````
• @ 2017-07-03 16:14:54

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

``````#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);
}
``````
• @ 2017-07-02 17:40:43

一个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
n:=1 shl n;
try(n,st);
writeln;
end.

• @ 2017-02-14 20:00:36

很笨的方法，递归建立树，子树用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;
}

``````
• @ 2020-03-06 16:19:59
``````//一开始没懂题意, 看了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;
}
``````
• @ 2018-06-11 14:20:37

#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;
}

• @ 2017-10-21 21:54:04

有没有更优美的递归法？
#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';
}

{
if(i==n)
{
c++;
return ans[c-1]=a[s]*('I'-'B')+'B';
}
else
{
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;
for(i=0;i<c;i++) printf("%c",ans[i]);
return 0;
}

• @ 2017-08-26 20:51:22
``````
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
n:=1;
for i:=1 to k do
n:=n*2;
dfs(1,n,s);
writeln(q);
End.
``````

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

• @ 2017-04-08 11:03:14
``````#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);
}
``````
• @ 2016-12-28 12:33:27
``````#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;
}
``````
• @ 2016-11-04 20:35:23
``````#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);
}
``````
• @ 2016-10-09 21:46:01
``````
#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;
}

``````
• @ 2016-10-08 15:20:52
``````#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;
}
``````
• @ 2016-09-28 13:20:44
``````#include<bits/stdc++.h>
using namespace std;
int n,t=0;
char a;
char dis[1026][1026],c[1026];
{
}
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;
}
``````
• @ 2016-08-28 15:35:56

###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; } ```

ID
1114

3

4154

2218

53%

26