USACO 2.3 Cow Pedigrees

题目描述

Farmer John is considering purchasing a new herd of cows. In this new herd, each mother cow gives birth to two children. The relationships among the cows can easily be represented by one or more binary trees with a total of N (3 <= N < 200) nodes. The trees have these properties:

  • The degree of each node is 0 or 2. The degree is the count of the node's immediate children.
  • The height of the tree is equal to K (1 < K < 100). The height is the number of nodes on the longest path from the root to any leaf; a leaf is a node with no children.

How many different possible pedigree structures are there? A pedigree is different if its tree structure differs from that of another pedigree. Output the remainder when the total number of different possible pedigrees is divided by 9901.

继续阅读USACO 2.3 Cow Pedigrees

USACO 2.3 Longest Prefix

题目描述

The structure of some biological objects is represented by the sequence of their constituents, where each part is denoted by an uppercase letter. Biologists are interested in decomposing a long sequence into shorter sequences called primitives.

We say that a sequence S can be composed from a given set of primitives P if there is a some sequence of (possibly repeated) primitives from the set whose concatenation equals S. Not necessarily all primitives need be present. For instance the sequence ABABACABAABcan be composed from the set of primitives

   {A, AB, BA, CA, BBC}

The first K characters of S are the prefix of S with length K. Write a program which accepts as input a set of primitives and a sequence of constituents and then computes the length of the longest prefix that can be composed from primitives

继续阅读USACO 2.3 Longest Prefix

USACO 2.2 Subset Sums-动态规划

题目描述

For many sets of consecutive integers from 1 through N (1 <= N <= 39), one can partition the set into two sets whose sums are identical.

For example, if N=3, one can partition the set {1, 2, 3} in one way so that the sums of both subsets are identical:

{3} and {1,2}
This counts as a single partitioning (i.e., reversing the order counts as the same partitioning and thus does not increase the count of partitions).

If N=7, there are four ways to partition the set {1, 2, 3, ... 7} so that each partition has the same sum:

  • {1,6,7} and {2,3,4,5}
  • {2,5,7} and {1,3,4,6}
  • {3,4,7} and {1,2,5,6}
  • {1,2,4,7} and {3,5,6}

Given N, your program should print the number of ways a set containing the integers from 1 through N can be partitioned into two sets whose sums are identical. Print 0 if there are no such ways.

Your program must calculate the answer, not look it up from a table.

继续阅读USACO 2.2 Subset Sums-动态规划

「NOIp2003」加分二叉树-记忆化搜索

题目描述

设一个\(n\)个节点的二叉树\(tree\)的中序遍历为\((1,2,3,…,n)\),其中数字1,2,3,…,n为节点编号。每个节点都有一个分数(均为正整数),记第i个节点的分数为\(d_i\),\(tree\)及它的每个子树都有一个加分,任一棵子树\(subtree\)(也包含\(tree\)本身)的加分计算方法如下:

\(subtree\)的左子树的加分\(\times subtree\)的右子树的加分\(+ subtree\)的根的分数。

若某个子树为空,规定其加分为11,叶子的加分就是叶节点本身的分数。不考虑它的空子树。

试求一棵符合中序遍历为\((1,2,3,…,n)\)且加分最高的二叉树\(tree\)。要求输出;

(1)\(tree\)的最高加分

(2)\(tree\)的前序遍历

Links

Luogu P1040

继续阅读「NOIp2003」加分二叉树-记忆化搜索