P1087 [noip2004 popularity group question 3] FBI tree

Title source

https://www.luogu.com.cn/problem/P1087
https://www.acwing.com/problem/content/description/421/

Title Description

We can turn the “$0$” and “$1$” There are three types of strings ： whole “$0$” The string is called $B$ strand , whole “$1$” The string is called $I$ strand , Both contain “$0$” It also includes “$1$” The string of is called $F$ strand .

$FBI$ A tree is a binary tree , Its node types also include $F$ node ,$B$ Node sum $I$ There are three kinds of nodes . By a length of $2^N$ Of “$01$” strand S You can build a tree $FBI$ Trees $T$, The construction of recursion is as follows ：

1. $T$ The root node of is $R$, Its type and string $S$ Same type of ;
2. Ruoshan $S$ Is longer than $1$, String $S$ Separate from the middle , It is divided into equal length left and right substrings $S_1$ and $S_2$; From left sub string $S_1$ structure R The left subtree $T_1$, From the right sub string $S_2$ structure $R$ The right subtree $T_2$.

Now let's give a length of $2^N$ Of “$01$” strand , Please construct a $FBI$ Trees , And output its post order traversal sequence .

Input format

The first line is an integer $N(0\le N\le 10)$,

The second line is a length of $2^N$ Of “$01$” strand .

Output format

A string , namely $FBI$ The subsequent traversal sequence of the tree .

The sample input #1

3
10001011

Sample output #1

IBFBBBFIBFIIIFF

Tips

about 40% The data of ,$N\le 2$;

For all the data ,$N\le 10$.

Algorithm code 1

Algorithm code 1 comes from ：https://www.acwing.com/solution/content/5497/

#include <bits/stdc++.h>
using namespace std;

void dfs(string str) {
    
	if(str.size()>1) {
    
		dfs(str.substr(0,str.size()/2));
		dfs(str.substr(str.size()/2));
	}

	int one=0, zero=0;
	for(int i=0; i<str.size(); i++)
		if(str[i]=='0') zero++;
		else one++;

	if(one && zero) cout<<'F';
	else if(one) cout<<'I';
	else cout<<'B';
}

int main() {
    
	int n;
	string str;
	cin>>n>>str;

	dfs(str);

	return 0;
}

/* in: 3 10001011 out: IBFBBBFIBFIIIFF */

In order to understand this code , Need to understand functions in depth substr() Usage of . As shown below .

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    
	string s="abcdef";
	string a=s.substr(0,s.size()/2); // From the subscript 0 Start to output s.size()/2 Characters 
	string b=s.substr(s.size()/2);   // From the subscript s.size()/2 Start outputting all characters 
	string c=s.substr(2,s.size()/2); // From the subscript 2 Start to output s.size()/2 Characters  
	cout<<s.size()/2<<endl;  //3
	cout<<a<<" "<<b<<endl;   //abc def
	cout<<c<<" "<<b<<endl;   //cde def
	
	return 0;
}

Of course , If this question is changed to require the output of medium order $FBI$ Trees , Then the code is slightly adjusted as follows ：

#include <bits/stdc++.h>
using namespace std;

void dfs(string str) {
    
	if(str.size()>1) {
    
		dfs(str.substr(0,str.size()/2));
	}

	int one=0, zero=0;
	for(int i=0; i<str.size(); i++)
		if(str[i]=='0') zero++;
		else one++;
	if(one && zero) cout<<'F';
	else if(one) cout<<'I';
	else cout<<'B';

	if(str.size()>1) {
    
		dfs(str.substr(str.size()/2));
	}
}

int main() {
    
	int n;
	string str;
	cin>>n>>str;

	dfs(str);

	return 0;
}

/* in: 3 10001011 out: IFBFBBBFIFBFIII */

Accordingly , If this question is changed to require the output of the first order $FBI$ Trees , Then the code is slightly adjusted as follows ：

#include <bits/stdc++.h>
using namespace std;

void dfs(string str) {
    
	int one=0, zero=0;
	for(int i=0; i<str.size(); i++)
		if(str[i]=='0') zero++;
		else one++;

	if(one && zero) cout<<'F';
	else if(one) cout<<'I';
	else cout<<'B';

	if(str.size()>1) {
    
		dfs(str.substr(0,str.size()/2));
		dfs(str.substr(str.size()/2));
	}
}

int main() {
    
	int n;
	string str;
	cin>>n>>str;

	dfs(str);

	return 0;
}

/* in: 3 10001011 out: FFFIBBBBFFIBIII */

Algorithm code 2

#include <bits/stdc++.h>
using namespace std;

const int maxn=1050;
char s[maxn];
int n;

void create(int x,int y) {
    
	if(y>x) {
    
		create(x,(x+y)/2);
		create((x+y+1)/2,y);
	}
	
	int B=1,I=1;
	for(int i=0; i<=y-x; i++) {
    
		if(s[x+i]=='1')
			B=0;
		else if(s[x+i]=='0')
			I=0;
	}
	
	if(B)
		cout<<'B';
	else if(I)
		cout<<'I';
	else
		cout<<'F';
}

int main() {
    
	cin>>n>>s;
	create(0,(1<<n)-1);

	return 0;
}

/* in: 3 10001011 out: IBFBBBFIBFIIIFF */

reference

https://blog.csdn.net/weixin_44170305/article/details/109568533
https://www.acwing.com/solution/content/5497/