📄 usaco 2_3_2 cow pedigrees 题解_leokan的blog.mht
字号:
http://hi.baidu.com/leokan"=20
href=3D"http://hi.baidu.com/leokan">leokan=B5=C4blog</A></DIV>
<DIV class=3Ddesc></DIV>
<DIV id=3Dtabline></DIV>
<DIV id=3Dtab><A href=3D"http://hi.baidu.com/leokan">=D6=F7=D2=B3</A><A =
class=3Don=20
href=3D"http://hi.baidu.com/leokan/blog">=B2=A9=BF=CD</A><A=20
href=3D"http://hi.baidu.com/leokan/album">=CF=E0=B2=E1</A><SPAN>|</SPAN><=
A=20
href=3D"http://hi.baidu.com/leokan/profile">=B8=F6=C8=CB=B5=B5=B0=B8</A> =
<SPAN>|</SPAN><A=20
href=3D"http://hi.baidu.com/leokan/friends">=BA=C3=D3=D1</A> =
<SPAN>|</SPAN><A=20
href=3D"http://hi.baidu.com/leokan/modify/spbasic/0">=C9=E8=D6=C3</A> =
</DIV></DIV>
<DIV class=3Dstage>
<DIV class=3Dstagepad>
<DIV style=3D"WIDTH: 100%">
<TABLE class=3Dmodth cellSpacing=3D0 cellPadding=3D0 width=3D"100%" =
border=3D0>
<TBODY>
<TR>
<TD class=3Dmodtl width=3D7> </TD>
<TD class=3Dmodtc noWrap>
<DIV class=3Dmodhead><SPAN =
class=3Dmodtit>=B2=E9=BF=B4=CE=C4=D5=C2</SPAN></DIV></TD>
<TD class=3Dmodtc noWrap align=3Dright>
<DIV class=3Dmodopt><A class=3Dmodact=20
href=3D"http://hi.baidu.com/leokan/creat/blog/"><IMG=20
src=3D"http://img.baidu.com/hi/img/ico_postnew.gif" =
align=3DabsMiddle=20
border=3D0>=D0=B4=D0=C2=CE=C4=D5=C2</A></DIV></TD>
<TD class=3Dmodtr width=3D7> </TD></TR></TBODY></TABLE>
<DIV class=3Dmodbox id=3Dm_blog>
<DIV class=3Dtit>USACO 2.3.2 Cow Pedigrees =CC=E2=BD=E2</DIV>
<DIV class=3Ddate>2008=C4=EA01=D4=C229=C8=D5 =D0=C7=C6=DA=B6=FE =
22:52</DIV>
<TABLE style=3D"TABLE-LAYOUT: fixed">
<TBODY>
<TR>
<TD>
<DIV class=3Dcnt>
<H2>USACO 2.3.2 Cow Pedigrees</H2>
<DIV class=3Dt_msgfont>Cow Pedigrees<BR>Silviu Ganceanu --=20
2003<BR><BR>Farmer John is considering purchasing a new herd of =
cows. In=20
this new herd, each mother cow gives birth to two children. The=20
relationships among the cows can easily be represented by one or =
more=20
binary trees with a total of N (3 <=3D N < 200) nodes. The =
trees have=20
these properties: <BR><BR><BR>The degree of each node is 0 or 2. =
The=20
degree is the count of the node's immediate children. <BR><BR>The =
height=20
of the tree is equal to K (1 < K <100). The height is the =
number of=20
nodes on the longest path from the root to any leaf; a leaf is a =
node with=20
no children. <BR><BR>How many different possible pedigree =
structures are=20
there? A pedigree is different if its tree structure differs from =
that of=20
another pedigree. Output the remainder when the total number of =
different=20
possible pedigrees is divided by 9901. <BR><BR>PROGRAM NAME:=20
nocows<BR>INPUT FORMAT<BR>Line 1: Two space-separated integers, N =
and K.=20
<BR>SAMPLE INPUT (file nocows.in)<BR>5 3<BR><BR><BR>OUTPUT =
FORMAT<BR>Line=20
1: One single integer number representing the number of possible =
pedigrees=20
MODULO 9901. <BR>SAMPLE OUTPUT (file nocows.out) =
<BR>2<BR><BR>OUTPUT=20
DETAILS:<BR><BR>Two possible pedigrees have 5 nodes and height =
equal to=20
3:<BR> @ =20
@ =
<BR> / \ =
=20
/ \<BR> @ =
@=20
and @ @<BR> =
/ \=20
=20
/ \<BR> @ @ =20
@ @<BR><BR><BR><BR>Cow=20
Pedigrees<BR><BR>=C4=CC=C5=A3=BC=D2=C6=D7<BR><BR>Silviu Ganceanu =
-- 2003<BR><BR>=D2=EB=20
=
yangzhe1990<BR><BR>=C5=A9=C3=F1=D4=BC=BA=B2=D7=BC=B1=B8=B9=BA=C2=F2=D2=BB=
=C8=BA=D0=C2=C4=CC=C5=A3=A1=A3 =
=D4=DA=D5=E2=B8=F6=D0=C2=B5=C4=C4=CC=C5=A3=C8=BA=D6=D0,=20
=
=C3=BF=D2=BB=B8=F6=C4=B8=C7=D7=C4=CC=C5=A3=B6=BC=C9=FA=C1=BD=D0=A1=C4=CC=C5=
=A3=A1=A3=D5=E2=D0=A9=C4=CC=C5=A3=BC=E4=B5=C4=B9=D8=CF=B5=BF=C9=D2=D4=D3=C3=
=B6=FE=B2=E6=CA=F7=C0=B4=B1=ED=CA=BE=A1=A3=D5=E2=D0=A9=B6=FE=B2=E6=CA=F7=D7=
=DC=B9=B2=D3=D0N=B8=F6=BD=DA=B5=E3(3 <=3D N <=20
=
200)=A1=A3=D5=E2=D0=A9=B6=FE=B2=E6=CA=F7=D3=D0=C8=E7=CF=C2=D0=D4=D6=CA: =
<BR>=C3=BF=D2=BB=B8=F6=BD=DA=B5=E3=B5=C4=B6=C8=CA=C70=BB=F22=A1=A3=B6=C8=CA=
=C7=D5=E2=B8=F6=BD=DA=B5=E3=B5=C4=BA=A2=D7=D3=B5=C4=CA=FD=C4=BF=A1=A3<BR>=
<BR>=CA=F7=B5=C4=B8=DF=B6=C8=B5=C8=D3=DAK(1 < K=20
< =
100)=A1=A3=B8=DF=B6=C8=CA=C7=B4=D3=B8=F9=B5=BD=C8=CE=BA=CE=D2=B6=D7=D3=B5=
=C4=D7=EE=B3=A4=B5=C4=C2=B7=BE=B6=C9=CF=B5=C4=BD=DA=B5=E3=B5=C4=CA=FD=C4=BF=
; =
=D2=B6=D7=D3=CA=C7=D6=B8=C3=BB=D3=D0=BA=A2=D7=D3=B5=C4=BD=DA=B5=E3=A1=A3<=
BR><BR><BR>=D3=D0=B6=E0=C9=D9=B2=BB=CD=AC=B5=C4=BC=D2=C6=D7=BD=E1=B9=B9? =
=
=C8=E7=B9=FB=D2=BB=B8=F6=BC=D2=C6=D7=B5=C4=CA=F7=BD=E1=B9=B9=B2=BB=CD=AC=D3=
=DA=C1=ED=D2=BB=B8=F6=B5=C4, =
=C4=C7=C3=B4=D5=E2=C1=BD=B8=F6=BC=D2=C6=D7=BE=CD=CA=C7=B2=BB=CD=AC=B5=C4=A1=
=A3=CA=E4=B3=F6=BF=C9=C4=DC=B5=C4=BC=D2=C6=D7=CA=F7=B5=C4=B8=F6=CA=FD=B3=FD=
=D2=D49901=B5=C4=D3=E0=CA=FD=A1=A3<BR><BR>PROGRAM NAME:=20
nocows<BR><BR>INPUT FORMAT<BR><BR>=B5=DA1=D0=D0: =
=C1=BD=B8=F6=BF=D5=B8=F1=B7=D6=BF=AA=B5=C4=D5=FB=CA=FD, =
N=BA=CDK=A1=A3<BR><BR>SAMPLE INPUT=20
(file nocows.in)<BR><BR>5 3<BR><BR>OUTPUT FORMAT<BR><BR>=B5=DA 1 =
=D0=D0:=20
=
=D2=BB=B8=F6=D5=FB=CA=FD=A3=AC=B1=ED=CA=BE=BF=C9=C4=DC=B5=C4=BC=D2=C6=D7=CA=
=F7=B5=C4=B8=F6=CA=FD=B3=FD=D2=D49901=B5=C4=D3=E0=CA=FD=A1=A3<BR><BR>SAMP=
LE OUTPUT (file=20
nocows.out)<BR><BR>2<BR><BR>OUTPUT=20
=
DETAILS:<BR>=D3=D05=B8=F6=BD=DA=B5=E3=A3=AC=B8=DF=CE=AA3=B5=C4=C1=BD=B8=F6=
=B2=BB=CD=AC=B5=C4=BC=D2=C6=D7=A3=BA<BR> =20
@ =
=20
@ <BR> / \ =
=20
/ \<BR> =
@=20
@ =BA=CD @ @<BR> =
/ \=20
=20
/ \<BR> @ @ =
=20
@ @</DIV>
<P></P>
<HR>
<P></P>
<P><STRONG>USACO 2.3.2 Cow Pedigrees</STRONG></P>
=
<P><STRONG>=CE=CA=CC=E2=D6=D8=CA=F6:<BR>=B8=F8=B3=F6n,k,=C7=F3=C2=FA=D7=E3=
=D2=BB=CF=C2=CC=F5=BC=FE=B5=C4=B6=FE=B2=E6=CA=F7=B8=F6=CA=FD<BR>1.=C3=BF=B8=
=F6=BD=E1=B5=E3=B5=C4=B6=C8=CE=AA=C5=BC=CA=FD<BR>2.=B8=C3=CA=F7=D3=D0n=B8=
=F6=BD=E1=B5=E3<BR>3.=B8=C3=CA=FD=B5=C4=C9=EE=B6=C8=CE=AAk</STRONG></P>
=
<P><STRONG>=CE=CA=CC=E2=B7=D6=CE=F6:<BR>=D3=C3=B6=AF=CC=AC=B9=E6=BB=AE=BA=
=CD=B3=CB=B7=A8=D4=AD=C0=ED=C7=F3=BD=E2,=BF=C9=D2=D4=B9=DB=B2=EC=B5=BD=D2=
=BB=B8=F6=CA=F7G(=D3=D0x=B8=F6=BD=E1=B5=E3,=C9=EE=B6=C8=CE=AAk),=C8=E7=B9=
=FB=C8=A5=B3=FD=CB=FC=B5=C4=B8=F9=BD=E1=B5=E3=BF=C9=D2=D4=B5=C3=B5=BD=C1=BD=
=B8=F6=D7=D3=CA=FDG1,G2,=D5=E2=C1=BD=B8=F6=D7=D3=CD=BC=B5=C4=C9=EE=B6=C8=CE=
=AAk-1,=CB=FB=C3=C7=B5=C4=BD=E1=B5=E3=CA=FD=B5=C4=BA=CD=CE=AAx-1.=C9=E8=C6=
=E4=D6=D0G1=D3=D0i=B8=F6=BD=E1=B5=E3=D4=F2G2=D3=D0x-1-i=B8=F6=BD=E1=B5=E3=
.</STRONG></P>
=
<P><STRONG>=B6=A8=D2=E5P(G)=CE=AA=D3=EB=C2=FA=D7=E3=CC=F5=BC=FE=B5=C4=B6=FE=
=B2=E6=CA=F7G=D3=D0=CD=AC=D1=F9=B6=E0=BD=E1=B5=E3=D3=D0=C9=EE=B6=C8=CF=E0=
=CD=AC=C7=D2=CD=AC=D1=F9=C2=FA=D7=E3=CC=F5=BC=FE=B5=C4=CA=F7=B5=C4=B8=F6=CA=
=FD.</STRONG></P>
=
<P><STRONG>=BD=AB=B6=FE=B2=E6=CA=F7=B0=B4=C9=CF=CA=F6=B7=BD=B7=A8=D2=C0=B4=
=CE=B7=D6=BD=E2=CE=AA(=D3=D01=B8=F6=BD=E1=B5=E3,=C9=EE=B6=C8=CE=AAk-1=B5=C4=
=CA=F7=BA=CD=D3=D0x-1-1=B8=F6=BD=E1=B5=E3=C9=EE=B6=C8=CE=AAk-1=B5=C4=CA=F7=
),(=D3=D02=B8=F6=BD=E1=B5=E3,=C9=EE=B6=C8=CE=AAk-1=B5=C4=CA=F7=BA=CD=D3=D0=
x-1-2=B8=F6=BD=E1=B5=E3=C9=EE=B6=C8=CE=AAk-1=B5=C4=CA=F7),(=D3=D03=B8=F6=BD=
=E1=B5=E3,=C9=EE=B6=C8=CE=AAk-1=B5=C4=CA=F7=BA=CD=D3=D0x-1-3=B8=F6=BD=E1=B5=
=E3=C9=EE=B6=C8=CE=AAk-1=B5=C4=CA=F7)...(=D3=D0x-1-1=B8=F6=BD=E1=B5=E3,=C9=
=EE=B6=C8=CE=AAk-1=B5=C4=CA=F7=BA=CD=D3=D01=B8=F6=BD=E1=B5=E3=C9=EE=B6=C8=
=CE=AAk-1=B5=C4=CA=F7)...</STRONG></P>
=
<P><STRONG>=D3=C9=B3=CB=B7=A8=D4=AD=C0=ED=B5=C3=B5=BD:=D3=C9G=B0=B4=C9=CF=
=CA=F6=B7=BD=B7=A8=B7=D6=BD=E2=B3=C9=B5=C4=C3=BF=B6=D4=B6=FE=B2=E6=CA=F7(=
Gx,Gy)=BC=D3=D2=BB=B8=F6=B8=F9=BD=E1=B5=E3=B9=B9=B3=C9=B5=C4=B6=FE=B2=E6=CA=
=F7=B5=C4=B8=F6=CA=FD=D3=D0P(Gx)*P(Gy)=B8=F6.</STRONG></P>
=
<P><STRONG>G=BF=C9=D2=D4=B7=D6=BD=E2=CE=AAx-2=B6=D4=D7=D3=CA=F7,=D3=C9=BC=
=D3=B7=A8=D4=AD=C0=ED=B5=C3=B5=BDP(G)=3D=A1=C6P(Gi)*P(Gj){(i,j)=A1=CAG=BF=
=C9=D2=D4=B7=D6=BD=E2=B5=BD=B5=C4=D7=D3=CA=F7=B6=D4(Gi,Gj)}</STRONG></P>
=
<P><STRONG>=B6=A8=D2=E5f(x,k)=C2=FA=D7=E3=CE=AA=C9=EE=B6=C8=CE=AAk,=BD=E1=
=B5=E3=B8=F6=CA=FD=CE=AAx,=C3=BF=B8=F6=BD=E1=B5=E3=B5=C4=B6=C8=CE=AA=C5=BC=
=CA=FD=B5=C4=B6=FE=B2=E6=CA=F7=B5=C4=B8=F6=CA=FD,=D3=C9=C9=CF=CA=F6=B7=D6=
=CE=F6=B5=C3=B5=BDf(x,k)=3D=A1=C6(f(x-1-i,k-1)*f(i,k-1){1<=3Di<=3Dx=
-2}.</STRONG></P>
=
<P><STRONG>code:<BR>{<BR>TASK:nocows<BR>LANG:PASCAL<BR>}<BR>program=20
nocows;<BR>var<BR> f:array[0..200,0..100] of=20
qword;<BR> leaf:array[0..200,0..100] of=20
qword;<BR> n,d:integer;<BR>procedure=20
init;<BR>begin<BR> =20
assign(input,'nocows.in');reset(input);<BR> =20
readln(n,d);<BR> =
close(input);<BR>end;<BR>procedure=20
dp;<BR>var<BR> =20
i,j,k,ans:integer;<BR>begin<BR> =20
assign(output,'nocows.out');rewrite(output);<BR> =
if n=20
and 1=3D0 then<BR> =20
=
begin<BR> &nbs=
p;=20
=
writeln(0);<BR> &nbs=
p; =20
=
close(output);<BR> &=
nbsp; =20
exit;<BR> =20
end;<BR> =
fillchar(f,sizeof(f),0);<BR> =20
for i:=3D1 to d do f[1,i]:=3D1;<BR> for i:=3D1 =
to n=20
do<BR> if i and 1=3D1=20
=
then<BR>  =
;=20
for j:=3D1 to d=20
=
do<BR> &=
nbsp; =20
for k:=3D1 to i-2=20
=
do<BR> &=
nbsp; =20
if k and 1=3D1=20
=
then<BR>  =
; =20
=
begin<BR> &nbs=
p;  =
;=20
=
inc(f[i,j],f[i-k-1,j-1]*f[k,j-1]);<BR>  =
; =
=20
f[i,j]:=3Df[i,j] mod=20
=
9901;<BR> &nbs=
p; =20
end;<BR> =
ans:=3D(f[n,d]-f[n,d-1]);<BR> =20
if ans<0 then ans:=3Dans+9901;<BR> ans:=3Dans =
mod=20
9901;<BR> writeln(ans);<BR> =20
close(output);<BR>end;<BR>begin<BR> =20
init;<BR> dp;<BR>end.</STRONG></P><STRONG>
<HR>
</STRONG>
<P><STRONG>usaco=B5=C4=B7=D6=CE=F6<BR></STRONG></P>
<P><STRONG>This is a DP problem. The properties of a tree that we =
are=20
interested in are depth and number of nodes, so we'll make a =
table:=20
table[i][j] contains the number of trees with depth i and number =
of nodes=20
j. Given the constraints of the task, j must be odd. How do you =
construct=20
a tree? From smaller trees, of course. A tree of depth i and j =
nodes will=20
be constructed from two smaller trees and one more node. With i =
and j=20
already chosen, we chose k, which is the number of nodes in the =
left=20
subtree. Then the number of nodes in the right subtree is known, =
j-k-1.=20
For depth, at least one subtree has to have depth i-1 so that the =
new made=20
tree would have depth i. There are three possibilities: the left =
subtree=20
can have depth i-1 and the depth of the right subtree can be =
smaller, the=20
right subtree can have depth i-1 and the depth of the left subtree =
can be=20
smaller, or they can both have depth i-1. The truth is that once =
we are=20
constructing trees of depth i, we use smaller trees, but we only =
care if=20
those are of depth i-1 or smaller. So, let another array,=20
smalltrees[i-2][j] contain number of trees of any depth smaller =
than i-1,=20
not just i-2. Now, knowing all this, we contruct our tree from =
three=20
possible ways: </STRONG></P><PRE><STRONG>table[i][j] +=3D =
smalltrees[i-2][k]*table[i-1][j-1-k];
// left subtree smaller than i-1, right is i-1
table[i][j] +=3D table[i-1][k]*smalltrees[i-2][j-1-k];
// left subtree is i-1, right smaller
table[i][j] +=3D table[i-1][k]*table[i-1][j-1-k];
// both i-1 </STRONG></PRE>
<P><STRONG>In addition, if the number of nodes in the left subtree =
is=20
smaller then the number of nodes in the left subtree, we can count =
the=20
tree twice, as different tree can be constructed by swaping left =
and right=20
subtree. Total running time is O(K*N^2),with very favorable =
constant=20
factor. </STRONG></P><PRE><STRONG>#include <cstdio>
#include <cstdlib>
#include <cassert>
#define MOD 9901
using namespace std;
int table[101][202],N,K,c;
int smalltrees[101][202];
FILE *fin=3Dfopen("nocows.in","r");
FILE *fout=3Dfopen("nocows.out","w");
int main() {
fscanf (fin,"%d %d",&N,&K);
table[1][1]=3D1;
for (int i=3D2;i<=3DK;i++) {
for (int j=3D1;j<=3DN;j+=3D2)
for (int k=3D1;k<=3Dj-1-k;k+=3D2) {
if (k!=3Dj-1-k) c=3D2; else c=3D1; =20
table[i][j]+=3Dc*(
smalltrees[i-2][k]*table[i-1][j-1-k] // left =
subtree smaller than i-1
+table[i-1][k]*smalltrees[i-2][j-1-k] // right =
smaller
+table[i-1][k]*table[i-1][j-1-k]);// both i-1
table[i][j]%=3DMOD;
}
for (int k=3D0;k<=3DN;k++) { // we ensure that =
smalltrees[i-2][j] in
the next i
smalltrees[i-1][k]+=3Dtable[i-1][k]+smalltrees[i-2][k]; // =
iteration
contains the number
smalltrees[i-1][k]%=3DMOD; // of trees smaller =
than i-1 and with
j nodes
}
}
=20
fprintf (fout,"%d\n",table[K][N]);
return 0;
}</STRONG></PRE></DIV></TD></TR></TBODY></TABLE><BR>
<DIV class=3Dopt><A =
title=3D=B2=E9=BF=B4=B8=C3=B7=D6=C0=E0=D6=D0=CB=F9=D3=D0=CE=C4=D5=C2=20
href=3D"http://hi.baidu.com/leokan/blog/category/Oi">=C0=E0=B1=F0=A3=BAOi=
</A> | <A=20
href=3D"http://hi.baidu.com/leokan/modify/blog/a8fca034599fd0b3d0a2d3bd">=
=B1=E0=BC=AD</A> |=20
<A onclick=3D"return blogdel('blogdelform')"=20
href=3D"http://hi.baidu.com/leokan/blog/item/a8fca034599fd0b3d0a2d3bd.htm=
l#">=C9=BE=B3=FD</A>=20
<FORM id=3Dblogdelform style=3D"DISPLAY: none" name=3Dblogdelform=20
action=3D/leokan/commit method=3Dpost><INPUT type=3Dhidden value=3D1 =
name=3Dct><INPUT=20
type=3Dhidden value=3D3 name=3Dcm><INPUT type=3Dhidden =
value=3Da8fca034599fd0b3d0a2d3bd=20
name=3DspBlogID><INPUT type=3Dhidden =
value=3Dhttp://hi.baidu.com/leokan/blog=20
name=3DspRefURL></FORM>
<SCRIPT language=3Djavascript>
<!--
function blogdel(str)
{
var pop=3Dnew Popup({ =
contentType:3,isReloadOnClose:false,width:340,height:80});
pop.setContent("title","=C9=BE=B3=FD=CE=C4=D5=C2");
=
pop.setContent("confirmCon","=C4=FA=C8=B7=B6=A8=D2=AA=B3=B9=B5=D7=C9=BE=B3=
=FD=D5=E2=C6=AA=CE=C4=D5=C2=BC=B0=C6=E4=CB=F9=D3=D0=C6=C0=C2=DB=C2=F0=A3=BF=
");
pop.setContent("callBack",delCallback);
pop.setContent("parameter",{fid:str,popup:pop});
pop.build();
pop.show();
return false;
}
function delCallback(para)
{
var o_pop=3Dpara["popup"];
o_pop.config.contentType=3D1;
o_pop.setContent("contentUrl","");
o_pop.reBuild();
G(para["fid"]).target=3Do_pop.iframeIdName;
eval("document."+para["fid"]).submit();
}
//-->
</SCRIPT>
| <A =
title=3D=BD=AB=B4=CB=CE=C4=D5=C2=CC=ED=BC=D3=B5=BD=B0=D9=B6=C8=CB=D1=B2=D8=
onclick=3D"return addToFavor();"=20
href=3D"http://cang.baidu.com/do/add" =
target=3D_blank>=CC=ED=BC=D3=B5=BD=CB=D1=B2=D8</A> | =E4=AF=C0=C0(<SPAN=20
id=3Dresult></SPAN>) | <A=20
href=3D"http://hi.baidu.com/leokan/blog/item/a8fca034599fd0b3d0a2d3bd.htm=
l#send">=C6=C0=C2=DB</A> (0)
<SCRIPT language=3Djavascript>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -