算法实训题目

算法实训

2011-软件091-092-实验一 .............................................................................................................. 3

最大子段和问题一 ................................................................................................................... 3 最大子段和问题二 ................................................................................................................... 3 最大子段和问题三 ................................................................................................................... 4 2011-软件091-092-实验二 .............................................................................................................. 5

找新朋友 ................................................................................................................................... 5 三个师妹之出题 ....................................................................................................................... 5 Sample Input ....................................................................................................................... 6 Sample Output .................................................................................................................... 6 提示: ......................................................................................................................................... 6 整数分解 ................................................................................................................................... 6 2011-软件091-092-实验三 .............................................................................................................. 7

找新朋友 ................................................................................................................................... 7 三个师妹之出题 ....................................................................................................................... 7 Sample Input ....................................................................................................................... 8 Sample Output .................................................................................................................... 8 提示: ......................................................................................................................................... 8 整数分解 ................................................................................................................................... 8 小学生都会算的A+B问题 ..................................................................................................... 9 幂运算精确值计算问题 ........................................................................................................... 9 字母序列 ................................................................................................................................. 10 2011-软件091-092-实验四 ............................................................................................................ 10

最大子段和问题三 ................................................................................................................. 10 2011-软件091-092-实验五 ............................................................................................................ 11

输油管道问题 ......................................................................................................................... 11 众数问题 ................................................................................................................................. 12 邮局选址问题 ......................................................................................................................... 13 半数集问题 ............................................................................................................................. 14 士兵站队问题 ......................................................................................................................... 14 2011-软件091-092-实验六 ............................................................................................................ 15

输油管道问题 ......................................................................................................................... 15 众数问题 ................................................................................................................................. 16 邮局选址问题 ......................................................................................................................... 17 半数集问题 ............................................................................................................................. 18 士兵站队问题 ......................................................................................................................... 19 有重复元素的排列问题 ......................................................................................................... 20 排列的字典序问题 ................................................................................................................. 21 集合划分问题I ...................................................................................................................... 22 集合划分问题II ..................................................................................................................... 23 半数单集问题 ......................................................................................................................... 24 双色Hanoi塔问题 ................................................................................................................. 25 标准2维表问题 ..................................................................................................................... 26

整数因子分解问题 ................................................................................................................. 27 有向直线2中值问题 ............................................................................................................. 28 数字游戏 ................................................................................................................................. 29 2011-软件091-092-实验七 ............................................................................................................ 30

零件加工问题1 ...................................................................................................................... 30

Sample Input ............................................................................................................. 30 Sample Output .......................................................................................................... 30 零件加工问题2 ...................................................................................................................... 31 2011-软件091-092-实验八 ............................................................................................................ 32

和MM去上课........................................................................................................................ 32 看亚运..................................................................................................................................... 33 零件加工问题2 ...................................................................................................................... 34 2011-软件091-092-实验九 ............................................................................................................ 35

打包......................................................................................................................................... 35 基站安装 ................................................................................................................................. 35 和MM去上课........................................................................................................................ 36 2011-软件091-092-实验十 ............................................................................................................ 37

Huffman Coding ..................................................................................................................... 37 2011-软件091-092-实验十一 ........................................................................................................ 38

部分背包问题 ......................................................................................................................... 38 2011-软件091-092-实验十二 ........................................................................................................ 39

最小生成树 ............................................................................................................................. 39 2011-软件091-092-实验十三 ........................................................................................................ 40

最小生成树 ............................................................................................................................. 40 2011-软件091-092-实验十四 ........................................................................................................ 41

拍照......................................................................................................................................... 41 最大子段和 ............................................................................................................................. 42 最长不下降子序列 ................................................................................................................. 43 2011-软件091-092-实验十五 ........................................................................................................ 44

拍照......................................................................................................................................... 44 数字三角形问题 ..................................................................................................................... 45 最长不下降子序列 ................................................................................................................. 46 2011-软件091-092-实验十六 ........................................................................................................ 47

神农架野人问题 ..................................................................................................................... 47

2011-软件091-092-实验一

最大子段和问题一

Time limit: 1000MS Memory limit: 32768K

Total Submit: 107 Accepted: 56

给你n个整数a1，a2，a3??，an，对于1<=i<=j<=n（1<=n<=1000）；求ai+ai+1+ai+2+??aj的最大值。如果给定的n个整数都为负数，那么规定最大值为零，From=0,To=0。如果和出现相同取i最小，如果i相同取j最大。

输入：输入为两行，第一行为整数n，第二行为n个整数。

输出：输出也有两行，第一行为i和j；第二行为最大的子段和的指，格式参见Sample Output；

Sample Input：

6

2 -5 11 -4 13 -2

Sample Output： From=3,To=5

MaxSum=20

最大子段和问题二

Time limit: 1000MS Memory limit: 32768K

Total Submit: 49 Accepted: 34

给你n个整数a1，a2，a3??，an，对于1<=i<=j<=n（1<=n<=10000）；求ai+ai+1+ai+2+??aj的最大值。如果给定的n个整数都为负数，那么规定最大值为零，From=0,To=0。如果和出现相同取i最小，如果i相同取j最大。

输入：输入为两行，第一行为整数n，第二行为n个整数。

输出：输出也有两行，第一行为i和j；第二行为最大的子段和的指，格式参见Sample Output；

Sample Input：

6

2 -5 11 -4 13 -2

Sample Output： From=3,To=5

MaxSum=20

最大子段和问题三

Time limit: 1000MS Memory limit: 32768K

Total Submit: 12 Accepted: 3

给你n个整数a1，a2，a3??，an，对于1<=i<=j<=n（1<=n<= 100000 ）；求ai+ai+1+ai+2+??aj的最大值。如果给定的n个整数都为负数，那么规定最大值为零，From=0,To=0。如果和出现相同取i最小，如果i相同取j最大。

