apio2007 mobiles

一芥书生 — Sat, 24 Apr 2010 08:30:00 GMT

额，这题其实挺简单，练手了。
题目大意：
给你一棵树，问这棵树能否经过调整后变成完全二叉树。
这棵二叉树满足叶子节点的深度差<=1。
解法：
首先，先遍历一遍这棵树，保留d[i]表示第i号节点到顶点的距离，s[i,1..2]表示i节点左右儿子的叶子节点总数，h[i,1..2]表示i节点左右儿子节点的最深深度。
好了，那么如果某个节点左右儿子节点的深度差大于1那么肯定无解。
如果某一层的最后儿子深度差等于1的节点数>1那么肯定无解。
很显然的吧。
然后就是调整，按先序遍历，s[i,1] 很简单吧，程序86行：

{$M 10000000}
program mobiles;
var f,d:array[-1..100001] of longint;
     son,h,s:array[-1..100001,1..2] of longint;
     sum:array[0..100] of longint;
     n,num:longint;
{---------------------------------------------------}
procedure init;
  var i,p,q:longint;
  begin
   readln(n);
   for i:=1 to n do
    begin
     readln(p,q);
     if p<>-1 then f[p]:=i; son[i,1]:=p;
     if q<>-1 then f[q]:=i; son[i,2]:=q;
    end;
  end;
{---------------------------------------------------}
function max(x,y:longint):longint;
  begin
   if x>y then exit(x);
   exit(y);
  end;
{---------------------------------------------------}
function min(x,y:longint):longint;
  begin
   if x<y then exit(x);
   exit(y);
  end;
{---------------------------------------------------}
procedure dfs(x:longint);
  var i:longint;
  begin
   d[x]:=d[f[x]]+1;
   for i:=1 to 2 do
   if son[x,i]=-1 then begin
    h[x,i]:=1;s[x,i]:=1; end
    else begin
     dfs(son[x,i]);
     h[x,i]:=max(h[son[x,i],1],h[son[x,i],2])+1;
     s[x,i]:=s[son[x,i],1]+s[son[x,i],2];
     end;
  end;
{---------------------------------------------------}
procedure nosol;
  begin
   writeln(-1);
   close(output);
   halt;
  end;
{---------------------------------------------------}
procedure update(x:longint);
  var i:longint;
  begin
   if x=-1 then exit;
   if s[x,1]<s[x,2] then
    begin
     i:=son[x,1];son[x,1]:=son[x,2];son[x,2]:=i;
     inc(num);
    end;
   update(son[x,1]);
   update(son[x,2]);
  end;
{---------------------------------------------------}
procedure main;
  var i:longint;
  begin
   dfs(1);
   for i:=1 to n do
    if abs(h[i,1]-h[i,2])>1 then nosol
    else
    if abs(h[i,1]-h[i,2])=1 then inc(sum[d[i]]);
    for i:=1 to 100 do
     if sum[i]>1 then nosol;
   update(1);
   writeln(num);
  end;
{---------------------------------------------------}
begin
  assign(input,'mobiles.in');reset(input);
  assign(output,'mobiles.out');rewrite(output);
  init;
  main;
  close(output);
end.

居然没有Pascal，我去学c++吧

一芥书生 2010-04-24 16:30 发表评论

原来是这样

一芥书生 — Sat, 24 Apr 2010 06:52:00 GMT

原来随笔才能发到首页上，刚知道。

一芥书生 2010-04-24 14:52 发表评论

C++博客-寂寞花开

apio2007 mobiles

原来是这样