蓝桥杯所有题目

1.

A+B问题

问题描述

输入A、B，输出A+B。

说明：在“问题描述”这部分，会给出试题的意思，以及所要求的目标。

输入格式

输入的第一行包括两个整数，由空格分隔，分别表示A、B。

输出格式

输出一行，包括一个整数，表示A+B的值。

样例输入

12 45

样例输出

57

数据规模与约定

-10000 <= A, B <= 10000。

2.

序列求和

问题描述

求1+2+3+...+n的值。

输入格式

输入包括一个整数n。

输出格式

输出一行，包括一个整数，表示1+2+3+...+n的值。

样例输入

4

样例输出

10

样例输入

100

样例输出

5050

数据规模与约定

1 <= n <= 1,000,000,000

3.

圆的面积

问题描述

给定圆的半径r，求圆的面积。

输入格式

输入包含一个整数r，表示圆的半径。

输出格式

输出一行，包含一个实数，四舍五入保留小数点后7位，表示圆的面积。

样例输入

4

样例输出

50.2654825

数据规模与约定

1 <= r <= 10000。

提示

本题对精度要求较高，请注意π的值应该取较精确的值。你可以使用常量来表示π，比如

PI=3.979323，也可以使用数学公式来求π，比如PI=atan(1.0)*4。

4.

Fibonacci数列

问题描述

Fibonacci数列的递推公式为：F

n

=F

n-1

+F

n-2

，其中F

1

=F

2

=1。

当n比较大时，F

n

也非常大，现在我们想知道，F

n

除以10007的余数是多少。

输入格式

输入包含一个整数n。

输出格式

输出一行，包含一个整数，表示F

n

除以10007的余数。

说明：在本题中，答案是要求F

n

除以10007的余数，因此我们只要能算出这个余数即可，

而不需要先计算出F

n

的准确值，再将计算的结果除以10007取余数，直接计算余数往往比

先算出原数再取余简单。

样例输入

10

样例输出

55

样例输入

22

样例输出

7704

数据规模与约定

1 <= n <= 1,000,000。

5.

闰年判断

问题描述

给定一个年份，判断这一年是不是闰年。

当以下情况之一满足时，这一年是闰年：

1. 年份是4的倍数而不是100的倍数；

2. 年份是400的倍数。

其他的年份都不是闰年。

输入格式

输入包含一个整数y，表示当前的年份。

输出格式

输出一行，如果给定的年份是闰年，则输出yes，否则输出no。

样例输入

2013

样例输出

no

样例输入

2016

样例输出

yes

数据规模与约定

1990 <= y <= 2050。

6.

01字串

问题描述

对于长度为5位的一个01串，每一位都可能是0或1，一共有32种可能。它们的前几个是：

00000

00001

00010

00011

00100

请按从小到大的顺序输出这32种01串。

输出格式

输出32行，按从小到大的顺序每行一个长度为5的01串。

样例输出

00000

00001

00010

00011

<以下部分省略>

7.

字母图形

问题描述

利用字母可以组成一些美丽的图形，下面给出了一个例子：

ABCDEFG

BABCDEF

CBABCDE

DCBABCD

EDCBABC

这是一个5行7列的图形，请找出这个图形的规律，并输出一个n行m列的图形。

输入格式

输入一行，包含两个整数n和m，分别表示你要输出的图形的行数的列数。

输出格式

输出n行，每个m个字符，为你的图形。

样例输入

5 7

样例输出

ABCDEFG

BABCDEF

CBABCDE

DCBABCD

EDCBABC

数据规模与约定

1 <= n, m <= 26。

8.

数列特征

问题描述

给出n个数，找出这n个数的最大值，最小值，和。

输入格式

第一行为整数n，表示数的个数。

第二行有n个数，为给定的n个数，每个数的绝对值都小于10000。

输出格式

输出三行，每行一个整数。第一行表示这些数中的最大值，第二行表示这些数中的最小值，

第三行表示这些数的和。

样例输入

5

1 3 -2 4 5

样例输出

5

-2

3

数据规模与约定

1 <= n <= 10000。

9.

查找整数

问题描述

给出一个包含n个整数的数列，问整数a在数列中的第一次出现是第几个。

输入格式

第一行包含一个整数n。

第二行包含n个非负整数，为给定的数列，数列中的每个数都不大于10000。

第三行包含一个整数a，为待查找的数。

输出格式

如果a在数列中出现了，输出它第一次出现的位置(位置从1开始编号)，否则输出-1。

样例输入

6

1 9 4 8 3 9

9

样例输出

2

数据规模与约定

1 <= n <= 1000。

10.

杨辉三角形

问题描述

杨辉三角形又称Pascal三角形，它的第i+1行是(a+b)的展开式的系数。它的一个重要性

质是：三角形中的每个数字等于它两肩上的数字相加。下面给出了杨辉三角形的前4行：

1

1 1

1 2 1

1 3 3 1

给出n，输出它的前n行。

i

输入格式

输入包含一个数n。

输出格式

输出杨辉三角形的前n行。每一行从这一行的第一个数开始依次输出，中间使用一个空格分

隔。请不要在前面输出多余的空格。

样例输入

4

样例输出

1

1 1

1 2 1

1 3 3 1

数据规模与约定

1 <= n <= 34。

11.

特殊的数字

问题描述

153是一个非常特殊的数，它等于它的每位数字的立方和，即153=1*1*1+5*5*5+3*3*3。

编程求所有满足这种条件的三位十进制数。

输出格式

按从小到大的顺序输出满足条件的三位十进制数，每个数占一行。

12.

回文数

问题描述

1221是一个非常特殊的数，它从左边读和从右边读是一样的，编程求所有这样的四位

十进制数。

输出格式

按从小到大的顺序输出满足条件的四位十进制数。

13.

特殊回文数

问题描述

123321是一个非常特殊的数，它从左边读和从右边读是一样的。

输入一个正整数n， 编程求所有这样的五位和六位十进制数，满足各位数字之和等于

n 。

输入格式

输入一行，包含一个正整数n。

输出格式

按从小到大的顺序输出满足条件的整数，每个整数占一行。

样例输入

52

样例输出

899998

989989

998899

数据规模和约定

1<=n<=54。

14.

十进制转十六进制

问题描述

十六进制数是在程序设计时经常要使用到的一种整数的表示方式。它有

0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F共16个符号，分别表示十进制数的0至15。十六进制

的计数方法是满16进1，所以十进制数16在十六进制中是10，而十进制的17在十六进制

中是11，以此类推，十进制的30在十六进制中是1E。

给出一个非负整数，将它表示成十六进制的形式。

输入格式

输入包含一个非负整数a，表示要转换的数。0<=a<=2147483647

输出格式

输出这个整数的16进制表示

样例输入

30

样例输出

1E

15.

十六进制转十进制

问题描述

从键盘输入一个不超过8位的正的十六进制数字符串，将它转换为正的十进制数后输

出。

注：十六进制数中的10~15分别用大写的英文字母A、B、C、D、E、F表示。

样例输入

FFFF

样例输出

65535

16.

十六进制转八进制

问题描述

给定n个十六进制正整数，输出它们对应的八进制数。

输入格式

输入的第一行为一个正整数n （1<=n<=10）。

接下来n行，每行一个由0~9、大写字母A~F组成的字符串，表示要转换的十六进制正

整数，每个十六进制数长度不超过100000。

输出格式

输出n行，每行为输入对应的八进制正整数。

注意

输入的十六进制数不会有前导0，比如012A。

输出的八进制数也不能有前导0。

样例输入

2

39

123ABC

样例输出

71

4435274

提示

先将十六进制数转换成某进制数，再由某进制数转换成八进制。

17.

数列排序

问题描述

给定一个长度为n的数列，将这个数列按从小到大的顺序排列。1<=n<=200

输入格式

第一行为一个整数n。

第二行包含n个整数，为待排序的数，每个整数的绝对值小于10000。

输出格式

输出一行，按从小到大的顺序输出排序后的数列。

样例输入

5

8 3 6 4 9

样例输出

3 4 6 8 9

18.

时间转换

问题描述

给定一个以秒为单位的时间t，要求用“::”的格式来表示这个时间。表

示时间，表示分钟，而表示秒，它们都是整数且没有前导的“0”。例如，若t=0，

则应输出是“0:0:0”；若t=3661，则输出“1:1:1”。

输入格式

输入只有一行，是一个整数t（0<=t<=86399）。

输出格式

输出只有一行，是以“::”的格式所表示的时间，不包括引号。

样例输入

0

样例输出

0:0:0

样例输入

5436

样例输出

1:30:36

19.

字符串对比

问题描述