输入：输入为两行，第一行为整数n，第二行为n个整数。

输出：输出也有两行，第一行为i和j；第二行为最大的子段和的指，格式参见Sample Output；

Sample Input：

6

2 -5 11 -4 13 -2

Sample Output： From=3,To=5

MaxSum=20

2011-软件091-092-实验二

找新朋友

Time limit: 1000MS Memory limit: 32768K

Total Submit: 11 Accepted: 5

新年快到了，“猪头帮协会”准备搞一个聚会，已经知道现有会员N人，把会员从1到N编号，其中会长的号码是N号，凡是和会长是老朋友的，那么该会员的号码肯定和N有大于1的公约数，否则都是新朋友，现在会长想知道究竟有几个新朋友？请你编程序帮会长计算出来。

输入：第一行是测试数据的组数CN（Case number，1），接着有CN行正整数N（1），表示会员人数。

输出：对于每一个N，输出一行新朋友的人数，这样共有CN行输出。

Sample input:

2 25608 24027

Sample output:

7680 16016

三个师妹之出题

Time limit: 1000MS Memory limit: 32768K

Total Submit: 49 Accepted: 31

这一次,那几个师妹给sharp出了一个题目:给定一个正整数N,求1/X+1/Y= 1/N的所有正整数解.sharp哈哈笑了两声,很简单的题目嘛....但是他一听数据范围就傻眼了,N最大可能是999999999!!!聪明的你能帮帮可怜的sharp吗?好让他不那么丢脸.

第一行输入一个正整数M,下面有M行,每一行都是一个正整数N.

输出共M行,每行都是方程解的个数.

Sample Input

2 1 2

Sample Output

1 3

提示:

当N=2时,共有三个解 X=4,Y=4; X=3,Y=6;X=6,Y=3.

整数分解

Time limit: 1000MS Memory limit: 32768K

Total Submit: 20 Accepted: 8

根据数论的有关理论可知，任何大于1的正整数都可唯一地表示为形如(P1^N1)*(P2^N2)*…(Pm^Nm)的形式。请你编程序实现。

输入：第一行是测试数据的组数N(N小于10000)，接着是N行正整数，每行一个，每个正整数不超过32767。

输出：形式是M=(P1^N1)*(P2^N2)*…(Pm^Nm)。 说明：（a）如果幂的值为1，则不用写括号和1次幂；如：15=3*5。

（b）如果N是素数，也不用写括号和1次幂；如：7=7。 （c）如果因子只有一个，也不用写括号；如：27=3^3。

Sample input:

2 25608 24027

Sample output:

25608=(2^3)*3*11*97 24027=3*8009

2011-软件091-092-实验三

找新朋友

Time limit: 1000MS Memory limit: 32768K

Total Submit: 11 Accepted: 10

新年快到了，“猪头帮协会”准备搞一个聚会，已经知道现有会员N人，把会员从1到N编号，其中会长的号码是N号，凡是和会长是老朋友的，那么该会员的号码肯定和N有大于1的公约数，否则都是新朋友，现在会长想知道究竟有几个新朋友？请你编程序帮会长计算出来。

输入：第一行是测试数据的组数CN（Case number，1），接着有CN行正整数N（1），表示会员人数。

输出：对于每一个N，输出一行新朋友的人数，这样共有CN行输出。

Sample input:

2 25608 24027

Sample output:

7680 16016

三个师妹之出题

Time limit: 1000MS Memory limit: 32768K

Total Submit: 16 Accepted: 16

这一次,那几个师妹给sharp出了一个题目:给定一个正整数N,求1/X+1/Y= 1/N的所有正整数解.sharp哈哈笑了两声,很简单的题目嘛....但是他一听数据范围就傻眼了,N最大可能是999999999!!!聪明的你能帮帮可怜的sharp吗?好让他不那么丢脸.

第一行输入一个正整数M,下面有M行,每一行都是一个正整数N. 输出共M行,每行都是方程解的个数.

Sample Input

2 1 2

Sample Output

1 3

提示:

当N=2时,共有三个解 X=4,Y=4; X=3,Y=6;X=6,Y=3.

整数分解

Time limit: 1000MS Memory limit: 32768K

Total Submit: 15 Accepted: 15

根据数论的有关理论可知，任何大于1的正整数都可唯一地表示为形如(P1^N1)*(P2^N2)*…(Pm^Nm)的形式。请你编程序实现。

输入：第一行是测试数据的组数N(N小于10000)，接着是N行正整数，每行一个，每个正整数不超过32767。

输出：形式是M=(P1^N1)*(P2^N2)*…(Pm^Nm)。 说明：（a）如果幂的值为1，则不用写括号和1次幂；如：15=3*5。

（b）如果N是素数，也不用写括号和1次幂；如：7=7。 （c）如果因子只有一个，也不用写括号；如：27=3^3。

Sample input:

2 25608 24027

Sample output:

25608=(2^3)*3*11*97 24027=3*8009

Source:

小学生都会算的A+B问题

Time limit: 1000MS Memory limit: 32768K

Total Submit: 74 Accepted: 61

大家都知道OJ上的最简单的题目就是A+B了，今天我们还是做这个A+B，不过这个数非常大，两个加数的位数不超过100000位，请你写个程序试试吧。

Sample Input： 12345 67890123

Sample Output： 67902468

幂运算精确值计算问题

Time limit: 5000MS Memory limit: 32768K

Total Submit: 89 Accepted: 45

输入两个不超过10000的正整数a、n正整数n，输出a^n的精确结果。

Sample Input 2 3 91 37

Sample Output 8

