P1087 FBI树题解：
看到这个题，我想到了线段树！（毕竟刚搞完st表。。。）
当然，题解中有位大佬也用的线段树，但是当时看的时候我看见了9个if，当场去世。
那么这是一个不用暴力的线段树，且简单易懂。
（所以我认为我的方法还是可以供大家参考的。求过。。。。。。）
正解：
根据题意中“将串S从中间分开，分为等长的左右子串S1和S2” 和现在给定一个长度为2^n的“01”串可知：给定字符串一定位诸如16,8,4,2,1之类的二的指数幂，并且一定满足可以被均分n次，因为原字符串长度就是2^n的， 那么，我们可以建树如下：
F 长度为8
F F 长度为4
F B F I 长度为2
I B B B I B I I长度为1
| | | | | | | |
| | | | | | | |
1 0 0 0 1 0 1 1
是不是特别像线段树QWQ
这里我们要用到一个法则:
1，如果其两个子串同为‘I’或者同为‘B’，那么两个子串合二为一后也为对应的‘I’或者‘B’。
2，子串中只要有一个为‘F’，那么他们合起来组成的字符串一定为‘F’。
证明：利用了题目中的性质：全“0”串称为B串，全“1”串称为I串，既含“0”又含“1”的串则称为F串。 也就是说两个子串中只要都是‘B’或者‘F’的话，他们合起来一定也只有一种字符‘0’或者‘1’，但是子串中只要有一个为‘F’，那么他们合起来一定即含有1也含有0，那么他一定是一个01串，就是‘F’。证毕。
然后再按照后序遍历，即可得到答案：
IBFBBBFIBFIIIFF
AC代码如下：
#include<cstdio>
#include<cstring>
using namespace std;
int n,zero=0,one=0,lenb;
char b[1025];
char dis[1025][12];
inline void chuli()
{
for(int i=0;i<lenb;i++)
{
if(b[i]=='1')dis[i][0]='I';
if(b[i]=='0')dis[i][0]='B';//底层初始化
}
for(int j=1;j<=n;j++)
for(int i=0;i+(1<<j)-1<lenb;i+=(1<<j))
{
if(dis[i][j-1]=='B'&&dis[i+(1<<(j-1))][j-1]=='B')
dis[i][j]='B';//只要满足左右子树都为‘F’或者‘B’，他们合起来就是‘B’或‘F’
else
if(dis[i][j-1]=='I'&&dis[i+(1<<(j-1))][j-1]=='I')
dis[i][j]='I';//只要满足左右子树都为‘F’或者‘B’，他们合起来就是‘B’或‘F’
else dis[i][j]='F';//否则，其他情况都是F
}
}
inline void print(int i,int n)
{
if(n>0)
{
print(i,n-1);//左子树
print(i+(1<<(n-1)),n-1);//右子树
}
printf("%c",dis[i][n]);//输出当前节点
}
int main(){
freopen("fbi.in","r",stdin);
freopen("fbi.out","w",stdout);
scanf("%d",&n);
scanf("%s",b);
lenb=strlen(b);
chuli();//可以说是很形象了
print(0,n);//后序遍历并输出
return 0;
}
完结QWQ
本蒟蒻真心希望能帮助到各位大佬