给定两个仅由大写字母或小写字母组成的字符串(长度介于1到10之间)，它们之间的

关系是以下4中情况之一：

1：两个字符串长度不等。比如 Beijing 和 Hebei

2：两个字符串不仅长度相等，而且相应位置上的字符完全一致(区分大小写)，比如

Beijing 和 Beijing

3：两个字符串长度相等，相应位置上的字符仅在不区分大小写的前提下才能达到完全

一致（也就是说，它并不满足情况2）。比如 beijing 和 BEIjing

4：两个字符串长度相等，但是即使是不区分大小写也不能使这两个字符串一致。比如

Beijing 和 Nanjing

编程判断输入的两个字符串之间的关系属于这四类中的哪一类，给出所属的类的编号。

输入格式

包括两行，每行都是一个字符串

输出格式

仅有一个数字，表明这两个字符串的关系编号

样例输入

BEIjing

beiJing

样例输出

3

20.

分解质因数

问题描述

求出区间[a,b]中所有整数的质因数分解。

输入格式

输入两个整数a，b。

输出格式

每行输出一个数的分解，形如k=a1*(a1<=a2<=a3...，k也是从小到大的)(具

体可看样例)

样例输入

3 10

样例输出

3=3

4=2*2

5=5

6=2*3

7=7

8=2*2*2

9=3*3

10=2*5

提示

先筛出所有素数，然后再分解。

数据规模和约定

2<=a<=b<=10000

21.

矩阵乘法

问题描述

给定一个N阶矩阵A，输出A的M次幂（M是非负整数）

例如：

A =

1 2

3 4

A的2次幂

7 10

15 22

输入格式

第一行是一个正整数N、M（1<=N<=30, 0<=M<=5），表示矩阵A的阶数和要求的幂数

接下来N行，每行N个绝对值不超过10的非负整数，描述矩阵A的值

输出格式

输出共N行，每行N个整数，表示A的M次幂所对应的矩阵。相邻的数之间用一个空格

隔开

样例输入

2 2

1 2

3 4

样例输出

7 10

15 22

22.

矩形面积交

问题描述

平面上有两个矩形，它们的边平行于直角坐标系的X轴或Y轴。对于每个矩形，我们给

出它的一对相对顶点的坐标，请你编程算出两个矩形的交的面积。

输入格式

输入仅包含两行，每行描述一个矩形。

在每行中，给出矩形的一对相对顶点的坐标，每个点的坐标都用两个绝对值不超过10^7

的实数表示。

输出格式

输出仅包含一个实数，为交的面积，保留到小数后两位。

样例输入

1 1 3 3

2 2 4 4

样例输出

1.00

23.

完美的代价

问题描述

回文串，是一种特殊的字符串，它从左往右读和从右往左读是一样的。小龙龙认为回文

串才是完美的。现在给你一个串，它不一定是回文的，请你计算最少的交换次数使得该串变

成一个完美的回文串。

交换的定义是：交换两个相邻的字符

例如mamad

第一次交换 ad : mamda

第二次交换 md : madma

第三次交换 ma : madam (回文！完美！)

输入格式

第一行是一个整数N，表示接下来的字符串的长度(N <= 8000)

第二行是一个字符串，长度为N.只包含小写字母

输出格式

如果可能，输出最少的交换次数。

否则输出Impossible

样例输入

5

mamad

样例输出

3

24.

数的读法

问题描述

Tom教授正在给研究生讲授一门关于基因的课程，有一件事情让他颇为头疼：一条染色

体上有成千上万个碱基对，它们从0开始编号，到几百万，几千万，甚至上亿。

比如说，在对学生讲解第1234567009号位置上的碱基时，光看着数字是很难准确的念

出来的。

所以，他迫切地需要一个系统，然后当他输入12 3456 7009时，会给出相应的念法：

十二亿三千四百五十六万七千零九

用汉语拼音表示为

shi er yi san qian si bai wu shi liu wan qi qian ling jiu

这样他只需要照着念就可以了。

你的任务是帮他设计这样一个系统：给定一个阿拉伯数字串，你帮他按照中文读写的规

范转为汉语拼音字串，相邻的两个音节用一个空格符格开。

注意必须严格按照规范，比如说“10010”读作“yi wan ling yi shi”而不是“yi wan

ling shi”，“100000”读作“shi wan”而不是“yi shi wan”，“2000”读作“er qian”

而不是“liang qian”。

输入格式

有一个数字串，数值大小不超过2,000,000,000。

输出格式

是一个由小写英文字母，逗号和空格组成的字符串，表示该数的英文读法。

样例输入

1234567009

样例输出

shi er yi san qian si bai wu shi liu wan qi qian ling jiu

25.

Sine之舞

问题描述

最近FJ为他的奶牛们开设了数学分析课，FJ知道若要学好这门课，必须有一个好的三

角函数基本功。所以他准备和奶牛们做一个“Sine之舞”的游戏，寓教于乐，提高奶牛们

的计算能力。

不妨设

