noip2004 FBI樹 （樹的後序周遊）

A1149. FBI樹 時間限制： 1.0s   記憶體限制： 256.0MB   總送出次數： 582   AC次數： 286   平均分： 63.64 将本題分享到：             檢視未格式化的試題    送出    試題讨論 試題來源 　　NOIP2004 普及組 問題描述 　　我們可以把由“0”和“1”組成的字元串分為三類：全“0”串稱為B串，全“1”串稱為I串，既含“0”又含“1”的串則稱為F串。

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

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

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

　　現在給定一個長度為2 N的“01”串，請用上述構造方法構造出一棵FBI樹，并輸出它的後序周遊序列。 輸入格式 　　第一行是一個整數N（0 <= N <= 10），第二行是一個長度為2 N的“01”串。 輸出格式 　　包括一行，這一行隻包含一個字元串，即FBI樹的後序周遊序列。 樣例輸入 3

10001011 樣例輸出 IBFBBBFIBFIIIFF 資料規模和約定 　　對于40%的資料，N <= 2；

　　對于全部的資料，N <= 10。

　　注：

　　[1] 二叉樹：二叉樹是結點的有限集合，這個集合或為空集，或由一個根結點和兩棵不相交的二叉樹組成。這兩棵不相交的二叉樹分别稱為這個根結點的左子樹和右子樹。

　　[2] 後序周遊：後序周遊是深度優先周遊二叉樹的一種方法，它的遞歸定義是：先後序周遊左子樹，再後序周遊右子樹，最後通路根。

解析：write(l,r) 輸出區間（l，r）所代表的 FBI 樹，先輸出左子區間，再輸出右子區間，最後輸出根。 代碼：

#include<cstdio>
#include<cstring>

const int maxn=(1<<10);
char s[maxn+20];

int write(int l,int r)
{
  if(l==r)
    {
      printf("%c",(s[l]=='0')?'B':'I');
      return s[l]=='1';
	}
  int sl,sr,k=(l+r)/2;
  sl=write(l,k),sr=write(k+1,r);
  if(sl+sr==0){printf("B");return 0;}
  if(sl+sr==2){printf("I");return 1;}
  printf("F");  return 3;
}

int main()
{
  scanf("%s%s",s,s);
  write(0,strlen(s)-1);
  return 0;
}