SDNU 1168.FBI樹【NOIP 2004 普及組】【不建樹】【7月28】

FBI樹

解題的思路不止一種，或許還有更優的解。靈感就在一瞬間

Description

我們可以把由“0”和“1”組成的字元串分為三類：全“0”串稱為B串，全“1”串稱為I串，既含“0”又含“1”的串則稱為F串。

FBI樹是一種二叉樹[1]，它的結點類型也包括F結點，B結點和I結點三種。由一個長度為2N的“01”串S可以構造出一棵FBI樹T，遞歸的構造方法如下：

1)      T的根結點為R，其類型與串S的類型相同；

2)      若串S的長度大于1，将串S從中間分開，分為等長的左右子串S1和S2；由左子串S1構造R的左子樹T1，由右子串S2構造R的右子樹T2。

現在給定一個長度為2N的“01”串，請用上述構造方法構造出一棵FBI樹，并輸出它的後序周遊[2]序列。

Input

輸入檔案fbi.in的第一行是一個整數N（0 <= N <= 10），第二行是一個長度為2N的“01”串。

Output

輸出檔案fbi.out包括一行，這一行隻包含一個字元串，即FBI樹的後序周遊序列。

Sample Input

3
10001011      

Sample Output

IBFBBBFIBFIIIFF      

這道題是我思考了一段時間才做的。看過YG跟WYC的思路，都是建樹之後再後序周遊，我就在想，可不可以不建樹，因為本身建樹的一個過程就是周遊的過程，隻是周遊的順序不一樣。後來發現，完全可以用遞歸實作的。對于一組資料字元串s的周遊順序是這樣的：s[0]->s[1]->s[0]+[s1]->s[2]->s[3]->s[2]+s[3]->s[0]+s[1]+s[2]+s[3]......代碼如下：

#include<cstdio>
#include<cstring>
char s[1100];
int FBI(int start,int len){//兩個變量，start起始位置，len長度
    if(len==1){
        if(s[start]=='0'){
            printf("B");
            return 0;
        }
        else{
            printf("I");
            return 1;
        }
    }
    else{//傳回0說明全為0，傳回1說明全為1，否則傳回2
        int x=FBI(start,len/2);
        int y=FBI(start+len/2,len/2);
        if(x==y&&x==0){
            printf("B");
            return 0;
        }
        else if(x==y&&x==1){
            printf("I");
            return 1;
        }
        else{
            printf("F");
            return 2;
        }
    }
}
int main(){
    int n;//其實這樣做，n是一個無用的變量
    scanf("%d%s",&n,s);
    int l=strlen(s);
    FBI(0,l);
    printf("\n");
    return 0;
}