An=sin(1–sin(2+sin(3–sin(4+...sin(n))...)

Sn=(...(A1+n)A2+n-1)A3+...+2)An+1

FJ想让奶牛们计算Sn的值，请你帮助FJ打印出Sn的完整表达式，以方便奶牛们做题。

输入格式

仅有一个数：N<201。

输出格式

请输出相应的表达式Sn，以一个换行符结束。输出中不得含有多余的空格或换行、回

车符。

样例输入

3

样例输出

((sin(1)+3)sin(1–sin(2))+2)sin(1–sin(2+sin(3)))+1

26. FJ的字符串

问题描述

FJ在沙盘上写了这样一些字符串：

A1 = “A”

A2 = “ABA”

A3 = “ABACABA”

A4 = “ABACABADABACABA”

… …

你能找出其中的规律并写所有的数列AN吗？

输入格式

仅有一个数：N ≤ 26。

输出格式

请输出相应的字符串AN，以一个换行符结束。输出中不得含有多余的空格或换行、回

车符。

样例输入

3

样例输出

ABACABA

27.

芯片测试

问题描述

有n（2≤n≤20）块芯片，有好有坏，已知好芯片比坏芯片多。

每个芯片都能用来测试其他芯片。用好芯片测试其他芯片时，能正确给出被测试芯片是

好还是坏。而用坏芯片测试其他芯片时，会随机给出好或是坏的测试结果（即此结果与被测

试芯片实际的好坏无关）。

给出所有芯片的测试结果，问哪些芯片是好芯片。

输入格式

输入数据第一行为一个整数n，表示芯片个数。

第二行到第n+1行为n*n的一张表，每行n个数据。表中的每个数据为0或1，在这n

行中的第i行第j列（1≤i, j≤n）的数据表示用第i块芯片测试第j块芯片时得到的测试

结果，1表示好，0表示坏，i=j时一律为1（并不表示该芯片对本身的测试结果。芯片不能

对本身进行测试）。

输出格式

按从小到大的顺序输出所有好芯片的编号

样例输入

3

1 0 1

0 1 0

1 0 1

样例输出

1 3

28.

龟兔赛跑预测

问题描述

话说这个世界上有各种各样的兔子和乌龟，但是研究发现，所有的兔子和乌龟都有一个

共同的特点——喜欢赛跑。于是世界上各个角落都不断在发生着乌龟和兔子的比赛，小华对

此很感兴趣，于是决定研究不同兔子和乌龟的赛跑。他发现，兔子虽然跑比乌龟快，但它们

有众所周知的毛病——骄傲且懒惰，于是在与乌龟的比赛中，一旦任一秒结束后兔子发现自

己领先t米或以上，它们就会停下来休息s秒。对于不同的兔子，t，s的数值是不同的，

但是所有的乌龟却是一致——它们不到终点决不停止。

然而有些比赛相当漫长，全程观看会耗费大量时间，而小华发现只要在每场比赛开始后

记录下兔子和乌龟的数据——兔子的速度v1（表示每秒兔子能跑v1米），乌龟的速度v2，

以及兔子对应的t，s值，以及赛道的长度l——就能预测出比赛的结果。但是小华很懒，

不想通过手工计算推测出比赛的结果，于是他找到了你——清华大学计算机系的高才生——

请求帮助，请你写一个程序，对于输入的一场比赛的数据v1，v2，t，s，l，预测该场比赛

的结果。

输入格式

输入只有一行，包含用空格隔开的五个正整数v1，v2，t，s，l，其中

(v1,v2<=100;t<=300;s<=10;l<=10000且为v1,v2的公倍数)

输出格式

输出包含两行，第一行输出比赛结果——一个大写字母“T”或“R”或“D”，分别表

示乌龟获胜，兔子获胜，或者两者同时到达终点。

第二行输出一个正整数，表示获胜者（或者双方同时）到达终点所耗费的时间（秒数）。

样例输入

10 5 5 2 20

样例输出

D

4

样例输入

10 5 5 1 20

样例输出

R

3

样例输入

10 5 5 3 20

样例输出

T

4

29.

回形取数

问题描述

回形取数就是沿矩阵的边取数，若当前方向上无数可取或已经取过，则左转90度。一

开始位于矩阵左上角，方向向下。

输入格式

输入第一行是两个不超过200的正整数m, n，表示矩阵的行和列。接下来m行每行n

个整数，表示这个矩阵。

输出格式

输出只有一行，共mn个数，为输入矩阵回形取数得到的结果。数之间用一个空格分隔，

行末不要有多余的空格。

样例输入

3 3

1 2 3

4 5 6

7 8 9

样例输出

1 4 7 8 9 6 3 2 5

样例输入

3 2

1 2

3 4

5 6

样例输出

1 3 5 6 4 2

30.

报时助手

问题描述

给定当前的时间，请用英文的读法将它读出来。

时间用时h和分m表示，在英文的读法中，读一个时间的方法是：

如果m为0，则将时读出来，然后加上“o'clock”，如3:00读作“three o'clock”。

如果m不为0，则将时读出来，然后将分读出来，如5:30读作“five thirty”。

时和分的读法使用的是英文数字的读法，其中0~20读作：

0:zero, 1: one, 2:two, 3:three, 4:four, 5:five, 6:six, 7:seven, 8:eight, 9:nine,

10:ten, 11:eleven, 12:twelve, 13:thirteen, 14:fourteen, 15:fifteen, 16:sixteen,

17:seventeen, 18:eighteen, 19:nineteen, 20:twenty。

30读作thirty，40读作forty，50读作fifty。

对于大于20小于60的数字，首先读整十的数，然后再加上个位数。如31首先读30

再加1的读法，读作“thirty one”。

按上面的规则21:54读作“twenty one fifty four”，9:07读作“nine seven”，0:15

读作“zero fifteen”。

输入格式

输入包含两个非负整数h和m，表示时间的时和分。非零的数字前没有前导0。h小于

24，m小于60。

输出格式

输出时间时刻的英文。

样例输入

0 15

样例输出

zero fifteen

31.

2n皇后问题

问题描述

给定一个n*n的棋盘，棋盘中有一些位置不能放皇后。现在要向棋盘中放入n个黑皇后

和n个白皇后，使任意的两个黑皇后都不在同一行、同一列或同一条对角线上，任意的两个

白皇后都不在同一行、同一列或同一条对角线上。问总共有多少种放法？n小于等于8。

输入格式

输入的第一行为一个整数n，表示棋盘的大小。

接下来n行，每行n个0或1的整数，如果一个整数为1，表示对应的位置可以放皇后，

如果一个整数为0，表示对应的位置不可以放皇后。

输出格式

输出一个整数，表示总共有多少种放法。

样例输入

4

1 1 1 1

1 1 1 1

1 1 1 1

1 1 1 1

样例输出

2

样例输入

4

1 0 1 1

1 1 1 1

1 1 1 1

1 1 1 1

样例输出

0

32. Huffuman树

问题描述

Huffman树在编码中有着广泛的应用。在这里，我们只关心Huffman树的构造过程。

给出一列数{p

i

}={p

0

, p

1

, …, p

n-1

}，用这列数构造Huffman树的过程如下：

1. 找到{p

i

}中最小的两个数，设为p

a

和p

b

，将p

a

和p

b

从{p

i

}中删除掉，然后将它们的

和加入到{p

i

}中。这个过程的费用记为p

a

+ p

b

。

2. 重复步骤1，直到{p

i

}中只剩下一个数。

在上面的操作过程中，把所有的费用相加，就得到了构造Huffman树的总费用。

本题任务：对于给定的一个数列，现在请你求出用该数列构造Huffman树的总费用。

例如，对于数列{p

i

}={5, 3, 8, 2, 9}，Huffman树的构造过程如下：

1. 找到{5, 3, 8, 2, 9}中最小的两个数，分别是2和3，从{p

i

}中删除它们并将和5

加入，得到{5, 8, 9, 5}，费用为5。

2. 找到{5, 8, 9, 5}中最小的两个数，分别是5和5，从{p

i

}中删除它们并将和10加

入，得到{8, 9, 10}，费用为10。

3. 找到{8, 9, 10}中最小的两个数，分别是8和9，从{p

i

}中删除它们并将和17加入，

得到{10, 17}，费用为17。

4. 找到{10, 17}中最小的两个数，分别是10和17，从{p

i

}中删除它们并将和27加入，

得到{27}，费用为27。

5. 现在，数列中只剩下一个数27，构造过程结束，总费用为5+10+17+27=59。

输入格式

输入的第一行包含一个正整数n（n<=100）。

接下来是n个正整数，表示p

0

, p

1

, …, p

n-1

，每个数不超过1000。

输出格式

输出用这些数构造Huffman树的总费用。

样例输入

5

5 3 8 2 9

样例输出

59

33.

高精度加法

问题描述

输入两个整数a和b，输出这两个整数的和。a和b都不超过100位。

算法描述

由于a和b都比较大，所以不能直接使用语言中的标准数据类型来存储。对于这种问题，

一般使用数组来处理。

定义一个数组A，A[0]用于存储a的个位，A[1]用于存储a的十位，依此类推。同样可

以用一个数组B来存储b。

计算c = a + b的时候，首先将A[0]与B[0]相加，如果有进位产生，则把进位（即和

的十位数）存入r，把和的个位数存入C[0]，即C[0]等于(A[0]+B[0])%10。然后计算A[1]

与B[1]相加，这时还应将低位进上来的值r也加起来，即C[1]应该是A[1]、B[1]和r三个

数的和．如果又有进位产生，则仍可将新的进位存入到r中，和的个位存到C[1]中。依此

类推，即可求出C的所有位。

最后将C输出即可。

输入格式

输入包括两行，第一行为一个非负整数a，第二行为一个非负整数b。两个整数都不超

过100位，两数的最高位都不是0。

输出格式

输出一行，表示a + b的值。

样例输入

290

2122

样例输出

212

34.

阶乘计算

问题描述

输入一个正整数n，输出n!的值。

其中n!=1*2*3*…*n。

算法描述

n!可能很大，而计算机能表示的整数范围有限，需要使用高精度计算的方法。使用一个

数组A来表示一个大整数a，A[0]表示a的个位，A[1]表示a的十位，依次类推。

将a乘以一个整数k变为将数组A的每一个元素都乘以k，请注意处理相应的进位。

首先将a设为1，然后乘2，乘3，当乘到n时，即得到了n!的值。

输入格式

输入包含一个正整数n，n<=1000。

输出格式

输出n!的准确值。

样例输入

10

样例输出

3628800

35.

区间k大数查询

问题描述

给定一个序列，每次询问序列中第l个数到第r个数中第K大的数是哪个。

输入格式

第一行包含一个数n，表示序列长度。

第二行包含n个正整数，表示给定的序列。

第三个包含一个正整数m，表示询问个数。

接下来m行，每行三个数l,r,K，表示询问序列从左往右第l个数到第r个数中，从大往小

第K大的数是哪个。序列元素从1开始标号。

输出格式

总共输出m行，每行一个数，表示询问的答案。

样例输入

5

1 2 3 4 5

2

1 5 2

2 3 2

样例输出

4

2

数据规模与约定

对于30%的数据，n,m<=100；

对于100%的数据，n,m<=1000；

6

保证k<=(r-l+1)，序列中的数<=10。

36.

最大最小公倍数

问题描述

已知一个正整数N，问从1~N中任选出三个数，他们的最小公倍数最大可以为多少。

输入格式

输入一个正整数N。

输出格式

输出一个整数，表示你找到的最小公倍数。

样例输入

9

样例输出

504

数据规模与约定

1 <= N <= 10。

6

37.

K好数

问题描述

如果一个自然数N的K进制表示中任意的相邻的两位都不是相邻的数字，那么我们就说这个

数是K好数。求L位K进制数中K好数的数目。例如K = 4，L = 2的时候，所有K好数为

11、13、20、22、30、31、33 共7个。由于这个数目很大，请你输出它对1000000007取模

后的值。

输入格式

输入包含两个正整数，K和L。

输出格式

输出一个整数，表示答案对1000000007取模后的值。

样例输入

4 2

样例输出

7

数据规模与约定

对于30%的数据，K <= 10；

对于50%的数据，K <= 16， L <= 10；

对于100%的数据，1 <= K,L <= 100。

L6

38.

结点选择

问题描述

有一棵 n 个节点的树，树上每个节点都有一个正整数权值。如果一个点被选择了，那么在

树上和它相邻的点都不能被选择。求选出的点的权值和最大是多少？

输入格式

第一行包含一个整数 n 。

接下来的一行包含 n 个正整数，第 i 个正整数代表点 i 的权值。

接下来一共 n-1 行，每行描述树上的一条边。

输出格式

输出一个整数，代表选出的点的权值和的最大值。

样例输入

5

1 2 3 4 5

1 2

1 3

2 4

2 5

样例输出

12

样例说明

选择3、4、5号点，权值和为 3+4+5 = 12 。

数据规模与约定

对于20%的数据， n <= 20。

对于50%的数据， n <= 1000。

对于100%的数据， n <= 100000。

权值均为不超过1000的正整数。

39.

最短路

问题描述

给定一个n个顶点，m条边的有向图（其中某些边权可能为负，但保证没有负环）。请你计

算从1号点到其他点的最短路（顶点从1到n编号）。

输入格式

第一行两个整数n, m。

接下来的m行，每行有三个整数u, v, l，表示u到v有一条长度为l的边。

输出格式

共n-1行，第i行表示1号点到i+1号点的最短路。

样例输入

3 3

1 2 -1

2 3 -1

3 1 2

样例输出

-1

-2

数据规模与约定

对于10%的数据，n = 2，m = 2。

对于30%的数据，n <= 5，m <= 10。

对于100%的数据，1 <= n <= 20000，1 <= m <= 200000，-10000 <= l <= 10000，保证从

任意顶点都能到达其他所有顶点。

40.

安慰奶牛

问题描述

Farmer John变得非常懒，他不想再继续维护供奶牛之间供通行的道路。道路被用来连接N

个牧场，牧场被连续地编号为1到N。每一个牧场都是一个奶牛的家。FJ计划除去P条道路

中尽可能多的道路，但是还要保持牧场之间 的连通性。你首先要决定那些道路是需要保留

的N-1条道路。第j条双向道路连接了牧场S

j

和E

j

(1 <= S

j

<= N; 1 <= E

j

<= N; S

j

!=

E

j

)，而且走完它需要L

j

的时间。没有两个牧场是被一条以上的道路所连接。奶牛们非常伤

心，因为她们的交通系统被削减了。你需要到每一个奶牛的住处去安慰她们。每次你到达第

i个牧场的时候(即使你已经到过)，你必须花去C

i

的时间和奶牛交谈。你每个晚上都会在同

一个牧场(这是供你选择的)过夜，直到奶牛们都从悲伤中缓过神来。在早上 起来和晚上回

去睡觉的时候，你都需要和在你睡觉的牧场的奶牛交谈一次。这样你才能完成你的 交谈任

务。假设Farmer John采纳了你的建议，请计算出使所有奶牛都被安慰的最少时间。

输入格式

第1行包含两个整数N和P。

接下来N行，每行包含一个整数C

i

。

接下来P行，每行包含三个整数S

j

, E

j

和L

j

。

输出格式

输出一个整数, 所需要的总时间(包含和在你所在的牧场的奶牛的两次谈话时间)。

样例输入

5 7

10

10

20

6

30

1 2 5

2 3 5

2 4 12

3 4 17

2 5 15

3 5 6

样例输出

176

数据规模与约定

5 <= N <= 10000，N-1 <= P <= 100000，0 <= L

j

<= 1000，1 <= C

i

<= 1,000。

41.

逆序对

问题描述

Alice是一个让人非常愉跃的人!他总是去学习一些他不懂的问题，然后再想出许多稀奇古

怪的题目。这几天，Alice又沉浸在逆序对的快乐当中，他已近学会了如何求逆序对对数，

动态维护逆序对对数等等题目，他认为把这些题让你做简直是太没追求了，于是，经过一天

的思考和完善，Alice终于拿出了一道他认为差不多的题目：

有一颗2n-1个节点的二叉树，它有恰好n个叶子节点，每个节点上写了一个整数。如果将

这棵树的所有叶子节点上的数从左到右写下来，便得到一个序列a[1]…a[n]。现在想让这

个序列中的逆序对数量最少，但唯一的操作就是选树上一个非叶子节点，将它的左右两颗子

树交换。他可以做任意多次这个操作。求在最优方案下，该序列的逆序对数最少有多少。

Alice自己已近想出了题目的正解，他打算拿来和你分享，他要求你在最短的时间内完成。

输入格式

第一行一个整数n。

下面每行，一个数x。

如果x=0，表示这个节点非叶子节点，递归地向下读入其左孩子和右孩子的信息，如果x≠0，

表示这个节点是叶子节点，权值为x。

输出格式

输出一个整数，表示最少有多少逆序对。

样例输入

3

0

0

3

1

2

样例输出

1

数据规模与约定

对于20%的数据，n <= 5000。

对于100%的数据，1 <= n <= 200000，0 <= a[i]<2^31。

42.

操作格子

问题描述

有n个格子，从左到右放成一排，编号为1-n。

共有m次操作，有3种操作类型：

1.修改一个格子的权值，

2.求连续一段格子权值和，

3.求连续一段格子的最大值。

对于每个2、3操作输出你所求出的结果。

输入格式

第一行2个整数n，m。

接下来一行n个整数表示n个格子的初始权值。

接下来m行，每行3个整数p,x,y，p表示操作类型，p=1时表示修改格子x的权值为y，p=2

时表示求区间[x,y]内格子权值和，p=3时表示求区间[x,y]内格子最大的权值。

输出格式

有若干行，行数等于p=2或3的操作总数。

每行1个整数，对应了每个p=2或3操作的结果。

样例输入

4 3

1 2 3 4

2 1 3

1 4 3

3 1 4

样例输出

6

3

数据规模与约定

对于20%的数据n <= 100，m <= 200。

对于50%的数据n <= 5000，m <= 5000。

对于100%的数据1 <= n <= 100000，m <= 100000，0 <= 格子权值 <= 10000。

43.

摆动序列

问题描述

如果一个序列满足下面的性质，我们就将它称为摆动序列：

1. 序列中的所有数都是不大于k的正整数；

2. 序列中至少有两个数。

3. 序列中的数两两不相等；

4. 如果第i – 1个数比第i – 2个数大，则第i个数比第i – 2个数小；如果第i

– 1个数比第i – 2个数小，则第i个数比第i – 2个数大。

比如，当k = 3时，有下面几个这样的序列：

1 2

1 3

2 1

2 1 3

2 3

2 3 1

3 1

3 2

一共有8种，给定k，请求出满足上面要求的序列的个数。

输入格式

输入包含了一个整数k。（k<=20）

输出格式

输出一个整数，表示满足要求的序列个数。

样例输入

3

样例输出

8

44.

集合运算

问题描述

给出两个整数集合A、B，求出他们的交集、并集以及B在A中的余集。

输入格式

第一行为一个整数n，表示集合A中的元素个数。

第二行有n个互不相同的用空格隔开的整数，表示集合A中的元素。

第三行为一个整数m，表示集合B中的元素个数。

第四行有m个互不相同的用空格隔开的整数，表示集合B中的元素。

集合中的所有元素均为int范围内的整数，n、m<=1000。

输出格式

第一行按从小到大的顺序输出A、B交集中的所有元素。

第二行按从小到大的顺序输出A、B并集中的所有元素。

第三行按从小到大的顺序输出B在A中的余集中的所有元素。

样例输入

5

1 2 3 4 5

5

2 4 6 8 10

样例输出

2 4

1 2 3 4 5 6 8 10

1 3 5

样例输入

4

1 2 3 4

3

5 6 7

样例输出

1 2 3 4 5 6 7

1 2 3 4

45.

瓷砖铺放

问题描述

有一长度为N(1<=Ｎ<=10)的地板，给定两种不同瓷砖：一种长度为1，另一种长度为2，

数目不限。要将这个长度为N的地板铺满，一共有多少种不同的铺法？

例如，长度为4的地面一共有如下5种铺法：

4=1+1+1+1

4=2+1+1

4=1+2+1

4=1+1+2

4=2+2

编程用递归的方法求解上述问题。

输入格式

只有一个数N，代表地板的长度

输出格式

输出一个数，代表所有不同的瓷砖铺放方法的总数

样例输入

4

样例输出

5

46.

幂方分解

问题描述

任何一个正整数都可以用2的幂次方表示。例如：

730

137=2+2+2

b

同时约定方次用括号来表示，即a 可表示为a（b）。

由此可知，137可表示为：

2（7）+2（3）+2（0）

20 1

进一步：7= 2+2+2（2用2表示）

0

3=2+2

所以最后137可表示为：

2（2（2）+2+2（0））+2（2+2（0））+2（0）

又如：

1085

1315=2 +2 +2 +2+1

所以1315最后可表示为：

2（2（2+2（0））+2）+2（2（2+2（0）））+2（2（2）+2（0））+2+2（0）

输入格式

输入包含一个正整数N（N<=20000），为要求分解的整数。

输出格式

程序输出包含一行字符串，为符合约定的n的0，2表示（在表示中不能有空格）

47.

拦截导弹

问题描述

某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一

个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发

的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，

因此有可能不能拦截所有的导弹。

输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数），计算这套

系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

输入格式

一行，为导弹依次飞来的高度

输出格式

两行，分别是最多能拦截的导弹数与要拦截所有导弹最少要配备的系统数

样例输入

389 207 155 300 299 170 158 65

样例输出

6

2

48.

回文数

问题描述

若一个数（首位不为零）从左向右读与从右向左读都一样，我们就将其称之为回文数。

例如：给定一个10进制数56，将56加65（即把56从右向左读），得到121是一个回

文数。

又如：对于10进制数87：

STEP1：87+78 = 165 STEP2：165+561 = 726

STEP3：726+627 = 1353 STEP4：1353+3531 = 4884

在这里的一步是指进行了一次N进制的加法，上例最少用了4步得到回文数4884。

写一个程序，给定一个N（2<=N<=10或N=16）进制数M（其中16进制数字为0-9与A-F），

求最少经过几步可以得到回文数。

如果在30步以内（包含30步）不可能得到回文数，则输出“Impossible!”

输入格式

两行，N与M

输出格式

如果能在30步以内得到回文数，输出“STEP=xx”（不含引号），其中xx是步数；否

则输出一行”Impossible!”（不含引号）

样例输入

9

87

样例输出

STEP=6

49.

旅行家的预算

问题描述

一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市（假设出发时油箱是空

的）。给定两个城市之间的距离D1、汽车油箱的容量C（以升为单位）、每升汽油能行驶的

距离D2、出发点每升汽油价格P和沿途油站数N（N可以为零），油站i离出发点的距离Di、

每升汽油价格Pi（i=1，2，……N）。计算结果四舍五入至小数点后两位。如果无法到达目

的地，则输出“No Solution”。

输入格式

第一行为4个实数D1、C、D2、P与一个非负整数N；

接下来N行，每行两个实数Di、Pi。

输出格式

如果可以到达目的地，输出一个实数（四舍五入至小数点后两位），表示最小费用；否

则输出“No Solution”（不含引号）。

样例输入

275.6 11.9 27.4 2.8 2

102.0 2.9

220.0 2.2

样例输出

26.95

50.

进制转换

问题描述

我们可以用这样的方式来表示一个十进制数： 将每个阿拉伯数字乘以一个以该数字所

处位置的（值减１）为指数，以１０为底数的幂之和的形式。例如：１２３可表示为 １＊

２１０

１０＋２＊１０＋３＊１０这样的形式。

与之相似的，对二进制数来说，也可表示成每个二进制数码乘以一个以该数字所处位置

的（值－１）为指数，以２为底数的幂之和的形式。一般说来，任何一个正整数Ｒ或一个负

整数－Ｒ都可以被选来作为一个数制系统的基数。如果是以Ｒ或－Ｒ为基数，则需要用到的

数码为 ０，１，．．．．Ｒ－１。例如，当Ｒ＝７时，所需用到的数码是０，１，２，３，

４，５和６，这与其是Ｒ或－Ｒ无关。如果作为基数的数绝对值超过１０，则为了表示这些

数码，通常使用英文字母来表示那些大于９的数码。例如对１６进制数来说，用Ａ表示１０，

用Ｂ表示１１，用Ｃ表示１２，用Ｄ表示１３，用Ｅ表示１４，用Ｆ表示１５。

在负进制数中是用－Ｒ 作为基数，例如－１５（十进制）相当于１１０００１（－２

进制），并且它可以被表示为２的幂级数的和数：

５４３２

１１０００１＝１＊（－２）＋１＊（－２）＋０＊（－２）＋０＊（－２）＋

１０

０＊（－２） ＋１＊（－２）

设计一个程序，读入一个十进制数和一个负进制数的基数, 并将此十进制数转换为此

负进制下的数： －Ｒ∈｛－２，－３，－４，．．．，－２０｝

输入格式

一行两个数，第一个是十进制数Ｎ（－32768＜＝Ｎ＜＝32767）， 第二个是负进制数

的基数－Ｒ。

输出格式

输出所求负进制数及其基数，若此基数超过１０，则参照１６进制的方式处理。

样例输入

30000 -2

样例输出

30000=11000(base-2)

样例输入

-20000 -2

样例输出

-20000=1111(base-2)

样例输入

28800 -16

样例输出

28800=19180(base-16)

样例输入

-25000 -16

样例输出

-25000=7FB8(base-16)

51.

单词接龙

问题描述

单词接龙是一个与我们经常玩的成语接龙相类似的游戏，现在我们已知一组单词，且给

定一个开头的字母，要求出以这个字母开头的最长的“龙”（每个单词都最多在“龙”中出

现两次），在两个单词相连时，其重合部分合为一部分，例如 beast和astonish，如果接

成一条龙则变为beastonish，另外相邻的两部分不能存在包含关系，例如at 和 atide 间

不能相连。

输入格式

输入的第一行为一个单独的整数n (n<=20)表示单词数，以下n 行每行有一个单词，输

入的最后一行为一个单个字符，表示“龙”开头的字母。你可以假定以此字母开头的“龙”

一定存在.

输出格式

只需输出以此字母开头的最长的“龙”的长度

样例输入

5

at

touch

cheat

choose

tact

a

样例输出

23

样例说明

连成的“龙”为atoucheatactactouchoose

52.

乘积最大

问题描述

今年是国际数学联盟确定的“2000——世界数学年”，又恰逢我国著名数学家华罗庚先

生诞辰90周年。在华罗庚先生的家乡江苏金坛，组织了一场别开生面的数学智力竞赛的活

动，你的一个好朋友XZ也有幸得以参加。活动中，主持人给所有参加活动的选手出了这样

一道题目：

设有一个长度为N的数字串，要求选手使用K个乘号将它分成K+1个部分，找出一种分

法，使得这K+1个部分的乘积能够为最大。

同时，为了帮助选手能够正确理解题意，主持人还举了如下的一个例子：

有一个数字串：312， 当N=3，K=1时会有以下两种分法：

3*12=36

31*2=62

这时，符合题目要求的结果是：31*2=62

现在，请你帮助你的好朋友XZ设计一个程序，求得正确的答案。

输入格式

程序的输入共有两行：

第一行共有2个自然数N，K（6≤N≤40，1≤K≤6）

第二行是一个长度为N的数字串。

输出格式

输出所求得的最大乘积（一个自然数）。

样例输入

4 2

1231

样例输出

62

53. 方格取数

问题描述

设有N*N的方格图(N<=10),我们将其中的某些方格中填入正整数,而其他的方格中则放

入数字0。

某人从图的左上角的A 点(1,1)出发，可以向下行走，也可以向右走，直到到达右下角

的B点(N,N)。在走过的路上，他可以取走方格中的数（取走后的方格中将变为数字0）。

此人从A点到B 点共走两次，试找出2条这样的路径，使得取得的数之和为最大。

输入格式

输入的第一行为一个整数N（表示N*N的方格图），接下来的每行有三个整数，前两个

表示位置，第三个数为该位置上所放的数。一行单独的0表示输入结束。

输出格式

只需输出一个整数，表示2条路径上取得的最大的和。

样例输入

8

2 3 13

2 6 6

3 5 7

4 4 14

5 2 21

5 6 4

6 3 15

7 2 14

0 0 0

样例输出

67

54. 求先序排列

问题描述

给出一棵二叉树的中序与后序排列。求出它的先序排列。（约定树结点用不同的大写字

母表示，长度<=8）。

输入格式

两行，每行一个字符串，分别表示中序和后序排列

输出格式

一个字符串，表示所求先序排列

样例输入

BADC

BDCA

样例输出

ABCD

55. 装箱问题

问题描述

有一个箱子容量为V（正整数，0＜＝V＜＝20000），同时有n个物品（0＜n＜＝30），

每个物品有一个体积（正整数）。

要求n个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。

输入格式

第一行为一个整数，表示箱子容量；

第二行为一个整数，表示有n个物品；

接下来n行，每行一个整数表示这n个物品的各自体积。

输出格式

一个整数，表示箱子剩余空间。

样例输入

24

6

8

3

12

7

9

7

样例输出

0

56. 数的划分

问题描述

将整数n分成k份，且每份不能为空，任意两份不能相同(不考虑顺序)。

例如：n=7，k=3，下面三种分法被认为是相同的。

1，1，5; 1，5，1; 5，1，1;

问有多少种不同的分法。

输入格式

n，k

输出格式

一个整数，即不同的分法

样例输入

7 3

样例输出

4 {四种分法为：1，1，5;1，2，4;1，3，3;2，2，3;}

数据规模和约定

6

57. 一元三次方程求解

问题描述

有形如：ax+bx+cx+d=0 这样的一个一元三次方程。给出该方程中各项的系数(a，b，c，

d 均为实数)，并约定该方程存在三个不同实根(根的范围在-100至100之间)，且根与根之

差的绝对值>=1。要求三个实根。。

32

输入格式

四个实数：a，b，c，d

输出格式

由小到大依次在同一行输出这三个实根(根与根之间留有空格)，并精确到小数点后2

位

样例输入

1 -5 -4 20

样例输出

-2.00 2.00 5.00

数据规模和约定

|a|，|b|，|c|，|d|<=10

58. 统计单词个数

问题描述

给出一个长度不超过200的由小写英文字母组成的字母串(约定;该字串以每行20个字

母的方式输入，且保证每行一定为20个)。要求将此字母串分成k份 (1

包含的单词个数加起来总数最大(每份中包含的单词可以部分重叠。当选用一个单词之后，

其第一个字母不能再用。例 如字符串this中可包含this和is，选用this之后就不能包

含th)。

单词在给出的一个不超过6个单词的字典中。

要求输出最大的个数。

输入格式

第一行有二个正整数(p，k)

p表示字串的行数;

k表示分为k个部分。

接下来的p行，每行均有20个字符。

再接下来有一个正整数s，表示字典中单词个数。(1<=s<=6)

接下来的s行，每行均有一个单词。

输出格式

每行一个整数，分别对应每组测试数据的相应结果。

样例输入

1 3

thisisabookyouareaoh

4

is

a

ok

sab

样例输出

7

数据规模和约定

长度不超过200，1

59. Car的旅行路线

问题描述

又到暑假了，住在城市A的Car想和朋友一起去城市B旅游。她知道每个城市都有四个

飞机场，分别位于一个矩形的四个顶点上，同一个城市中两个机场之间有一 条笔直的高速

铁路，第I个城市中高速铁路了的单位里程价格为Ti，任意两个不同城市的机场之间均有

航线，所有航线单位里程的价格均为t。

那么Car应如何安排到城市B的路线才能尽可能的节省花费呢?她发现这并不是一个简

单的问题，于是她来向你请教。

找出一条从城市A到B的旅游路线，出发和到达城市中的机场可以任意选取，要求总的

花费最少。

输入格式

的第一行有四个正整数s，t，A，B。

S表示城市的个数，t表示飞机单位里程的价格，A，B分别为城市A，B的序号，(1<=A，

B<=S)。

接下来有S行，其中第I行均有7个正整数xi1，yi1，xi2，yi2，xi3，yi3，Ti，这

当中的(xi1，yi1)，(xi2，yi2)，(xi3，yi3)分别是第I个城市中任意三个机场的坐标，T I

为第I个城市高速铁路单位里程的价格。

输出格式

共有n行，每行一个数据对应测试数据，保留一位小数。

样例输入

1

1 10 1 3

1 1 1 3 3 1 30

2 5 7 4 5 2 1

8 6 8 8 11 6 3

样例输出

47.55

数据规模和约定

0

60. 麦森数

问题描述

形如2-1的素数称为麦森数，这时P一定也是个素数。但反过来不一定，即如果P是

P

个素数，2-1不一定也是素数。到1998年底，人们已找到了37个麦森数。最大的一个是

P=3021377，它有909526位。麦森数有许多重要应用，它与完全数密切相关。

P

任务：从文件中输入P（1000

进制高精度数表示）

P

输入格式

文件中只包含一个整数P（1000

输出格式

第一行：十进制高精度数2-1的位数。

P

第2-11行：十进制高精度数2-1的最后500位数字。（每行输出50位，共输出10行，

不足500位时高位补0）

P

不必验证2-1与P是否为素数。

P

样例输入

1279

样例输出

386

00

00

46643993640855

386753360298012

2394442424832346

49773293892296

66962

5960

466622483354887

329587361869557

61. FBI树

问题描述

我们可以把由“0”和“1”组成的字符串分为三类：全“0”串称为B串，全“1”串称

为I串，既含“0”又含“1”的串则称为F串。

FBI树是一种二叉树，它的结点类型也包括F结点，B结点和I结点三种。由一个长度

N

为2的“01”串S可以构造出一棵FBI树T，递归的构造方法如下：

1)T的根结点为R，其类型与串S的类型相同；

2)若串S的长度大于1，将串S从中间分开，分为等长的左右子串S1和S2；由左子串

