题解：P1087 [NOIP 2004 普及组] FBI 树

· · 题解

这题理论上来说是考二叉树的，但是呢，当时我做这道题的时候刚刚学完线段树，于是......

小知识：线段树的递归建树过程就是一个后序遍历，所以我们可以直接用线段树的建树函数改造得到这道题的答案。

具体的，我们将整个串输入，之后像线段树递归那样，在这个 01 串上建树，建好之后，按照题意合并两个子节点的对应串：

  1. 对于叶子节点，若是 0 就为 B 串，反之为 I 串。
  2. B+B=B,I+I=I,B+I=F,I+B=F,F+(B/I/F)=F

按照上面的小知识，当求出每一个节点对应的类型时，直接输出，最终得到的就是答案。

上代码：

#include<bits/stdc++.h>
using namespace std;
const int N=10050;
char sgt[N]={0};
void build(int tt,string s)
{
    if(s.size()==1)
    {
        if(s[0]=='0')sgt[tt]='B';
        else sgt[tt]='I';
        cout<<sgt[tt];
        return ;
    }
    int mid=s.size()/2;
    build(tt*2,s.substr(0,mid));
    build(tt*2+1,s.substr(mid,mid));
    if(sgt[tt*2]=='I'&&sgt[tt*2+1]=='I')sgt[tt]='I';
    else if(sgt[tt*2]=='B'&&sgt[tt*2+1]=='B')sgt[tt]='B';
    else sgt[tt]='F';
    cout<<sgt[tt];
    return ;
}
int main()
{
    int n;
    string s;
    cin>>n;
    cin>>s;
    build(1,s);
    return 0;
}