2007-2011年noip初赛提高组试题及答案

end.

2. （笛卡尔树）对于一个给定的两两不等的正整数序列，笛卡尔树是这样的一棵二叉树：首先，它是一个最小堆，即除了根结点外，每个结点的权值都大于父节点的权值；其次，它的中序遍历恰好就是给定的序列。例如，对于序列7、2、12、1、10、5、15、3，下图就是一棵对应的笛卡尔树。现输入序列的规模n（1≤n<100）和序列的n个元素，试求其对应的笛号尔树的深度d(根节点深度为1)，以及有多少个叶节点的深度为d。 const

SIZE = 100;

INFINITY = 1000000; var

n, maxDeep, num, i : integer; a : array[1..SIZE] of integer;

procedure solve(1eft, right, deep : integer); var

i, j, min : integer; begin

if deep > maxDeep then begin

maxDeep := deep; num := 1; end

else if deep = maxDeep then ___①___;

min := INFINITY;

for i := 1eft to right do if min > a[i] then begin

min := a[i]; ___②___; end;

if left < j then ___③___;

if j < right then

___④___; end; begin readln(n);

for i := 1 to n do read(a[i]); maxDeep := 0; solve(1, n, 1);

writeln(maxDeep, end.

’, num); ‘