S1构造R的左子树T1，由右子串S2构造R的右子树T2。

N

现在给定一个长度为2的“01”串，请用上述构造方法构造出一棵FBI树，并输出它

的后序遍历序列。

输入格式

第一行是一个整数N（0 <= N <= 10），第二行是一个长度为2的“01”串。

N

输出格式

包括一行，这一行只包含一个字符串，即FBI树的后序遍历序列。

样例输入

3

10001011

样例输出

IBFBBBFIBFIIIFF

数据规模和约定

对于40%的数据，N <= 2；

对于全部的数据，N <= 10。

注：

[1] 二叉树：二叉树是结点的有限集合，这个集合或为空集，或由一个根结点和两棵不

相交的二叉树组成。这两棵不相交的二叉树分别称为这个根结点的左子树和右子树。

[2] 后序遍历：后序遍历是深度优先遍历二叉树的一种方法，它的递归定义是：先后序

遍历左子树，再后序遍历右子树，最后访问根。

62. 星际交流

问题描述

人类终于登上了火星的土地并且见到了神秘的火星人。人类和火星人都无法理解对方的

语言，但是我们的科学家发明了一种用数字交流的方法。这种交流方法是这样 的，首先，

火星人把一个非常大的数字告诉人类科学家，科学家破解这个数字的含义后，再把一个很小

