CSP历年复赛题-P1087 [NOIP2004 普及组] FBI 树

原题链接：https://www.luogu.com.cn/problem/P1087

题意解读：字符串作为根，左边一半作为左子树，右边一半作为右子树，递归构造数，并按FBI规则输出后续遍历结果。

解题思路：

按照题意，通过dfs来构造树，对于字符串str，提取左边一半递归构造左子树，提取右边一半递归构造右子树，前提是字符串长度>1

输出根的位置在左、右子树dfs之后，即为后续遍历。

根据字符串的提取方法，有两种程序实现，一种是对string进行处理，一种是直接通过下标来变换，下面给出两种代码：

string str1 = "123456";

string str2(str1, 0, 3); //str2 = "123"，表示从第0个开始3个字符

string str3(str1, 3); //str3 = "456"，表示从第3个开始直到最后所有字符

100分代码-string处理：

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

void print(string str)
{
    int sum = 0;
    for(int i = 0; i < str.size(); i++) sum += str[i] - '0';
    if(sum == 0) cout << "B";
    else if(sum == str.size()) cout << "I";
    else cout << "F";
}

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

int main()
{
    int n;
    string s;
    cin >> n >> s;
    dfs(s);
    return 0;
}

100分代码-下标变换：

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

int n;
string s;

void print(int l, int r)
{
    int sum = 0;
    for(int i = l; i <= r; i++) sum += s[i] - '0';
    if(sum == 0) cout << "B";
    else if(sum == r - l + 1) cout << "I";
    else cout << "F";
}

void dfs(int l, int r)
{
    if(r - l + 1 > 1)
    {
        dfs(l, l + (r - l + 1) / 2 - 1);
        dfs(l + (r - l + 1) / 2, r);
    }
    print(l, r);
}

int main()
{
    cin >> n >> s;
    dfs(0, s.size() - 1);
    return 0;
}