51 nod 算法马拉松28 先序遍历与后序遍历

​​先序遍历与后序遍历​​ 

​​​Scape​​​  (命题人)

​​​tangjz​​​  (测试)

基准时间限制：1 秒 空间限制：131072 KB 分值: 40

对于给定的一个二叉树的先序遍历和后序遍历，输出有多少种满足条件的二叉树。

两棵二叉树不同当且仅当对于某个x，x的左儿子编号不同或x的右儿子编号不同。

Input

第一行一个正整数n(3<=n<=10000)，表示二叉树的节点数，节点从1到n标号。
第二行n个整数a[i](1<=a[i]<=n)，表示二叉树的先序遍历。
第三行n个整数b[i](1<=b[i]<=n)，表示二叉树的后序遍历。

Output

输出一个整数表示有多少种方案。保证至少有1种方案。

Input示例

3
1 2 3
2 3 1

Output示例

1

这道题比较简单，按照先序遍历和后序遍历大概将一棵树构建出来。从根节点开始遍历，当一个节点只有一个儿子时，方案数乘2。

var
  n,i,max,lans,j,x:longint;
  a,b,ans:array[1..10000] of longint;
  son:array[1..10000,1..2] of longint;
procedure dfs(la,ra,lb,rb,k:longint);
var i:longint;
begin
  if rb=0 then exit;
  if a[la]=b[rb] then
  begin
    if son[k,1]=0 then son[k,1]:=a[la] else son[k,2]:=a[la];
    dfs(la+1,ra,lb,rb-1,la);
    exit;
  end;
  for i:=rb downto lb do
    if b[i]=a[la] then
    begin
      dfs(la,ra-rb+i,lb,i,k);
      dfs(ra-rb+i+1,ra,i+1,rb,k);
      break;
    end;
end;
begin
  ans[1]:=1;lans:=1;
  readln(n);
  for i:=1 to n do read(a[i]);
  for i:=1 to n do read(b[i]);
  dfs(2,n,1,n-1,1);
  for i:=1 to n do
    begin
      if (son[i,1]<>0)and(son[i,2]<>0) then continue;
      if (son[i,1]=0)and(son[i,2]=0) then continue;
      x:=0;
      for j:=1 to lans do
      begin
        ans[j]:=ans[j]*2+x;
        if ans[j]>=10 then
        begin
          x:=ans[j] div 10;
          ans[j]:=ans[j] mod 10;
        end else x:=0;
      end;
      if x>0 then
      begin
        inc(lans);
        ans[lans]:=x;
      end;
    end;
  for i:=lans downto 1 do write(ans[i]);
end.