P1087 [NOIP 2004 普及组] FBI 树——题解

解题思路

递归处理字符串区间。若区间长度大于 1，先处理左半区间，再处理右半区间；最后根据当前区间中是否出现过 0 和 1 输出 B、I 或 F。这个顺序恰好是后序遍历。

复杂度分析

共有 $2^{N+1}-1$ 个递归结点。直接扫描区间判型的实现最坏约 $O(N2^N)$，在 $N\le10$ 时非常充足；递归空间 $O(N)$。

C++17 参考代码

#include <bits/stdc++.h>
using namespace std;
string s;
char kind(int l,int r){
    bool z=false,o=false;
    for(int i=l;i<=r;i++) (s[i]=='0'?z:o)=true;
    if(z&&o) return 'F';
    return z?'B':'I';
}
void dfs(int l,int r){
    if(l<r){
        int mid=(l+r)/2;
        dfs(l,mid); dfs(mid+1,r);
    }
    cout<<kind(l,r);
}
int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n; cin>>n>>s;
    dfs(0,(int)s.size()-1);
    return 0;
}

#include <bits/stdc++.h> using namespace std; string s; char kind(int l,int r){ bool z=false,o=false; for(int i=l;i<=r;i++) (s[i]=='0'?z:o)=true; if(z&&o) return 'F'; return z?'B':'I'; } void dfs(int l,int r){ if(l<r){ int mid=(l+r)/2; dfs(l,mid); dfs(mid+1,r); } cout<<kind(l,r); } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin>>n>>s; dfs(0,(int)s.size()-1); return 0; }