的数字加到这个大数上面，把结果告诉火星人，作为人类的回 答。

火星人用一种非常简单的方式来表示数字——掰手指。火星人只有一只手，但这只手上

有成千上万的手指，这些手指排成一列，分别编号为1，2，3……。火星人的任意两根手指

都能随意交换位置，他们就是通过这方法计数的。

一个火星人用一个人类的手演示了如何用手指计数。如果把五根手指——拇指、食指、

中指、无名指和小指分别编号为1，2，3，4和5，当它们按正常顺序排列 时，形成了5位

数12345，当你交换无名指和小指的位置时，会形成5位数12354，当你把五个手指的顺序

完全颠倒时，会形成54321，在所有能够形 成的120个5位数中，12345最小，它表示1；

12354第二小，它表示2；54321最大，它表示120。下表展示了只有3根手指时能够形成的

6个 3位数和它们代表的数字：

三进制数

123

132

213

231

312

321

代表的数字

1

2

3

4

5

6

现在你有幸成为了第一个和火星人交流的地球人。一个火星人会让你看他的手指，科学

家会告诉你要加上去的很小的数。你的任务是，把火星人用手指表示的数与科 学家告诉你

的数相加，并根据相加的结果改变火星人手指的排列顺序。输入数据保证这个结果不会超出

