信息
- ID
- 584
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- 3
- 标签
- (无)
- 递交数
- 28
- 已通过
- 20
- 上传者
#include <bits/stdc++.h>
using namespace std;
int n;
string s;
// 把长度为 2^n 的串 s[l]~s[r] 对应的 FBI 树的后序遍历输出
char f(int l, int r, int n)
{
char now_res;
if (n == 0)
{
if (s[l] == '0')
now_res = 'B';
if (s[l] == '1')
now_res = 'I';
cout << now_res;
return now_res;
}
int len = (1 << n);
char left_res = f(l, l + len / 2 - 1, n - 1);
char right_res = f(l + len / 2, r, n - 1);
if (left_res == right_res && left_res == 'B')
now_res = 'B';
else if (left_res == right_res && left_res == 'I')
now_res = 'I';
else
now_res = 'F';
cout << now_res;
return now_res;
}
int main()
{
cin >> n;
cin >> s;
f(0, s.size() - 1, n);
return 0;
}
#include <bits/stdc++.h>
using namespace std;
int n;
string s;
// 把长度为 2^n 的串 s[l]~s[r] 对应的 FBI 树的后序遍历输出
void f(int l, int r, int n)
{
if (n > 0) //有左右子树
{
int len = r - l + 1;
f(l, l + len / 2 - 1, n - 1); //输出左子树的后序遍历
f(r - len / 2 + 1, r, n - 1); //输出右子树的后序遍历
}
bool one, zero; //是否有 1 与 0
one = false, zero = false;
for (int i = l; i <= r; i++)
{
if (s[i] == '1')
one = true;
else if (s[i] == '0')
zero = true;
}
//输出根节点对应的类型
if (one == false)
cout << 'B';
else if (zero == false)
cout << 'I';
else
cout << 'F';
}
int main()
{
cin >> n;
cin >> s;
f(0, s.size() - 1, n);
return 0;
}