/ Vijos / 题库 / FBI树 /

题解

157 条题解

  • 2
    @ 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;
    }

  • 2
    @ 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;
    }

  • 1
    @ 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)))
    
    
  • 1
    @ 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;
    }
    
    
  • 1
    @ 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;
    }
    
  • 1
    @ 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");
    }
    
  • 1
    @ 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);
    }
    
  • 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
    readln(n);
    n:=1 shl n;
    readln(st);
    try(n,st);
    writeln;
    end.

  • 1
    @ 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;
    }
    
    
  • 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;
    }
    
  • 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;
    }

  • 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';
    }

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

  • 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
            readln(k);
            n:=1;
            for i:=1 to k do
                    n:=n*2;
            readln(s);
            dfs(1,n,s);
            writeln(q);
            readln;
    End.
    

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

  • 0
    @ 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);
    }
    
  • 0
    @ 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;
    }
    
  • 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);
    }
    
  • 0
    @ 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;
    }
    
    
  • 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;
    }
    
  • 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];
    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;
    }
    
  • 0
    @ 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
分类
数据结构 | 点击显示
标签
递交数
4018
已通过
2155
通过率
54%
被复制
7
上传者