火星人手指能表示的范围。

输入格式

包括三行，第一行有一个正整数N，表示火星人手指的数目（1 <= N <= 10000）。第

二行是一个正整数M，表示要加上去的小整数（1 <= M <= 100）。下一行是1到N这N个

整数的一个排列，用空格隔开，表示火星人手指的排列顺序。

输出格式

只有一行，这一行含有N个整数，表示改变后的火星人手指的排列顺序。每两个相邻的

数中间用一个空格分开，不能有多余的空格。

样例输入

5

3

1 2 3 4 5

样例输出

1 2 4 5 3

数据规模和约定

对于30%的数据，N<=15；

对于60%的数据，N<=50；

对于全部的数据，N<=10000；

63. 校门外的树

问题描述

某校大门外长度为L的马路上有一排树，每两棵相邻的树之间的间隔都是1米。我们可

以把马路看成一个数轴，马路的一端在数轴0的位置，另一端在L的位置；数 轴上的每个

整数点，即0，1，2，……，L，都种有一棵树。

由于马路上有一些区域要用来建地铁。这些区域用它们在数轴上的起始点和终止点表

示。已 知任一区域的起始点和终止点的坐标都是整数，区域之间可能有重合的部分。现在

要把这些区域中的树（包括区域端点处的两棵树）移走。你的任务是计算将这些树 都移走

