📄 usaco 3_4_2 american heritage 题解_leokan的blog.mht
字号:
<DIV class=3Dmodbox id=3Dm_blog>
<DIV class=3Dtit>USACO 3.4.2 American Heritage =CC=E2=BD=E2</DIV>
<DIV class=3Ddate>2008=C4=EA02=D4=C213=C8=D5 =D0=C7=C6=DA=C8=FD =
17:36</DIV>
<TABLE style=3D"TABLE-LAYOUT: fixed">
<TBODY>
<TR>
<TD>
<DIV class=3Dcnt>
<H2>USACO 3.4.2 American Heritage</H2>
<DIV class=3Dt_msgfont>
<P>American Heritage<BR><BR>Farmer John takes the heritage of his =
cows=20
very seriously. He is not, however, a truly fine bookkeeper. He =
keeps his=20
cow genealogies as binary trees and, instead of writing them in =
graphic=20
form, he records them in the more linear `tree in-order' and `tree =
pre-order' notations. <BR><BR>Your job is to create the `tree =
post-order'=20
notation of a cow's heritage after being given the in-order and =
pre-order=20
notations. Each cow name is encoded as a unique letter. (You may =
already=20
know that you can frequently reconstruct a tree from any two of =
the=20
ordered traversals.) Obviously, the trees will have no more than =
26 nodes.=20
<BR><BR>Here is a graphical representation of the tree used in the =
sample=20
input and output: <BR><BR> =20
C<BR> =
=20
/ \<BR> =
/=20
\<BR> =20
B G<BR> =20
/ \ /<BR> =
A D H<BR> =
=20
/ \<BR> E =
F<BR><BR>The in-order traversal of this tree prints the left =
sub-tree, the=20
root, and the right sub-tree. <BR><BR>The pre-order traversal of =
this tree=20
prints the root, the left sub-tree, and the right sub-tree. =
<BR><BR>The=20
post-order traversal of this tree print the left sub-tree, the =
right=20
sub-tree, and the root. <BR><BR>PROGRAM NAME: heritage<BR>INPUT=20
FORMAT<BR>Line 1: The in-order representation of a=20
tree. <BR>Line 2: The pre-order =
representation of=20
that same tree. <BR><BR>SAMPLE INPUT (file heritage.in)=20
<BR>ABEDFCHG<BR>CBADEFGH<BR><BR>OUTPUT FORMAT<BR>A single line =
with the=20
post-order representation of the tree. <BR>SAMPLE OUTPUT (file=20
heritage.out)<BR>AEFDBHGC <BR><BR><BR><BR>American=20
Heritage<BR><BR>=C3=C0=B9=FA=D1=AA=CD=B3<BR><BR>=D2=EB By=20
=
TinyTony<BR><BR>=C5=A9=B7=F2=D4=BC=BA=B2=B7=C7=B3=A3=C8=CF=D5=E6=B5=D8=B6=
=D4=B4=FD=CB=FB=B5=C4=C4=CC=C5=A3=C3=C7=B5=C4=D1=AA=CD=B3=A1=A3=C8=BB=B6=F8=
=CB=FB=B2=BB=CA=C7=D2=BB=B8=F6=D5=E6=D5=FD=D3=C5=D0=E3=B5=C4=BC=C7=D5=CA=D4=
=B1=A1=A3=CB=FB=B0=D1=CB=FB=B5=C4=C4=CC=C5=A3=C3=C7=B5=C4=BC=D2=C6=D7=D7=F7=
=B3=C9=B6=FE=B2=E6=CA=F7=A3=AC=B2=A2=C7=D2=B0=D1=B6=FE=B2=E6=CA=F7=D2=D4=B8=
=FC=CF=DF=D0=D4<BR>=B5=C4=A1=B1=CA=F7=B5=C4<SPAN=20
class=3Dt_tag =
href=3D"tag.php?name=3D%D6%D0%D0%F2%B1%E9%C0%FA">=D6=D0=D0=F2<SPAN=20
class=3Dt_tag =
href=3D"tag.php?name=3D%B1%E9%C0%FA">=B1=E9=C0=FA</SPAN></SPAN>=A1=B0=BA=CD=
=A1=B1=CA=F7=B5=C4=C7=B0=D0=F2<SPAN=20
class=3Dt_tag=20
=
href=3D"tag.php?name=3D%B1%E9%C0%FA">=B1=E9=C0=FA</SPAN>=A1=B0=B5=C4=B7=FB=
=BA=C5=BC=D3=D2=D4=BC=C7=C2=BC=B6=F8=B2=BB=CA=C7=D3=C3=CD=BC=D0=CE=B5=C4=B7=
=BD=B7=A8=A1=A3<BR>=C4=E3=B5=C4=C8=CE=CE=F1=CA=C7=D4=DA=B1=BB=B8=F8=D3=E8=
=C4=CC=C5=A3=BC=D2=C6=D7=B5=C4=A1=B1=CA=F7=D6=D0=D0=F2=B1=E9=C0=FA=A1=B0=BA=
=CD=A1=B1=CA=F7<SPAN=20
class=3Dt_tag=20
=
href=3D"tag.php?name=3D%C7%B0%D0%F2%B1%E9%C0%FA">=C7=B0=D0=F2=B1=E9=C0=FA=
</SPAN>=A1=B0=B5=C4=B7=FB=BA=C5=BA=F3=A3=AC=B4=B4=BD=A8=C4=CC=C5=A3=BC=D2=
=C6=D7=B5=C4=A1=B1=CA=F7=B5=C4=BA=F3=D0=F2=B1=E9=C0=FA=A1=B0=B5=C4=B7=FB=BA=
=C5=A1=A3=C3=BF=D2=BB=CD=B7=C4=CC=C5=A3=B5=C4=D0=D5=C3=FB=B1=BB<BR>=D2=EB=
=CE=AA=D2=BB=B8=F6=CE=A8=D2=BB=B5=C4=D7=D6=C4=B8=A1=A3=A3=A8=C4=E3=BF=C9=C4=
=DC=D2=D1=BE=AD=D6=AA=B5=C0=C4=E3=BF=C9=D2=D4=D4=DA=D6=AA=B5=C0=CA=F7=B5=C4=
=C1=BD=D6=D6=B1=E9=C0=FA=D2=D4=BA=F3=BF=C9=D2=D4=BE=AD=B3=A3=B5=D8=D6=D8=BD=
=A8=D5=E2=BF=C3=CA=F7=A1=A3=A3=A9=CF=D4=C8=BB=A3=AC=D5=E2=C0=EF=B5=C4=CA=F7=
=B2=BB=BB=E1=D3=D0=B6=E0=D3=E026=B8=F6=B5=C4=B6=A5=B5=E3=A1=A3<BR>=D5=E2=CA=
=C7=D4=DA=D1=F9=C0=FD=CA=E4=C8=EB=BA=CD=D1=F9=C0=FD=CA=E4=B3=F6=D6=D0=B5=C4=
=CA=F7=B5=C4=CD=BC=D0=CE=B1=ED=B4=EF=B7=BD=CA=BD=A3=BA<BR><BR><BR> &=
nbsp;=20
=
C<BR> =20
/ \<BR> =
=20
/ \<BR> =20
B =20
G<BR> / \ =
/<BR> A D H<BR> =20
/ \<BR> =
=20
E=20
=
F<BR><BR><BR><BR>=CA=F7=B5=C4=D6=D0=D0=F2=B1=E9=C0=FA=CA=C7=B4=F2=D3=A1=D7=
=F3=D7=D3=CA=F7=A3=AC=B8=F9=BA=CD=D3=D2=D7=D3=CA=F7=A1=A3<BR>=CA=F7=B5=C4=
=C7=B0=D0=F2=B1=E9=C0=FA=CA=C7=B4=F2=D3=A1=B8=F9=A3=AC=D7=F3=D7=D3=CA=F7=BA=
=CD=D3=D2=D7=D3=CA=F7=A1=A3<BR>=CA=F7=B5=C4=BA=F3=D0=F2=B1=E9=C0=FA=CA=C7=
=B4=F2=D3=A1=D7=F3=D7=D3=CA=F7=A3=AC=D3=D2=D7=D3=CA=F7=BA=CD=B8=F9=A1=A3<=
BR><BR><BR>PROGRAM=20
NAME: heritage<BR>INPUT FORMAT<BR>=B5=DA=D2=BB=D0=D0=A3=BA =
=CA=F7=B5=C4=D6=D0=D0=F2=B1=E9=C0=FA <BR>=B5=DA=B6=FE=D0=D0=A3=BA =
=CD=AC=D1=F9=B5=C4=CA=F7=B5=C4=C7=B0=D0=F2=B1=E9=C0=FA=20
<BR><BR>SAMPLE INPUT (file=20
heritage.in)<BR>ABEDFCHG<BR>CBADEFGH<BR><BR>OUTPUT=20
=
FORMAT<BR>=B5=A5=B6=C0=B5=C4=D2=BB=D0=D0=B1=ED=CA=BE=B8=C3=CA=F7=B5=C4=BA=
=F3=D0=F2=B1=E9=C0=FA=A1=A3<BR><BR>SAMPLE OUTPUT (file=20
heritage.out)<BR><BR>AEFDBHGC</P>
<DIV class=3Dt_msgfont>
<P></P>
<HR>
<P></P>
<DIV class=3Dt_msgfont>
<DIV align=3Dleft>
<P><STRONG>USACO 3.4.2 American Heritage=20
=
<BR>=CC=E1=BD=BB=B4=CE=CA=FD:1=B4=CE<BR><BR>=D4=D9=D7=F6=C1=CB=D2=BB=B4=CE=
,=B5=DD=B9=E9=B5=C4=BC=F2=BD=E0=C1=CB=D2=BB=D0=A9 </STRONG></P=
>
=
<P><STRONG>=CB=E3=B7=A8=CB=BC=CF=EB=C7=EB=BC=FB=CE=D2=D2=D4=C7=B0=B5=C4=CC=
=E2=BD=E2:</STRONG></P>
<P><STRONG><A=20
=
href=3D"http://hi.baidu.com/leokan/blog/item/08513401934e070d7aec2c49.htm=
l">http://hi.baidu.com/leokan/blog/item/08513401934e070d7aec2c49.html</A>=
</STRONG></P></DIV>
<P><STRONG>{<BR>TASK:heritage<BR>LANG:PASCAL<BR>}<BR>program=20
heritage;<BR>var<BR> =20
front,middle,back:string;<BR>procedure=20
init;<BR>begin<BR> =20
assign(input,'heritage.in');reset(input);<BR> =20
readln(middle);<BR> =
readln(front);<BR> =20
close(input);<BR>end;<BR>procedure=20
solve(mid,fro:string);<BR>var<BR> =20
e,l,m:integer;<BR> =
ch:char;<BR> =20
mid1,fro1:string;<BR>begin<BR> =20
e:=3Dlength(fro);<BR> =
ch:=3Dfro[1];<BR> =20
m:=3Dpos(ch,mid);<BR> if=20
e>1then<BR> =20
=
begin<BR> &nbs=
p;=20
if m>1=20
=
then<BR>  =
; =20
=
begin<BR> &nbs=
p; =20
=
mid1:=3Dcopy(mid,1,m-1);<BR> &nb=
sp; =20
=
fro1:=3Dcopy(fro,2,m-1);<BR> &nb=
sp; =20
=
solve(mid1,fro1);<BR> &nbs=
p; =20
=
end;<BR>  =
;=20
if e>m=20
=
then<BR>  =
; =20
=
begin<BR> &nbs=
p; =20
=
mid1:=3Dcopy(mid,m+1,e-m);<BR> &=
nbsp; =20
=
fro1:=3Dcopy(fro,m+1,e-m);<BR> &=
nbsp; =20
=
solve(mid1,fro1);<BR> &nbs=
p; =20
end;<BR> =20
end;<BR> write(ch);<BR>end;<BR>procedure=20
work;<BR>begin<BR> =20
=
assign(output,'heritage.out');rewrite(output);<BR> =20
solve(middle,front);<BR> =
writeln;<BR> =20
close(output);<BR>end;<BR>begin<BR> =20
init;<BR> work;<BR>end. </STRONG>
<P></P>
<P></P>
<HR>
</DIV></DIV></DIV>
<P></P>
<P><STRONG>USACO=B5=C4=B7=D6=CE=F6</STRONG></P>
<P><STRONG>Here's one way: We use a recursive procedure to =
generate the=20
actual binary tree. Once we have the tree, we execute a postorder=20
traversal to print the node values. =
</STRONG></P><PRE><STRONG>#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
FILE *fout;
typedef struct Tree Tree;
struct Tree {
int c;
Tree *left;
Tree *right;
};
Tree*
mktree(int c, Tree *left, Tree *right)
{
Tree *t;
t =3D (Tree*)malloc(sizeof *t);
assert(t);
t->c =3D c;
t->left =3D left;
t->right =3D right;
return t;
}
/*
* Pre and in point at strings of length len
* that describe the same tree, in pre-order
* and in-order traversals. Return a
* corresponding binary tree.
*/
Tree*
prein2tree(char *pre, char *in, int len)
{
char *p;
int llen, rlen;
assert(strlen(pre)>=3Dlen && strlen(in)>=3Dlen);
if(len =3D=3D 0)
return NULL;
/*
* The first character of the preorder traversal is the root.
* If we find the root in the inorder traversal, then everything
* to its left is on the left side, and everything to its right on =
the
* right side. Recur on both sides.
*/
p =3D strchr(in, pre[0]);
assert(p !=3D NULL);
assert(p-in < len);
llen =3D p-in;
rlen =3D len-llen-1;
return mktree(pre[0], prein2tree(pre+1, in, llen), =
prein2tree(pre+1+llen, p+1, rlen));
}
void
postorder(Tree *t)
{
if(t =3D=3D NULL)
return;
postorder(t->left);
postorder(t->right);
fprintf(fout, "%c", t->c);
}
void
main(void)
{
FILE *fin;
char pre[50], in[50];
fin =3D fopen("heritage.in", "r");
fout =3D fopen("heritage.out", "w");
assert(fin !=3D NULL && fout !=3D NULL);
fscanf(fin, "%s %s", in, pre);
postorder(prein2tree(pre, in, strlen(pre)));
fprintf(fout, "\n");
exit(0);
}
</STRONG><PRE><P><STRONG> From Greg Price:
</STRONG></P><P><STRONG>We don't need to reconstruct the original tree =
explicitly for this
problem. Instead, we use a recursive function that plucks the root from
the start of the preorder traversal, uses it to divide the inorder
traversal, calls itself recursively on the left and right subtrees, and
outputs the root.
</STRONG></P><PRE><STRONG>#include <fstream.h>
#include <string.h>
ifstream fin("heritage.in");
ofstream fout("heritage.out");
const short maxn =3D 26 + 2;
short len;
char in[maxn], pre[maxn];
void
makepost(short ina, short inb, short prea, short preb)
{
char root;
short rt_in;
short lsize, rsize;
if (ina =3D=3D inb) // Null tree
return;
root =3D pre[prea];
// Find root in inorder
for (rt_in =3D ina; rt_in < inb; rt_in++)
if (in[rt_in] =3D=3D root)
break;
// Size of left-hand subtree
lsize =3D rt_in - ina;
makepost(ina, rt_in, prea+1, prea+1 + lsize); // Left
subtree
makepost(rt_in+1, inb, prea+1 + lsize, preb); // Right subtree
fout << root;
}
void
main()
{
fin.getline(in , maxn);
fin.getline(pre, maxn);
len =3D strlen(in);
makepost(0, len, 0, len);
fout << endl;
}
</STRONG></PRE>
<H2>Another Solution -- Daniel Bundala</H2>
<P><STRONG>Here is a better and faster solution for problem "heritage". =
I used
standard recursive approach like solutions in analysis for the
problem. But insert new element into the tree can be made faster.
Because solutions in analysis in each recursive call are finding
the position of inserting element in in-order representation of the
tree. It is O(N) in O(N) calls worth case =3D O(N^2).
</STRONG></P>
<P><STRONG>But what we can do is to precompute positions of elements in =
in-order
representation and when we are inserting new elment e into the node
n, e is in left subtree if and only if position_in_inorder[i] <
position_in_inorder[n->value] otherwise element e is in right
subtree.
</STRONG></P>
<P><STRONG>Now inserting: O(1) in O(N) recursive call - worth case =3D =
O(N).
All algorithm is O(N^2) and before was O(N^3) - worth case. And O(N
log N) now, before O(N^2) - average case; N =3D number of cows
</STRONG></P>
<P><STRONG>My implementation (I'm using index into the array instead of =
pointer):
</STRONG></P>
<PRE><STRONG>/*
LANG: C++
PROG: heritage
*/
#include <stdio.h>
#include <string.h>
FILE *in,*out;
char ino[200], preo[200];
int place[255];
struct NODE{
int left, right;
char name;
};
NODE node[200];
int count =3D 1;
//return true if who is before the value of node[n] in inorder; O(1)
bool isBefore(char who, int n){
return place[who] < place[node[n].name];
};
void insert(char c, int where){
if (isBefore(c, where)){ //in the left subtree
if (node[where].left =3D=3D -1){ //left subtree is empty
node[count].left =3D node[count].right =3D -1;
node[count].name =3D c;
node[where].left =3D count++;
} else {
insert(c, node[where].left); //insert into the left subtree
};
} else { // in the right subtree
if (node[where].right =3D=3D -1){ //right subtree is empty
node[count].left =3D node[count].right =3D -1;
node[count].name =3D c;
node[where].right =3D count++;
} else {
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -