UVa536 Recovery

链接:Link 耗时:0.012s

前言

真是疯玩了几天,脑袋都残了,一道弱智题做了近一个小时。

Code

var
pre, mid, s: string;
tree: array [1..50] of record
l, r: integer;
ch: char;
end;
cur: integer;
function init: integer;
var
m: integer;
begin
readln(s);
m := length(s) >> 1 + 1;
pre := Copy(s, 1, m-1);
mid := Copy(s, m+1, length(s));
init := m-1;
end;
function build(l1, l2, r2: integer): integer;
var
m,len: integer;
t: integer;
begin
if l2 > r2 then exit(0); //该子树不存在。**这个地方坑了我很久**
inc(cur);
t := cur; // 这里也坑了我,当下面构造完左右子树后,cur已经变了,所以要缓存起来
build := t;
tree[t].ch := pre[l1];
if r2-l2 = 0 then //叶节点
exit;
m := pos(pre[l1], mid); //在中序遍历中找根节点
len := m - l2;
tree[t].l := build(l1+1, l2, m-1); //构造左子树
tree[t].r := build(l1+len+1, m+1, r2); //构造右子树
end;
procedure print(x: integer);
begin
if x = 0 then exit;
print(tree[x].l);
print(tree[x].r);
write(tree[x].ch);
end;
begin
assign(input, 'main.in'); reset(input);
assign(output, 'main.out'); rewrite(output);
while not eof do
begin
fillchar(tree, sizeof(tree), 0);
cur := 0;
build(1, 1, init);
print(1);
writeln;
end;
close(input);
close(output);
end.

作者:hsfzxjy
链接:
许可:CC BY-NC-ND 4.0.
著作权归作者所有。本文不允许被用作商业用途,非商业转载请注明出处。

«UVa12219 Common Subexpression Elimination

OOPS!

A comment box should be right here...But it was gone due to network issues :-(If you want to leave comments, make sure you have access to disqus.com.