后，马路上还有多少棵树。

输入格式

输入文件的第一行有两个整数L（1 <= L <= 10000）和 M（1 <= M <= 100），L代表

马路的长度，M代表区域的数目，L和M之间用一个空格隔开。接下来的M行每行包含两个

不同的整数，用一个空格隔开，表示一个区域的起始点 和终止点的坐标。

输出格式

输出文件包括一行，这一行只包含一个整数，表示马路上剩余的树的数目。

样例输入

500 3

150 300

100 200

470 471

样例输出

298

数据规模和约定

对于20%的数据，区域之间没有重合的部分；

对于其它的数据，区域之间有重合的情况。

64. 入学考试

问题描述

辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最

有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都

是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，

每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果

你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”

如果你是辰辰，你能完成这个任务吗？

输入格式

第一行有两个整数T（1 <= T <= 1000）和M（1 <= M <= 100），用一个空格隔开，T

代表总共能够用来采药的时间，M代表山洞里的草药的数目。接下来的M行每行包括两个在

1到100之间（包括1和100）的整数，分别表示采摘某株草药的时间和这株草药的价值。

输出格式

包括一行，这一行只包含一个整数，表示在规定的时间内，可以采到的草药的最大总价

值。

样例输入

70 3

71 100

69 1

1 2

样例输出

3

数据规模和约定

对于30%的数据，M <= 10；

对于全部的数据，M <= 100。

65. 开心的金明

问题描述

金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间他自己专用的很宽敞的

房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎 么布置，你

说了算，只要不超过N元钱就行”。今天一早金明就开始做预算，但是他想买的东西太多了，

肯定会超过妈妈限定的N元。于是，他把每件物品规定了一 个重要度，分为5等：用整数

1~5表示，第5等最重要。他还从因特网上查到了每件物品的价格（都是整数元）。他希望

在不超过N元（可以等于N元）的前提 下，使每件物品的价格与重要度的乘积的总和最大。

设第j件物品的价格为v[j]，重要度为w[j]，共选中了k件物品，编号依次为 j1，

j2，……，jk，则所求的总和为：

v[j1]*w[j1]+v[j2]*w[j2]+ …+v[jk]*w[jk]。（其中*为乘号）

请 你帮助金明设计一个满足要求的购物单。

输入格式

数

输入文件 的第1行，为两个正整数，用一个空格隔开：

N m

（其中N（<30000）表示总钱 数，m（<25）为希望购买物品的个数。）

从第2行到第m+1行，第j行给出了编号为j-1的物品的基本数据，每行有2个非负整

v p

（其中v表示该物品的价格(v<=10000)，p表示该物品的重要度(1~5)）

输出格式

输出文件只有一个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值

（<100000000）。

样例输入

1000 5

800 2

400 5

300 5

400 3

200 2

样例输出

3900

66. JAM计数法

问题描述

Jam是个喜欢标新立异的科学怪人。他不使用阿拉伯数字计数，而是使用小写英文字母

计数，他觉得这样做，会使世界更加丰富多彩。在他的计数法中，每个数字的位数都是相同

的（使用相同个数的字母），英文字母按原先的顺序，排在前面的字母小于排在它后面的字

母。我们把这样的“数字”称为Jam数字。在Jam数字中，每个字母互不相同，而且从左到

右是严格递增的。每次，Jam还指定使用字母的范围，例如，从2到10，表示只能使用

{b,c,d,e,f,g,h,i,j}这些字母。如果再规定位数为5，那么，紧接在Jam数字“bdfij”之

后的数字应该是“bdghi”。（如果我们用U、V依次表示Jam数字“bdfij”与“bdghi”，

则U，且不存在Jam数字P，使U）。你的任务是：对于从文件读入

的一个Jam数字，按顺序输出紧接在后面的5个Jam数字，如果后面没有那么多Jam数字，

那么有几个就输出几个。

输入格式

有2行，第1行为3个正整数，用一个空格隔开：

s t w

（其中s为所使用的最小的字母的序号，t为所使用的最大的字母的序号。w为数字的

位数，这3个数满足：1≤s

第2行为具有w个小写字母的字符串，为一个符合要求的Jam数字。

所给的数据都是正确的，不必验证。

输出格式

最多为5行，为紧接在输入的Jam数字后面的5个Jam数字，如果后面没有那么多Jam

数字，那么有几个就输出几个。每行只输出一个Jam数字，是由w个小写字母组成的字符串，

不要有多余的空格。

样例输入

2 10 5

bdfij

样例输出

bdghi

bdghj

bdgij

bdhij

befgh

67. 数列

问题描述

给定一个正整数k(3≤k≤15),把所有k的方幂及所有有限个互不相等的k的方幂之和

构成一个递增的序列，例如，当k=3时，这个序列是：

1，3，4，9，10，12，13，…

（该序列实际上就是：3，3，3+3，3，3+3，3+3，3+3+3，…）

请你求出这个序列的第N项的值（用10进制数表示）。

例如，对于k=3，N=100，正确答案应该是981。

输入格式

只有1行，为2个正整数，用一个空格隔开：

k N

（k、N的含义与上述的问题描述一致，且3≤k≤15，10≤N≤1000）。

输出格式

计算结果，是一个正整数（在所有的测试数据中，结果均不超过2.1*10）。（整数前

不要有空格和其他符号）。

9

样例输入

3 100

样例输出

981

68. 纪念品分组

问题描述

元旦快到了，校学生会让乐乐负责新年晚会的纪念品发放工作。为使得参加晚会的同学

所获得的纪念品价值 相对均衡，他要把购来的纪念品根据价格进行分组，但每组最多只能

包括两件纪念品，并且每组纪念品的价格之和不能超过一个给定的整数。为了保证在尽量短

的时 间内发完所有纪念品，乐乐希望分组的数目最少。

你的任务是写一个程序，找出所有分组方案中分组数最少的一种，输出最少的分组数目。

输入格式

输入包含n+2行：

第1行包括一个整数w，为每组纪念品价格之和的上限。

第2行为一个整数n，表示购来的纪念品的总件数。

第3~n+2行每行包含一个正整数p

i

(5 <= p

i

<= w)，表示所对应纪念品的价格。

输出格式

输出仅一行，包含一个整数，即最少的分组数目。

样例输入

100

9

90

20

20

30

50

60

70

80

90

样例输出

6

数据规模和约定

50%的数据满足：1 <= n <= 15

100%的数据满足：1 <= n <= 30000, 80 <= w <= 200

69. 传球游戏

问题描述

上体育课的时候，小蛮的老师经常带着同学们一起做游戏。这次，老师带着同学们一起

做传球游戏。

游戏规则是这样的：n个同学站成一个圆圈，其中的一个同学手里拿着一个球，当老师

吹哨子时开始传球，每个同学可以把球传给自己左右的两个同学中的一个（左右任意），当

老师再次吹哨子时，传球停止，此时，拿着球没传出去的那个同学就是败者，要给大家表演

一个节目。

聪明的小蛮提出一个有趣的问题：有多少种不同的传球方法可以使得从小蛮手里开始传

的球，传了m次以后，又回到小蛮手里。两种传球的方法被视作不同的方法，当且仅当这两

种方法中，接到球的同学按接球顺序组成的序列是不同的。比如有3个同学1号、2号、3

号，并假设小蛮为1号，球传了3次回到小蛮手里的方式有1->2->3->1和1->3->2->1，共

2种。

输入格式

共一行，有两个用空格隔开的整数n，m（3<=n<=30，1<=m<=30）。

输出格式

t共一行，有一个整数，表示符合题意的方法数。

样例输入

3 3

样例输出

2

数据规模和约定

40%的数据满足：3<=n<=30，1<=m<=20

100%的数据满足：3<=n<=30，1<=m<=30

70. 传纸条

问题描述

小渊和小轩是好朋友也是同班同学，他们在一起总有谈不完的话题。一次素质拓展活动

中，班上同学安排做成一个m行n列的矩阵，而小渊和小轩被安排在矩阵对角线的两端，因

此，他们就无法直接交谈了。幸运的是，他们可以通过传纸条来进行交流。纸条要经由许多

同学传到对方手里，小渊坐在矩阵的左上角，坐标(1,1)，小轩坐在矩阵的右下角，坐标(m,n)。

从小渊传到小轩的纸条只可以向下或者向右传递，从小轩传给小渊的纸条只可以向上或者向

左传递。

