USACO题库2.3.2CowPedigrees奶牛家谱题解，如何高效解题？

2026-04-01 23:301阅读0评论SEO教程

内容介绍
文章标签
相关推荐

本文共计1477个文字，预计阅读时间需要6分钟。

项目描述：描述一个农民群体准备购买一群新奶牛。在这个新奶牛群中，每个母猪都生了两头小奶牛。这些奶牛之间的关系可以用二叉树来表示。这些二叉树总共有N个节点（3N-2个题目）。

题目描述农民约翰准备购买一群新奶牛。在这个新的奶牛群中,每一个母亲奶牛都生两小奶牛。这些奶牛间的关系可以用二叉树来表示。这些二叉树总共有N个节点(3N200 题目描述农民约翰准备购买一群新奶牛。在这个新的奶牛群中, 每一个母亲奶牛都生两小奶牛。这些奶牛间的关系可以用二叉树来表示。这些二叉树总共有N个节点(3 <= N <200)。这些二叉树有如下性质:每一个节点的度是0或2。度是这个节点的孩子的数目。树的高度等于K(1

这道题其实就是一个树形DP。

现在先讲一下我个人的方法：

我是直接设f[i,j]表示的是深度<=j，不仅是等于j，j以内的所有深度只要节点为i的方案数。

我们都知道一棵树，是由一个根节点+左子树+右子数。划分阶段当然是按树的深度和节点数来划分。

设这一棵树有m个节点，左子树有k个节点，则右子树有m-k-1个节点，f[i,j]:=f[i,j]+f[k,j-1]*f[i-k-1,j-1].

因为最后答案求的是深度为k的值，并不是<=k的值，所以应该是f[n,k]-f[n,k-1]

但是在每一个阶段的取模中，有可能会导致f[n,m]

代码：

var i,j,p,k,n:longint; f:array[0..500,0..500] of longint;begin readln(n,k); for i:=1 to k do f[1,i]:=1; for i:=3 to n dobegin if not odd(i) then continue; for j:=2 to k do for p:=1 to i-1 do f[i,j]:=(f[i,j]+f[p,j-1]*f[i-p-1,j-1]) mod 9901;end; if f[n,k]>=f[n,k-1] then writeln(f[n,k]-f[n,k-1]) else writeln(f[n,k]+9901-f[n,k-1]);end.

上面这种方法简便，好懂，但是我还是要介绍一种官方的方法：

对于一棵树，如何构成？当然是从这颗树的上一个阶段开始构成的，通俗的讲，当前第i层是由前i-1层加上第i层构成的，所以如果要构成一棵树，则至少要有一颗左子树或者右子树深度为i-1.

所以当：

左子树为i-1，右子树小于i-1，

右子树为i-1，左子树小于i-1，

左、右子树都为i-1。

这三种情况时可以构成第i层，所以这里的阶段划分与第一种方法一样，只不过表示不同的状态罢了。

所以——要计算第i层，节点数j的树的个数的时候要取这三种情况所构成的数目的和。

f[i,j]表示的是深度为i，节点数为j的树的个数。

f[i,j]:=tree[i-1,k]*f[i-1,j-1-k]+

tree[i-1,j-1-k]*f[i-1,k]+

f[i-1,k]*f[i-1,j-1-k]。

而这里小于i-1的是包含所有i-1之内的，这里就可以再用一个数组代替，或者直接暴力枚举（会有官方暴力版）而用数组代替则巧妙许多，可以设tree[i,j]表示包含所有小于i的节点数为j的树的个数。

显然

tree[i,j]=tree[i-1,j]+f[i-1,j]

tree[i,j]因为是小于i，所以i-1才是“所谓”的“最后一层”，所以是+f[i-1,j]。

空间稍稍大些，时间0.1m以内

const maxn=9901;var f,tree:array[0..200,0..200] of longint; i,j,p,n,k:Longint;begin readln(n,k); fillchar(f,sizeof(f),0); f[1,1]:=1; for i:=2 to k do for j:=1 to n do begin for p:=1 to j-1 do begin f[i,j]:=(f[i,j]+tree[i-2,p]*f[i-1,j-p-1]) mod maxn; f[i,j]:=(f[i,j]+tree[i-2,j-p-1]*f[i-1,p]) mod maxn; f[i,j]:=(f[i,j]+f[i-1,p]*f[i-1,j-p-1]) mod maxn; end; tree[i-1,j]:=(tree[i-2,j]+f[i-1,j]) mod maxn; end; writeln(f[k,n]);end.

暴力版（空间较小，时间500ms+）：

const maxn=9901;var f:array[0..200,0..200] of longint; i,j,p,q,n,k,sum:Longint;begin readln(n,k); fillchar(f,sizeof(f),0); f[1,1]:=1; for i:=2 to k do for j:=1 to n do for p:=1 to j-1 do begin sum:=0; for q:=1 to i-2 do inc(sum,f[q,p]); f[i,j]:=(f[i,j]+sum*f[i-1,j-p-1]) mod maxn; sum:=0; for q:=1 to i-2 do inc(sum,f[q,j-p-1]); f[i,j]:=(f[i,j]+sum*f[i-1,p]) mod maxn; //这个地方其实没有别的用处，就是代替第一种官方方法的tree数组罢了. f[i,j]:=(f[i,j]+f[i-1,p]*f[i-1,j-p-1]) mod maxn; end; writeln(f[k,n]);end.

标签：USACO 题库 232CowPedigrees