44 lines
1.1 KiB
C++
44 lines
1.1 KiB
C++
#include <bits/stdc++.h>
|
||
|
||
using namespace std;
|
||
const int N = 1e5 + 10;
|
||
|
||
int n, m;
|
||
string s; //2^n长度的01串
|
||
|
||
/**
|
||
* 功能：获取字符串s的类型
|
||
* @param s
|
||
* @return
|
||
*/
|
||
char getStype(string s) {
|
||
int c0 = 0, c1 = 0;
|
||
for (int i = 0; i < s.size(); i++) if (s[i] == '1') c1++; else c0++;
|
||
if (c1 == 0)return 'B';
|
||
else if (c0 == 0) return 'I';
|
||
return 'F';
|
||
}
|
||
|
||
/**
|
||
* 功能：构建FBI树
|
||
* @param start 开始的位置
|
||
* @param end 结束的位置
|
||
*/
|
||
void dfs(string s) {
|
||
if (s.length() > 1) {
|
||
//左树
|
||
dfs(s.substr(0, s.length() / 2));//从哪个位置开始，截取多少个
|
||
//右树
|
||
dfs(s.substr(s.length() / 2));//从哪个位置开始，不说截取多少个就是截取到尾
|
||
}
|
||
cout << getStype(s);//后序遍历
|
||
}
|
||
|
||
|
||
int main() {
|
||
//这个n是无用的，因为是上古的考题，都是C时代的，要求使用char数组，没有n说不过去，现在都用string了，不需要n了。
|
||
cin >> n >> s;
|
||
//利用递归构建FBI树
|
||
dfs(s);
|
||
return 0;
|
||
} |