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 Party Lamps

题目描述

To brighten up the gala dinner of the IOI'98 we have a set of N (10 <= N <= 100) colored lamps numbered from 1 to N.

The lamps are connected to four buttons:

  • Button 1: When this button is pressed, all the lamps change their state: those that are ON are turned OFF and those that are OFF are turned ON.
  • Button 2: Changes the state of all the odd numbered lamps.
  • Button 3: Changes the state of all the even numbered lamps.
  • Button 4: Changes the state of the lamps whose number is of the form 3xK+1 (with K>=0), i.e., 1,4,7,...

A counter C records the total number of button presses.

When the party starts, all the lamps are ON and the counter C is set to zero.

You are given the value of counter C (0 <= C <= 10000) and the final state of some of the lamps after some operations have been executed. Write a program to determine all the possible final configurations of the N lamps that are consistent with the given information, without repetitions.

继续阅读USACO 2.2 Party Lamps

USACO 2.2 Runaround Numbers-模拟

题目描述

Runaround numbers are integers with unique digits, none of which is zero (e.g., 81362) that also have an interesting property, exemplified by this demonstration:

  • If you start at the left digit (8 in our number) and count that number of digits to the right (wrapping back to the first digit when no digits on the right are available), you'll end up at a new digit (a number which does not end up at a new digit is not a Runaround Number). Consider: 8 1 3 6 2 which cycles through eight digits: 1 3 6 2 8 1 3 6 so the next digit is 6.
  • Repeat this cycle (this time for the six counts designed by the `6') and you should end on a new digit: 2 8 1 3 6 2, namely 2.
  • Repeat again (two digits this time): 8 1
  • Continue again (one digit this time): 3
  • One more time: 6 2 8 and you have ended up back where you started, after touching each digit once. If you don't end up back where you started after touching each digit once, your number is not a Runaround number.

Given a number M (that has anywhere from 1 through 9 digits), find and print the next runaround number higher than M, which will always fit into an unsigned long integer for the given test data.

继续阅读USACO 2.2 Runaround Numbers-模拟

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-动态规划

USACO 2.1 The Castle-漫水填充

题目描述

In a stroke of luck almost beyond imagination, Farmer John was sent a ticket to the Irish Sweepstakes (really a lottery) for his birthday. This ticket turned out to have only the winning number for the lottery! Farmer John won a fabulous castle in the Irish countryside.

Bragging rights being what they are in Wisconsin, Farmer John wished to tell his cows all about the castle. He wanted to know how many rooms it has and how big the largest room was. In fact, he wants to take out a single wall to make an even bigger room.

Your task is to help Farmer John know the exact room count and sizes.

The castle floorplan is divided into M (wide) by N (1 <=M,N<=50) square modules. Each such module can have between zero and four walls. Castles always have walls on their "outer edges" to keep out the wind and rain.

Consider this annotated floorplan of a castle:

     1   2   3   4   5   6   7
   #############################
 1 #   |   #   |   #   |   |   #
   #####---#####---#---#####---#   
 2 #   #   |   #   #   #   #   #
   #---#####---#####---#####---#
 3 #   |   |   #   #   #   #   #   
   #---#########---#####---#---#
 4 # ->#   |   |   |   |   #   #   
   ############################# 

#  = Wall     -,|  = No wall
-> = Points to the wall to remove to
     make the largest possible new room

By way of example, this castle sits on a 7 x 4 base. A "room" includes any set of connected "squares" in the floor plan. This floorplan contains five rooms (whose sizes are 9, 7, 3, 1, and 8 in no particular order).

Removing the wall marked by the arrow merges a pair of rooms to make the largest possible room that can be made by removing a single wall.

The castle always has at least two rooms and always has a wall that can be removed.

继续阅读USACO 2.1 The Castle-漫水填充

「NOIp2018」赛道修建-贪心+二分

题目描述

C 城将要举办一系列的赛车比赛。在比赛前,需要在城内修建 \(m\) 条赛道。

C 城一共有 \(n\) 个路口,这些路口编号为 \(1,2,…,n\)有 \(n−1\) 条适合于修建赛道的双向通行的道路,每条道路连接着两个路口。其中,第 \(i\) 条道路连接的两个路口编号为 \(a_i\) 和 \(b_i\),该道路的长度为 \(l_i\)。借助这 \(n-1\) 条道路,从任何一个路口出发都能到达其他所有的路口。

一条赛道是一组互不相同的道路 \(e_1,e_2,…,e_k\)满足可以从某个路口出发,依次经过 道路 \(e_1,e_2,…,e_k\)(每条道路经过一次,不允许调头)到达另一个路口。一条赛道的长度等于经过的各道路的长度之和。为保证安全,要求每条道路至多被一条赛道经过。

目前赛道修建的方案尚未确定。你的任务是设计一种赛道修建的方案,使得修建的 \(m\) 条赛道中长度最小的赛道长度最大(即 \(m\) 条赛道中最短赛道的长度尽可能大)

Links

Luogu P5021

继续阅读「NOIp2018」赛道修建-贪心+二分

「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」加分二叉树-记忆化搜索

「SHOI2015」自动刷题机-二分

题目描述

SHTSC发明了一种自动刷题机,它刷题的方式非常简单:首先会瞬间得出题目的正确做法,然后开始写程序。每秒,自动刷题机的代码生成模块会有两种可能的结果:

1.写了\(x\)行代码

2.心情不好,删掉了之前写的\(y\)行代码。(如果\(y\)大于当前代码长度则相当于全部删除。)

对于一个 OJ,存在某个固定的长度\(n>0\),一旦自动刷题机在某秒结束时积累了大于等于\(n\)行的代码,它就会自动提交并 AC 此题,然后新建一个文件(即弃置之前的所有代码)并开始写下一题。SHTSC 在某个 OJ 上跑了一天的自动刷题机,得到了很多条关于写代码的日志信息。他突然发现自己没有记录这个 OJ 的\(n\)究竟是多少。所幸他通过自己在 OJ 上的 Rank 知道了自动刷题机一共切了\(k\)道题,希望你计算\(n\)可能的最小值和最大值。

Links

Luogu P4343

继续阅读「SHOI2015」自动刷题机-二分