题解 P1087 【FBI树】

wuhao1027 · 2017-05-24 08:41:21 · 题解

递归即可。跟二分查找的思想有点像。想起以前学长跟我说的，很多树的题目事实上根本不用把树建立出来，虽然当时觉得这个思想很惊奇(marvel)，但现在自己也算真正的理解了这句话了。

在输入一长串的时候，写 A+1 就能从 A[1] 开始输入了，这很贴合人的语言习惯，但问题是这样就不能使用 strlen 了，所以使用了 math 来计算 2 的 n 次

#include<stdio.h>
#include<math.h>
char A[1025];
void work(int low, int up)
{
    int mid = (low+up)/2;
    if (low!=up){
        work(low, mid);
        work(mid+1,up);
    }
    int i,a=0,b=0;
    for (i=low;i<=up;i++)
        if (A[i]=='0') a++;
        else b++;
    if (a&&b) printf("F");
    else if (a) printf("B");
    else printf("I");
}
int main()
{
    int n;
    scanf("%d", &n);
    scanf("%s", A+1);
    work(1, pow(2,n));
    return 0;
}