3051627471597949451463369059654147285577479747909625754790616546501477931

字母序列

Time limit: 1000MS Memory limit: 32768K

Total Submit: 24 Accepted: 19

描述：

考虑由两个字母A和B构成的词所组成的这样一个序列：序列中的第一个词是“A”，第k个词是由第k-1个词经过下面的变换得到：每个A替换为AAB，以及每个B替换为A。容易看出每个词是它的下一个词的起始部分，这些词的起始部分相当于给出了一个字母序列AABAABAAABAABAAAB??。问你第n个字母A在哪一个位置出现？

输入：

N (1<=N<=1000000)

输出：

位置序号。

输入样例： 1000

输出样例： 1414

2011-软件091-092-实验四

最大子段和问题三

Time limit: 1000MS Memory limit: 32768K

Total Submit: 55 Accepted: 31

给你n个整数a1，a2，a3??，an，对于1<=i<=j<=n（1<=n<= 100000 ）；求ai+ai+1+ai+2+??aj的最大值。如果给定的n个整数都为负数，那么规定最大值为零，From=0,To=0。如果和出现相同取i最小，如果i相同取j最大。

输入：输入为两行，第一行为整数n，第二行为n个整数。

输出：输出也有两行，第一行为i和j；第二行为最大的子段和的指，格式参见Sample Output；

Sample Input： 6

2 -5 11 -4 13 -2

Sample Output： From=3,To=5 MaxSum=20

2011-软件091-092-实验五

输油管道问题

Time limit: 1000MS Memory limit: 32768K

Total Submit: 100 Accepted: 53

问题描述：

某石油公司计划建造一条由东向西的主输油管道。该管道要穿过一个有n 口油井的油

田。从每口油井都要有一条输油管道沿最短路经(或南或北)与主管道相连。如果给定n口油

井的位置,即它们的x 坐标（东西向）和y 坐标（南北向）,应如何确定主管道的最优位置,

即使各油井到主管道之间的输油管道长度总和最小的位置?证明可在线性时间内确定主管道 的最优位置。

给定n 口油井的位置,计算各油井到主管道之间的输油管道最小长度总和。 输入的第1 行是油井数n，1<=n<=10000。接下来n 行是 油井的位置，每行2个整数x和y，-10000<=x，y<=10000。 输出油井到主管道之间的输油管道最小长度总和。 Sample Input 5 1 2

2 2 1 3 3 -2 3 3

Sample Output 6

众数问题

Time limit: 5000MS Memory limit: 32768K

Total Submit: 67 Accepted: 35

问题描述：

给定含有n个元素的多重集合S，每个元素在S中出现的次数称为该元素的重数。多重

集S中重数最大的元素称为众数。 例如，S={1，2，2，2，3，5}。 多重集S的众数是2，其重数为3。

对于给定的由n 个自然数组成的多重集S，计算S的众数及其重数。 数据输入:

输入多重集S中元素个数n；接下来的n行中，每行有一个自然数。 结果输出:

输出第1行给出众数，第2 行是重数。 Sample Input 6 1 2 2 2 3 5

Sample Output 2 3

邮局选址问题

Time limit: 1000MS Memory limit: 32768K

Total Submit: 31 Accepted: 26

问题描述：

在一个按照东西和南北方向划分成规整街区的城市里，n 个居民点散乱地分布在不同的

街区中。用x坐标表示东西向，用y 坐标表示南北向。各居民点的位置可以由坐标(x,y)表示。

街区中任意2 点(x1,y1)和(x2,y2)之间的距离可以用数值| x1- x2|+| y1- y2|度量。

居民们希望在城市中选择建立邮局的最佳位置，使n个居民点到邮局的距离总和最小。

算法设计：

给定n 个居民点的位置，计算n 个居民点到邮局的距离总和的最小值。 数据输入：

输入的第1 行是居民点数n，1<=n<=10000。接下来n 行

是居民点的位置，每行2 个整数x 和y，-10000<=x，y<=10000。 结果输出:

输出的第1 行中的数是n 个居民点到邮局的距离总和的最小值。 Sample Input 5 1 2 2 2 1 3 3 -2 3 3

Sample Output 10

半数集问题

Time limit: 1000MS Memory limit: 32768K

Total Submit: 22 Accepted: 1

问题描述：

给定一个自然数n，由n 开始可以依次产生半数集set(n)中的数如下。 (1) n∈set(n)；

(2) 在n 的左边加上一个自然数，但该自然数不能超过最近添加的数的一半； (3) 按此规则进行处理，直到不能再添加自然数为止。

例如，set(6)={6,16,26,126,36,136}。半数集set(6)中有6 个元素。 注意半数集是多重集。

算法设计：

对于给定的自然数n，计算半数集set(n)中的元素个数。 数据输入：

