题解 P1087 【FBI树】

· · 题解

这道题说白了就是一道求后序遍历的题。

这道题含有分治与搜索还有二分的思想。

我们只要只要把一个字符串分成俩段相同的就可以了。

举个例子吧

10001101

第一步，平均分成2分

1000 1101

分成4分

10 00 11 01

分成8份

1 0 0 0 1 1 0 1

所以可以构成一棵树

10001101

1000 1101

10 00 11 01

1 0 0 0 1 1 0 1

var
a:longint;
x:ansistring;
function pd(x:ansistring):char;        ////判断当前字符串是‘I’ 还是 ‘B' 还是 ’F'
var
i:longint;
t,f:boolean;
begin
  t:=false; f:=false;          
  for i:=1 to length(x) do
  begin
    if x[i]='1' then t:=true;
    if x[i]='0' then f:=true;
  end;
  if (t) and (f) then exit('F');       如果1和0都出现过，则‘F'
  if t then exit('I');
  if f then exit('B');
end;
procedure fz(x:ansistring);
begin
  if length(x)<>1 then         //  当长度只有一时直接输出，无须再分治
  begin
    fz(copy(x,1,length(x) div 2));       // 左子树
    fz(copy(x,length(x) div 2+1,length(x) div 2));     //右子树
  end;
  write(pd(x));         // 由于是后序遍历，所以根最后输出
end;
begin
  readln(a);
  readln(x);
  fz(x);
end.