看到这个题，我想到了线段树！（毕竟刚搞完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

本蒟蒻真心希望能帮助到各位大佬