输入一个整数n。(0

结果输出:

输出半数集set(n)中的元素个数。 Sample Input 6

Sample Output 6

士兵站队问题

Time limit: 1000MS Memory limit: 32768K

Total Submit: 14 Accepted: 8

问题描述：

在一个划分成网格的操场上，n个士兵散乱地站在网格点上。网格点由整数坐标(x,y)表

示。士兵们可以沿网格边上、下、左、右移动一步，但在同一时刻任一网格点上只能有一名

士兵。按照军官的命令，士兵们要整齐地列成一个水平队列，即排列成

(x,y),(x+1,y),…,(x+n-1,y)。如何选择x 和y的值才能使士兵们以最少的总移动步数排成一列。

算法设计：

计算使所有士兵排成一行需要的最少移动步数。

数据输入：

输入士兵数n，1<=n<=10000。接下来n 行是

士兵的初始位置，每行2 个整数x 和y，-10000<=x，y<=10000。 结果输出:

输出的第1 行中的数是士兵排成一行需要的最少移动步数。 Sample Input 5 1 2 2 2 1 3 3 -2 3 3

Sample Output 8

2011-软件091-092-实验六

输油管道问题

Time limit: 1000MS Memory limit: 32768K

Total Submit: 9 Accepted: 5

问题描述：

某石油公司计划建造一条由东向西的主输油管道。该管道要穿过一个有n 口油井的油

田。从每口油井都要有一条输油管道沿最短路经(或南或北)与主管道相连。如果给定n口油

井的位置,即它们的x 坐标（东西向）和y 坐标（南北向）,应如何确定主管道的最优位置,

即使各油井到主管道之间的输油管道长度总和最小的位置?证明可在线性时间内确定主管道 的最优位置。

给定n 口油井的位置,计算各油井到主管道之间的输油管道最小长度总和。 输入的第1 行是油井数n，1<=n<=10000。接下来n 行是 油井的位置，每行2个整数x和y，-10000<=x，y<=10000。 输出油井到主管道之间的输油管道最小长度总和。 Sample Input 5 1 2 2 2 1 3 3 -2 3 3

Sample Output 6

众数问题

Time limit: 5000MS Memory limit: 32768K

Total Submit: 16 Accepted: 11

问题描述：

给定含有n个元素的多重集合S，每个元素在S中出现的次数称为该元素的重数。多重

集S中重数最大的元素称为众数。 例如，S={1，2，2，2，3，5}。 多重集S的众数是2，其重数为3。

对于给定的由n 个自然数组成的多重集S，计算S的众数及其重数。 数据输入:

输入多重集S中元素个数n；接下来的n行中，每行有一个自然数。 结果输出:

输出第1行给出众数，第2 行是重数。 Sample Input 6 1 2 2 2 3 5

Sample Output 2 3

Source:

邮局选址问题

Time limit: 1000MS Memory limit: 32768K

Total Submit: 11 Accepted: 10

问题描述：

在一个按照东西和南北方向划分成规整街区的城市里，n 个居民点散乱地分布在不同的

街区中。用x坐标表示东西向，用y 坐标表示南北向。各居民点的位置可以由坐标(x,y)表示。

街区中任意2 点(x1,y1)和(x2,y2)之间的距离可以用数值| x1- x2|+| y1- y2|度量。

居民们希望在城市中选择建立邮局的最佳位置，使n个居民点到邮局的距离总和最小。

算法设计：

给定n 个居民点的位置，计算n 个居民点到邮局的距离总和的最小值。 数据输入：

输入的第1 行是居民点数n，1<=n<=10000。接下来n 行

是居民点的位置，每行2 个整数x 和y，-10000<=x，y<=10000。 结果输出:

输出的第1 行中的数是n 个居民点到邮局的距离总和的最小值。 Sample Input 5 1 2 2 2 1 3 3 -2 3 3

Sample Output 10

半数集问题

Time limit: 1000MS Memory limit: 32768K

Total Submit: 20 Accepted: 5

问题描述：

给定一个自然数n，由n 开始可以依次产生半数集set(n)中的数如下。 (1) n∈set(n)；

(2) 在n 的左边加上一个自然数，但该自然数不能超过最近添加的数的一半； (3) 按此规则进行处理，直到不能再添加自然数为止。

例如，set(6)={6,16,26,126,36,136}。半数集set(6)中有6 个元素。 注意半数集是多重集。

算法设计：

对于给定的自然数n，计算半数集set(n)中的元素个数。 数据输入：

输入一个整数n。(0

结果输出:

输出半数集set(n)中的元素个数。 Sample Input 6

Sample Output 6

士兵站队问题

Time limit: 1000MS Memory limit: 32768K

Total Submit: 16 Accepted: 7

问题描述：

在一个划分成网格的操场上，n个士兵散乱地站在网格点上。网格点由整数坐标(x,y)表

示。士兵们可以沿网格边上、下、左、右移动一步，但在同一时刻任一网格点上只能有一名

士兵。按照军官的命令，士兵们要整齐地列成一个水平队列，即排列成

(x,y),(x+1,y),…,(x+n-1,y)。如何选择x 和y的值才能使士兵们以最少的总移动步数排成一列。

算法设计：

计算使所有士兵排成一行需要的最少移动步数。

数据输入：

输入士兵数n，1<=n<=10000。接下来n 行是

士兵的初始位置，每行2 个整数x 和y，-10000<=x，y<=10000。

结果输出:

输出的第1 行中的数是士兵排成一行需要的最少移动步数。 Sample Input 5 1 2 2 2 1 3 3 -2 3 3

Sample Output 8

有重复元素的排列问题

Time limit: 1000MS Memory limit: 32768K

Total Submit: 13 Accepted: 3

问题描述：

?设R={ r1 , r2 ,r3 }是要进行排列的n个元素。其中元素n r1 , r2 ... , rn 可能相同。试设计

一个算法，列出R的所有不同排列。

算法设计：

给定n以及待排列的n个元素。计算出这n个元素的所有不同排列。 数据输入：

输入的第1 行是元素个数n，1<=n<=500。接下来的1 行 是待排列的n个元素。

结果输出:

将计算出的n 个元素的所有不同排列输出（按字典序从小到大）。下一 行中的数是

排列总数。 Sample Input

4 aacc

Sample Output aacc acac acca caac caca ccaa 6

排列的字典序问题

Time limit: 1000MS Memory limit: 32768K

Total Submit: 18 Accepted: 16

问题描述：

, n?n个元素{1,2, }有n!个不同的排列。将这n!个排列按字典序排列，并编号为0，1，…，

n!-1。每个排列的编号为其字典序值。例如，当n=3时，6 个不同排列的字典序值如下：

字典序值 0 1 2 3 4 5 排列 123 132 213 231 312 321

算法设计：

, n }的一个排列，计算出这个排列的字典序值，以及按字典?给定n以及n个元素{1,2,

序排列的下一个排列。

数据输入：

输出元素个数n。接下来的1 行是n个元素 , n }的一个排列。?{1,2,

结果输出:

将计算出的排列的字典序值和按字典序排列的下一个排列输出。第一行是字典序值，第2行是按字典序排列的下一个排列。 Sample Input 8

2 6 4 5 8 1 7 3 Sample Output 8227

2 6 4 5 8 3 1 7

集合划分问题I

Time limit: 1000MS Memory limit: 32768K

Total Submit: 14 Accepted: 2

问题描述：

, n }可以划分为若干个非空子集。例如，当n=4 时，集合{1，2，?n个元素的集合{1,2,

3，4}可以划分为15 个不同的非空子集如下： {{1}，{2}，{3}，{4}}， {{1，2}，{3}，{4}}， {{1，3}，{2}，{4}}， {{1，4}，{2}，{3}}， {{2，3}，{1}，{4}}， {{2，4}，{1}，{3}}， {{3，4}，{1}，{2}}， {{1，2}，{3，4}}， {{1，3}，{2，4}}， {{1，4}，{2，3}}， {{1，2，3}，{4}}， {{1，2，4}，{3}}， {{1，3，4}，{2}}， {{2，3，4}，{1}}， {{1，2，3，4}}

算法设计：

, n }可以划分为多少个不同的非空子集。?给定正整数n，计算出n个元素的集合{1,2,

数据输入：

输入数据第1 行是元素个数n。 结果输出:

将计算出的不同的非空子集数输出. Sample input 5

Sample output 52

集合划分问题II

Time limit: 1000MS Memory limit: 32768K

Total Submit: 8 Accepted: 5

问题描述：

, n }可以划分为若干个非空子集。例如，当n=4 时，集合{1，2，?n个元素的集合{1,2,

3，4}可以划分为15 个不同的非空子集如下： {{1}，{2}，{3}，{4}}， {{1，2}，{3}，{4}}， {{1，3}，{2}，{4}}， {{1，4}，{2}，{3}}， {{2，3}，{1}，{4}}， {{2，4}，{1}，{3}}， {{3，4}，{1}，{2}}， {{1，2}，{3，4}}， {{1，3}，{2，4}}， {{1，4}，{2，3}}， {{1，2，3}，{4}}， {{1，2，4}，{3}}， {{1，3，4}，{2}}，

{{2，3，4}，{1}}， {{1，2，3，4}}

其中，集合{{1，2，3，4}}由1 个子集组成；集合{{1，2}，{3，4}}，{{1，3}，{2，

4}}，{{1，4}，{2，3}}，{{1，2，3}，{4}}，{{1，2，4}，{3}}，{{1，3，4}，{2}}，{{2，

3，4}，{1}}由2 个子集组成；集合{{1，2}，{3}，{4}}，{{1，3}，{2}，{4}}，{{1，4}，

{2}，{3}}，{{2，3}，{1}，{4}}，{{2，4}，{1}，{3}}，{{3，4}，{1}，{2}}由3 个子集组

成；集合{{1}，{2}，{3}，{4}}由4 个子集组成。

算法设计：

, n }可以划分为多少个不同的由m?给定正整数n 和m，计算出n 个元素的集合{1,2,

个非空子集组成的集合。

数据输入：

输入的第1 行是元素个数n和非空子集数m。 结果输出:

将计算出的不同的由m个非空子集组成的集合数输出。 Sample input 4 3

Sample output 6

半数单集问题

Time limit: 1000MS Memory limit: 32768K

Total Submit: 11 Accepted: 4

问题描述：

给定一个自然数n，由n 开始可以依次产生半数集set(n)中的数如下。 (1) n∈set(n)；

(2) 在n 的左边加上一个自然数，但该自然数不能超过最近添加的数的一半；

(3) 按此规则进行处理，直到不能再添加自然数为止。

例如，set(6)={6,16,26,126,36,136}。半数集set(6)中有6 个元素。 注意半数集不是多重集。集合中已经有的元素不再添加到集合中。 算法设计：

对于给定的自然数n，计算半数集set(n)中的元素个数。 数据输入： 给出整数n。(0

结果输出:

给出半数集set(n)中的元素个数。 Sample input 6

Sample output 6

双色Hanoi塔问题

Time limit: 1000MS Memory limit: 32768K

Total Submit: 44 Accepted: 22

问题描述：

设A、B、C是3 个塔座。开始时，在塔座A上有一叠共n个圆盘，这些圆盘自下而上，

由大到小地叠在一起。各圆盘从小到大编号为1，2，……，n，奇数号圆盘着红色，偶数号

圆盘着蓝色，如图所示。现要求将塔座A 上的这一叠圆盘移到塔座B 上，并仍按同样顺序

叠置。在移动圆盘时应遵守以下移动规则： 规则(1)：每次只能移动1 个圆盘；

规则(2)：任何时刻都不允许将较大的圆盘压在较小的圆盘之上； 规则(3)：任何时刻都不允许将同色圆盘叠在一起；

规则(4)：在满足移动规则(1)-(3)的前提下，可将圆盘移至A，B，C中任一塔座上。

试设计一个算法，用最少的移动次数将塔座A 上的n 个圆盘移到塔座B 上，并仍按同

样顺序叠置。

算法设计：

对于给定的正整数n，计算最优移动方案。 数据输入：

输入数据。第1 行是给定的正整数n。

结果输出:

文件的每一行由一个正整数k 和2 个字符c1 和c2组成，表示将第k个圆盘从塔座c1移到塔座c2上。（输出字典序最小） Sample input 3

Sample output 1 A B 2 A C 1 B C 3 A B 1 C A 2 C B 1 A B

标准2维表问题

Time limit: 1000MS Memory limit: 32768K

Total Submit: 9 Accepted: 6

问题描述：

设n 是一个正整数。2′n 的标准2 维表是由正整数1，2，…，2n 组成的2′n 数组，该

数组的每行从左到右递增，每列从上到下递增。2′n的标准2 维表全体记为Tab(n)。例如，

当n=3时Tab(3)如下：

1 2 3 4 5 1 2 3 1 2 4 1 2 5 1 3 4 1 3 5 4 5 6 3 5 6 3 4 6 2 5 6 2 4 6

算法设计：

给定正整数n，计算Tab(n)中2′n的标准2 维表的个数。 数据输入：

给出输入数据。第一行有1 个正整数n。

结果输出:

将计算出的Tab(n)中2′n的标准2 维表的个数输出. Sample input 3

Sample output 5

整数因子分解问题

Time limit: 1000MS Memory limit: 32768K

Total Submit: 14 Accepted: 1

问题描述：

大于1 的正整数n可以分解为：n=x1*x2*…*xm。 例如，当n=12 时，共有8 种不同的分解式： 12=12； 12=6*2； 12=4*3； 12=3*4； 12=3*2*2； 12=2*6； 12=2*3*2； 12=2*2*3。

算法设计：

对于给定的正整数n，计算n共有多少种不同的分解式。

数据输入：

给出输入数据。第一行有1 个正整数n (1≤n≤1000)。 结果输出:

将计算出的不同的分解式数输出. Sample input 12

Sample output 8

有向直线2中值问题

Time limit: 1000MS Memory limit: 32768K

Total Submit: 0 Accepted: 0

问题描述：

给定一条有向直线L以及L上的n+1个点x0 < x1 都有一个权w(xi )；每条有向边(xi ,xi-1 )也都有一个非负边长d(xi,xi-1 )。有向直线L上的 每个点xi可以看作客户，其服务需求量为w(xi)。每条边(xi,xi-1)的边长d(xi,xi-1)可以看

作运输费用。如果在点xi处未设置服务机构，则将点xi处的服务需求沿有向边转移到点xj

处服务机构需付出的服务转移费用为w(xi)*d(xi,xj)。在点x0处已设置了服务机构，现在

要在直线L上增设2处服务机构，使得整体服务转移费用最小。

算法设计：

对于给定的有向直线L，计算在直线L上增设2 处服务机构的最小服务转移费用。

数据输入：

给出输入数据。第1 行有1 个正整数n，表示有向直线L上除了点x0外 还有n个点x0别表示w(xn-i-1) n-i-1 w x 和d(xn-i-1,xn-i-2)。 结果输出:

将计算的最小服务转移费用输出. Sample input

9 1 2 2 1 3 3 1 1 3 2 1 6 2 1 1 2 1 1

Sample output 26

数字游戏

Time limit: 1000MS Memory limit: 32768K

Total Submit: 49 Accepted: 36

大家小的时候应该都玩过数字游戏吧，那一张张小卡片每次都会给我们带来意外的惊喜，那么现在让我们再玩一下吧。游戏规则很简单，就是给出一个数(小于100000000)，将他们的各位数字相乘得积，直到最后变成一位数字（在本题中，所有的测试数据最后都能变成一位数），将这个一位数字输出即可。规则很简单吧，格式就如输入举例的，那让我们试试吧。

Sample Input: 123 9999 5656 1234 1111

Sample Output: 6 0 0

8 1

2011-软件091-092-实验七

零件加工问题1

Time limit: 1000MS Memory limit: 32768K

Total Submit: 98 Accepted: 57

有个国有中型企业，接到一批需要加工零件的订单，员工们非常高兴，可是高兴之后却发现问题了，原来这家企业能够加工这批零件的机床有限，如果仅仅为了这批加工任务而新添机床的话，那么既不合算也不必要，因为加工完这批零件后很可能这些机床又要闲置起来，所以大批量购买肯定不行，但这批订单又必须要完成，那么这么办呢？很想请你帮忙设计一个加工任务的顺序，使得完成这批订单所需要使用的机床数量最少。

假定对于待加工的第i个零件，给你两个非负整数Si，Ei，其中Si表示加工开始的时间，Ei表示加工结束的时间，由于受到客观条件的制约，这开始和结束的时间限制必须要遵守。当然在某个时刻一台机器只能加工一个零件。 本问题有多组测试数据，对于每组测试数据，输入的第一行是需要加工的零件个数N，接着是N行[Si，Ei]，其中Si，Ei如上所述，输出只有一行，就是完成加工任务所需要的最少机床数。

Sample Input

7 [1,3] [1,4] [2,5] [3,7] [4,7] [6,9] [7,8]

Sample Output

3

Source:

零件加工问题2

Time limit: 5000MS Memory limit: 32768K

Total Submit: 18 Accepted: 1

有个国有中型企业，接到一批需要加工零件的订单，员工们非常高兴，工厂领导为了鼓励员工尽快地完成加工任务，出台了奖励政策：“如果在保证质量要求的前提下，每完成一个零件加工任务，都有相同数量的奖金！”。所以所有员工都希望加工尽量多的零件，以便拿到更多的奖金。现在请你帮忙，怎样加工才能在一台机床上加工最多的零件。

假定对于待加工的第i个零件，给你两个非负整数Si，Ei，其中Si表示加工开始的时间，其中Ei表示加工结束的时间，由于受到客观条件的制约，这开始和结束的时间限制必须要遵守。当然在某个时刻一台机器只能加工一个零件。

本问题有多组测试数据，对于每组测试数据，输入的第一行是三个非负的整数N（0<=N<=150），TB，TE（0<=TB<=TE<=10000），其中N表示需要加工的零件个数，TB和TE分别表示给定的时间范围，即要求在TB和TE的时间内加工尽量多的零件。接着是N行[Si，Ei]，其中Si，Ei如上所述（0<=Si<=Ei<=10000），而且规定零件编号顺序就是输入的顺序。输出只有一行是能够加工的最多的零件数。

Sample Input： 7 0 10 [4,7] [2,5] [1,3] [7,8] [3,7] [1,4] [6,9]

Sample Output：

3

2011-软件091-092-实验八

和MM去上课

Time limit: 1000MS Memory limit: 32768K

Total Submit: 1 Accepted: 0

北大的很多研究生住在万柳校区，他们每天要坐公交或骑车去4.5公里远的燕园上课。由于北京的交通很烂（我想也是很烂）,许多同学选择骑车去上课。 查理同学和其他同学的骑车习惯不同，其他同学都是以固定的速度骑行，查理则是跟某个MM一起，这样就不会觉得无聊。当查理出发的时候，他会寻找一个MM作伴去燕园。如果找到了PLMM，他就会和她一起，否则就继续物色。在去燕园的路上，如果有某个MM速度比较快，超过他了，他就会丢下身边的MM去追那个更快的MM，然后和她一起去燕园。 我们假设查理出发的时刻为0，现给出很多MM的出发时间和速度，你来计算一下查理什么时候能到燕园呢？

Input

包含多组数据。每组数据第一行以个整数N(1<=N<=10000)，代表MM数，N=0时退出，接下来有N行，每行代表一个MM的骑行信息。格式：Vi Ti。0 < Vi <= 40，代表骑车速度(km/h)，Ti是该MM的出发时间（s），Ti可能小于0。

Output

每行输出代表一组数据。输出查理到达燕园的时间，不满1秒的按1秒算。

Sample Input

4 20 0 25 -155 27 190 30 240 2 21 0 22 34 0

Sample Output

780 771

看亚运

Time limit: 1000MS Memory limit: 32768K

Total Submit: 53 Accepted: 38

亚运会已经开始好几天了，估计很多热爱运动的ACMer也会抛开电脑，奔向电视了。

亚运会不是每年都有的，所以一定想看尽量多的完整的比赛，当然，作为新时代的好青年，你一定还会看一些其它的节目，比如新闻联播（永远不要忘记关心国家大事）、非常6+7、我爱记歌词，以及非诚勿扰等等，假设你已经知道了所有你喜欢看的电视节目的转播时间表，你会合理安排吗？（目标是能看尽量多的完整节目）。 Input

输入数据包含多个测试实例，每个测试实例的第一行只有一个整数

n(n<=100)，表示你喜欢看的节目的总数，然后是n行数据，每行包括两个数据Ti_s,Ti_e (1<=i<=n)，分别表示第i个节目的开始和结束时间，为了简化问题，每个时间都用一个正整数表示。n=0表示输入结束，不做处理。

Output

对于每个测试实例，输出能完整看到的电视节目的个数，每个测试实例的输出占一行。

Sample Input 12 1 3 3 4 0 7 3 8 15 19 15 20 10 15 8 18 6 12 5 10 4 14 2 9

0

Sample Output

5

零件加工问题2

Time limit: 1000MS Memory limit: 32768K

Total Submit: 129 Accepted: 65

有个国有中型企业，接到一批需要加工零件的订单，员工们非常高兴，工厂领导为了鼓励员工尽快地完成加工任务，出台了奖励政策：“如果在保证质量要求的前提下，每完成一个零件加工任务，都有相同数量的奖金！”。所以所有员工都希望加工尽量多的零件，以便拿到更多的奖金。现在请你帮忙，怎样加工才能在一台机床上加工最多的零件。

假定对于待加工的第i个零件，给你两个非负整数Si，Ei，其中Si表示加工开始的时间，其中Ei表示加工结束的时间，由于受到客观条件的制约，这开始和结束的时间限制必须要遵守。当然在某个时刻一台机器只能加工一个零件。

本问题有多组测试数据，对于每组测试数据，输入的第一行是三个非负的整数N（0<=N<=150），TB，TE（0<=TB<=TE<=10000），其中N表示需要加工的零件个数，TB和TE分别表示给定的时间范围，即要求在TB和TE的时间内加工尽量多的零件。接着是N行[Si，Ei]，其中Si，Ei如上所述（0<=Si<=Ei<=10000），而且规定零件编号顺序就是输入的顺序。输出只有一行是能够加工的最多的零件数。

Sample Input： 7 0 10 [4,7] [2,5] [1,3] [7,8] [3,7] [1,4] [6,9]

Sample Output： 3

2011-软件091-092-实验九

打包

Time limit: 1000MS Memory limit: 32768K

Total Submit: 1 Accepted: 0

一个工厂把产品包装在正方形的盒子里，尺寸有1×1，2×2，3×3，4×4，5×5，6×6六种，高度为h。产品最终总是捆扎成高度为h的6×6的包裹送到客户手里，因为客户希望包裹越少越好。请你编写一个程序计算最少需要多少包裹才能把客户买的产品送完。

Input

输入包含多组数据。每组数据有一行，包含6个整数，用空格隔开，分别代表1×1的产品、2×2的产品……6×6的产品的个数。输入6个0时退出。

Output

每组数据输出一行，输出最少需要的包裹数。

Sample Input 0 0 4 0 0 1 7 5 1 0 0 0 0 0 0 0 0 0

Sample Output 2 1

基站安装

Time limit: 1000MS Memory limit: 32768K

Total Submit: 101 Accepted: 60

从前有一个一望无际的海滩，海滩后面是陆地，前面是广阔的大海。海中有很多小岛（可以用一个点表示）。现在海滩上需要安装一些基站（海滩上的任意位

置）这样岛上的居民就能用手机通话了，所有的基站的覆盖距离都是d，在距离d范围内的小岛都能收到基站发送的信号。

我们用笛卡尔坐标系来表示这个问题，定义x轴为海滩，x轴上方是大海，下方是陆地。现给出每个小岛的位置（用x-y坐标表示）和基站的覆盖范围d，你的任务就是写一个程序，计算出可以覆盖所有的小岛，至少需要在海滩上安装多少基站？

Input

输入包含多组数据。对每组数据，第一行包含两个整数n（1 <= n <= 1000）和d，n代表小岛数量，d代表基站的覆盖距离。接下来有n行，每行包含两个整数，表示小岛的位置坐标。输入n=0,d=0时退出。 Output

对每组数据，输出包含数据组数，格式如sample，后跟最少需要安装的基站数，如果无解，输出-1。 Sample Input 3 2 1 2 -3 1 2 1 1 2 0 2 1 -2 0 2 0 0

Sample Output Case 1: 2 Case 2: 1 Case 3: -1

和MM去上课

Time limit: 1000MS Memory limit: 32768K

Total Submit: 31 Accepted: 12

北大的很多研究生住在万柳校区，他们每天要坐公交或骑车去4.5公里远的燕园上课。由于北京的交通很烂（我想也是很烂）,许多同学选择骑车去上课。 查理同学和其他同学的骑车习惯不同，其他同学都是以固定的速度骑行，查理则是跟某个MM一起，这样就不会觉得无聊。当查理出发的时候，他会寻找一个MM作伴去燕园。如果找到了PLMM，他就会和她一起，否则就继续物色。在去燕园的路上，如果有某个MM速度比较快，超过他了，他就会丢下身边的MM去追那个更快的MM，然后和她一起去燕园。 我们假设查理出发的时刻为0，现给出很多MM的出发时间和速度，你来计算一下查理什么时候能到燕园呢？

Input

包含多组数据。每组数据第一行以个整数N(1<=N<=10000)，代表MM数，N=0时退出，接下来有N行，每行代表一个MM的骑行信息。格式：Vi Ti。0 < Vi <= 40，代表骑车速度(km/h)，Ti是该MM的出发时间（s），Ti可能小于0。

Output

每行输出代表一组数据。输出查理到达燕园的时间，不满1秒的按1秒算。

Sample Input

4 20 0 25 -155 27 190 30 240 2 21 0 22 34 0

Sample Output

780 771

2011-软件091-092-实验十

Huffman Coding

Time limit: 1000MS Memory limit: 32768K

Total Submit: 58 Accepted: 55

给定一个数字N，代表有N种不同的字符，已知每种字符的出现次数，现在要求你设计一种编码，使得任意一个编码都不是另外一个编码的前缀，并且使得这些字符经过编码压缩之后的总长度最小；

输入

一个数字N 代表有多少种不同的字符(0<=N<=1000) N个数字 每个数字代表一种字符的出现次数 输出

一个数字，代表总的编码长度

Sample Input 5 1 2 3 4 5 3 3 8 8

Sample Output 33 30

HINT: 比如第2组数据 A字符出现3次，B字符出现8次，C字符出现8次 则A编码可以为00 B为01 C为1 总长度为 3*2 + 8*2 + 8*1 =30

2011-软件091-092-实验十一

部分背包问题

Time limit: 3000MS Memory limit: 32768K

Total Submit: 76 Accepted: 58

一个商人带着一个能装M千克的背包去乡下收购货物，准备将这些货物卖到城里获利。现有N种货源，且知第i种货物有Wi千克，可获利Pi元。请你设计一个程序以帮助这个商人收购货物，使得他能获利最高。 Input

第一行输入一个整数 T(1 <= T<= 64), 表示测试数据数量。

每组CASE三行，第一行包含两个整数N(1 <= N <= 1024),M(1 <= M <= 4096)，表示资源的数量以及背包的容量。

第二行包含N个整数Wi(1 <= Wi <= 4096) 表示第i种货物有Wi千克。 第三行包含N个整数Pi(1 <= Pi <= 10086) 表示第i种货物可获利Pi元。 Output

对于每组Case， 输出一行:\表示当前是第几组CASE， Y表示最大获利。 Sample Input 2 3 5 1 2 3 3 2 1 7 4

1 2 3 2 1 1 4 1 2 10 3 2 1 100 Sample Output Case #1: 5 Case #2: 100

Source:

2011-软件091-092-实验十二

最小生成树

Time limit: 1000MS Memory limit: 32768K

Total Submit: 66 Accepted: 62

在一张图上有N个点，点与点之间的连接的花费都已经告诉你了，请你设计一下，如果解决这个“最小生成树”的问题。

输入

首先输入一个数字N（0〈=N〈=100）

然后输入一个N*N的矩阵 其中第i行第j列的数字k表示从点i到点j需要的花费。

输出

一个数字，最少需要多少花费才能使得整张图任意两点都直接或者间接连通（也就是最小生成树的权） Sample Input 5

0 41 67 34 0 41 0 69 24 78 67 69 0 58 62 34 24 58 0 64 0 78 62 64 0 0 2 0 1 1 0

Sample Output 116 0 1

2011-软件091-092-实验十三

最小生成树

Time limit: 1000MS Memory limit: 32768K

Total Submit: 76 Accepted: 60

本文来源：https://www.bwwdw.com/article/q7m3.html