在活动进行中，小渊希望给小轩传递一张纸条，同时希望小轩给他回复。班里每个同学

都可以帮他们传递，但只会帮他们一次，也就是说如果此人在小渊递给小轩纸条的时候帮忙，

那么在小轩递给小渊的时候就不会再帮忙。反之亦然。

还有一件事情需要注意，全班每个同学愿意帮忙的好感度有高有低（注意：小渊和小轩

的好心程度没有定义，输入时用0表示），可以用一个0-100的自然数来表示，数越大表示

越好心。小渊和小轩希望尽可能找好心程度高的同学来帮忙传纸条，即找到来回两条传递路

径，使得这两条路径上同学的好心程度只和最大。现在，请你帮助小渊和小轩找到这样的两

条路径。

输入格式

输入第一行有2个用空格隔开的整数m和n，表示班里有m行n列（1<=m,n<=50）。

接下来的m行是一个m*n的矩阵，矩阵中第i行j列的整数表示坐在第i行j列的学生

的好心程度。每行的n个整数之间用空格隔开。

输出格式

输出一行，包含一个整数，表示来回两条路上参与传递纸条的学生的好心程度之和的最

大值。

样例输入

3 3

0 3 9

2 8 5

5 7 0

样例输出

34

数据规模和约定

30%的数据满足：1<=m,n<=10

100%的数据满足：1<=m,n<=50

71. Hankson的趣味题

问题描述

Hanks 博士是BT (Bio-Tech，生物技术) 领域的知名专家，他的儿子名叫Hankson。现

在，刚刚放学回家的Hankson 正在思考一个有趣的问题。 今天在课堂上，老师讲解了如何

求两个正整数c1 和c2 的最大公约数和最小公倍数。现 在Hankson 认为自己已经熟练地

掌握了这些知识，他开始思考一个“求公约数”和“求公 倍数”之类问题的“逆问题”，

这个问题是这样的：已知正整数a0,a1,b0,b1，设某未知正整 数x 满足： 1． x 和a0 的

最大公约数是a1； 2． x 和b0 的最小公倍数是b1。 Hankson 的“逆问题”就是求出满

足条件的正整数x。但稍加思索之后，他发现这样的 x 并不唯一，甚至可能不存在。因此

他转而开始考虑如何求解满足条件的x 的个数。请你帮 助他编程求解这个问题。

输入格式

输入第一行为一个正整数n，表示有n 组输入数据。

接下来的n 行每 行一组输入数据，为四个正整数a0，a1，b0，b1，每两个整数之间用

一个空格隔开。输入 数据保证a0 能被a1 整除，b1 能被b0 整除。

输出格式

输出共n 行。每组输入数据的输出结果占一行，为一个整数。

对于每组数据：若不存在这样的 x，请输出0； 若存在这样的 x，请输出满足条件的x

的个数；

样例输入

2

41 1 96 288

95 1 37 1776

样例输出

6

2

样例说明

第一组输入数据，x 可以是9、18、36、72、144、288，共有6 个。

第二组输入数据，x 可以是48、1776，共有2 个。

数据规模和约定

对于 50%的数据，保证有1≤a0，a1，b0，b1≤10000 且n≤100。

72. 接水问题

问题描述

学校里有一个水房，水房里一共装有m 个龙头可供同学们打开水，每个龙头每秒钟的

供水量相等，均为1。 现在有n 名同学准备接水，他们的初始接水顺序已经确定。将这些

同学按接水顺序从1 到n 编号，i 号同学的接水量为wi。接水开始时，1 到m 号同学各占

一个水龙头，并同时打 开水龙头接水。当其中某名同学j 完成其接水量要求wj 后，下一

名排队等候接水的同学k 马上接替j 同学的位置开始接水。这个换人的过程是瞬间完成的，

且没有任何水的浪费。即 j 同学第x 秒结束时完成接水，则k 同学第x+1 秒立刻开始接

水。若当前接水人数n’不足m， 则只有n’个龙头供水，其它m−n’个龙头关闭。 现在给

出n 名同学的接水量，按照上述接水规则，问所有同学都接完水需要多少秒。

输入格式

第1 行2 个整数n 和m，用一个空格隔开，分别表示接水人数和龙头个数。 第2 行n

个整数w1、w2、……、wn，每两个整数之间用一个空格隔开，wi 表示i 号同 学的接水量。

输出格式

输出只有一行，1 个整数，表示接水所需的总时间。

样例输入

5 3

4 4 1 2 1

样例输出

4

样例输入

8 4

23 71 87 32 70 93 80 76

样例输出

163

输入输出样例 1 说明

第1 秒，3 人接水。第1 秒结束时，1、2、3 号同学每人的已接水量为1，3 号同学

接完

水，4 号同学接替3 号同学开始接水。

第2 秒，3 人接水。第2 秒结束时，1、2 号同学每人的已接水量为2，4 号同学的已

接

水量为1。

第3 秒，3 人接水。第3 秒结束时，1、2 号同学每人的已接水量为3，4 号同学的已

接

水量为2。4 号同学接完水，5 号同学接替4 号同学开始接水。

第4 秒，3 人接水。第4 秒结束时，1、2 号同学每人的已接水量为4，5 号同学的已

接

水量为1。1、2、5 号同学接完水，即所有人完成接水。

总接水时间为4 秒。

数据规模和约定

1 ≤ n ≤ 10000，1 ≤m≤ 100 且m≤ n；

1 ≤ wi ≤ 100。

73. 数组排序去重

问题描述

输入10个整数组成的序列，要求对其进行升序排序，并去掉重复元素。

输入格式

10个整数。

输出格式

多行输出，每行一个元素。

样例输入

2 2 3 3 1 1 5 5 5 5

样例输出

1

2

3

5

74. 会议中心

会议中心 Siruseri政府建造了一座新的会议中心。许多公司对租借会议中心的会

堂很感兴趣，他们希望能够在里面举行会议。

对于一个客户而言，仅当在开会时能够独自占用整个会堂，他才会租借会堂。会议中心

的销售主管认为：最好的策略应该是将会堂租借给尽可能多的客户。显然，有可能存在不止

一种满足要求的策略。

例如下面的例子。总共有4个公司。他们对租借会堂发出了请求，并提出了他们所需占

用会堂的起止日期（如下表所示）。

开始日期 结束日期

公司1 4 9

公司2 9 11

公司3 13 19

公司4 10 17

上例中，最多将会堂租借给两家公司。租借策略分别是租给公司1和公司3，或是公司

2和公司3，也可以是公司1和公司4。注意会议中心一天最多租借给一个公司，所以公司1

和公司2不能同时租借会议中心，因为他们在第九天重合了。

销售主管为了公平起见，决定按照如下的程序来确定选择何种租借策略：首先，将租借

给客户数量最多的策略作为候选，将所有的公司按照他们发出请求的顺序编号。对于候选策

略，将策略中的每家公司的编号按升序排列。最后，选出其中字典序最小[1]的候选策略作

为最终的策略。

例中，会堂最终将被租借给公司1和公司3：3个候选策略是{(1,3),(2,3),(1,4)}。而

在字典序中(1,3)<(1,4)<(2,3)。

你的任务是帮助销售主管确定应该将会堂租借给哪些公司。

输入格式

输入的第一行有一个整数N，表示发出租借会堂申请的公司的个数。第2到第N+1行每

行有2个整数。第i+1行的整数表示第i家公司申请租借的起始和终止日期。对于每个公司

9

的申请，起始日期为不小于1的整数，终止日期为不大于10的整数。

输出格式

输出的第一行应有一个整数M，表示最多可以租借给多少家公司。第二行应列出M个数，

表示最终将会堂租借给哪些公司。

数据规模和约定

对于50%的输入，N≤3000。在所有输入中，N≤200000。

样例输入

4

4 9

9 11

13 19

10 17

样例输出

2

1 3

[1] 字典序指在字典中排列的顺序，如果序列l

1

是序列l

2

的前缀，或者对于l

1

和l

2

的第一

个不同位置j，l

1

[j]

2

[j]，则l

1

比l

2

小。

75. 弹弹堂

问题描述

XX无聊玩弹弹堂，战斗力太低啦！

输入格式

测试数据的输入一定会满足的格式。

例：输入的第一行包含两个整数n, m，分别表示矩阵的行数和列数。接下来n行，每

行m个正整数，表示输入的矩阵。

输出格式

要求用户的输出满足的格式。

例：输出1行，包含一个整数，表示矩阵中所有元素的和。

样例输入

一个满足题目要求的输入范例。

例：

2 2

1 2

3 4

样例输出

与上面的样例输入对应的输出。

例：

10

数据规模和约定

输入数据中每一个数的范围。