蓝桥杯练习系统非VIP习题

蓝桥杯练习系统非VIP练习题

入门训练

1.Fibonacci数歹!J

问题描述

Fibonacci数列的递推公式为：冗=心+口，其中FFFFI。

当n比较大时，F.也非常大，现在我们想知道，F,除以10007的余数是多少。

输入格式

输入包含一个整数n。

输出格式

输出一行，包含一个整数，表示F,除以10007的余数。

说明：在本题中，答案是要求F.除以10007的余数，因此我们只要能算出这个余数即可，而不需要先

计算出的准确值，再将计算的结果除以10007取余数，直接计算余数往往比先算出原数再取余简单。

样例输入

10

样例输出

55

样例输入

22

样例输出

7704

数据规模与约定

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

2.圆的面积

问题描述

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

输入格式

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

输出格式

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

说明：在本题中，输入是一个整数，但是输出是一个实数。

对于实数输出的问题，请一定看清楚实数输出的要求，比如本题中要求保留小数点后7位，则你的程

序必须严格的输出7位小数，输出过多或者过少的小数位数都是不行的，都会被认为错误。

实数输出的问题如果没有特别说明，舍入都是按四舍五入进行。

样例输入

4

样例输出

50.2654825

数据规模与约定

1<=r<=10000c

提ZE

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

PI=3.14159265358979323,也可以使用数学公式来求n,比如PI=atan(l.0)*4。

3.序列求和

问题描述

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

输入格式

输入包括一个整数n。

输出格式

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

样例输入

4

样例输出

10

样例输入

100

说明：有一些试题会给出多组样例输入输出以帮助你更好的做题。

一般在提交之前所有这些样例都需要测试通过才行，但这不代表这几组样例数据都正确了你的程序就是完

全正确的，潜在的错误可能仍然导致你的得分较低。

样例输出

5050

数据规模与约定

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

说明：请注意这里的数据规模。

本题直接的想法是直接使用一个循环来累加，然而，当数据规模很大时，这种“暴力”的方法往往会

导致超时。此时你需要想想其他方法。你可以试一试，如果使用1000000000作为你的程序的输入，你的程

序是不是能在规定的上面规定的时限内运行出来。

本题另一个要值得注意的地方是答案的大小不在你的语言默认的整型(int)范围内，如果使用整型来保

存结果，会导致结果错误。

如果你使用C++或C语言而且准备使用printf输出结果，则你的格式字符串应该写成％164d以输出long

long类型的整数。

4.入门训练A+B问题

时间限制：1.0s内存限制：256.0MB

问题描述

输入A、B,输出A+Bo

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

输入格式

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

说明：“输入格式”是描述在测试你的程序时，所给的输入一定满足的格式。

做题时你应该假设所给的输入是一定满足输入格式的要求的，所以你不需要对输入的格式进行检查。

多余的格式检查可能会适得其反，使用你的程序错误。

在测试的时候，系统会自动将输入数据输入到你的程序中，你不能给任何提示。比如，你在输入的时

候提示“请输入A、B”之类的话是不需要的，这些多余的输出会使得你的程序被判定为错误。

输出格式

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

说明：“输出格式”是要求你的程序在输出结果的时候必须满足的格式。

在输出时，你的程序必须满足这个格式的要求，不能少任何内容，也不能多任何内容。如果你的内容

和输出格式要求的不一样，你的程序会被判断为错误，包括你输出了提示信息、中间调试信息、计时或者

统计的信息等。

样例输入

1245

说明：“样例输入”给出了一组满足“输入格式”要求的输入的例子。

这里给出的输入只是可能用来测试你的程序的一个输入，在测试的时候，还会有更多的输入用来测试你的

程序。

样例输出

57

说明：“样例输出”给出了一组满足“输出格式”要求的输出的例子。

样例输出中的结果是和样例输入中的是对应的，因此，你可以使用样例的输入输出简单的检查你的程序。

要特别指出的是，能够通过样例输入输出的程序并不-一定是正确的程序，在测试的时候，会用很多组数据

进行测试，而不局限于样例数据。有可能一个程序通过了样例数据，但测试的时候仍只能得0分，可能因

为这个程序只在一些类似样例的特例中正确，而不具有通用性，再测试更多数据时会出现错误。

比如，对于本题，如果你写一个程序不管输入是什么都输入57,则样例数据是对的，但是测试其他数据，

哪怕输入是1和2,这个程序也输出57,则对于其他数据这个程序都不正确。

数据规模与约定

-10000<=A,B<=10000»

说明：“数据规模与约定”中给出了试题中主要参数的范围。

这个范围对于解题非常重要，不同的数据范围会导致试题需要使用不同的解法来解决。比如本题中给

的A、B范围不大，可以使用整型(int)来保存，如果范围更大，超过int的范围，则要考虑其他方法来保

存大数。

有一些范围在方便的时候是在“问题描述”中直接给的，所以在做题时不仅要看这个范围，还要注意

问题描述。

提示

本题的C++源代码如下：

1.#include<iostream>

2.

3.usingnamespacestd;

4.

5.intmain()

6.(

7.inta,b;

8.cin»a»b;

9.cout«a+b；

10.return0;

11.)

本题的c源代码如下：

1.#include<stdio.h>

2.

3.intmainO

4.(

5.inta,b;

6.scanf("%d%d”,&a,&b);

7.printf("%d”,a+b);

8.return0;

9.)

本题的Java源代码如下：

1.importjava.util.*;

2.

3.publicclassMain

4.(

5.publicstaticvoidmain(Stringargs[])

6.(

7.Scannersc=newScanner(System,in)

8.Integera=sc.nextlnt();

9.Integerb=sc.nextlnt();

10.System,out.println(a+b);

11.)

12.}

说明：要答题，请点击页面上方的“提交此题”按钮，页面将跳转到提交代码的页面，选择好你的编

译语言，将你的编写好的代码粘贴到代码框中，再点击“提交答案”即可。

你的答案提交给系统后系统会自动对你的代码进行判分，并跳转到结果的列表里面，你可以直接从列

表中看到你提交的代码的状态，一般几秒钟后就可以看到判分的结果。

本题作为第一题，在提示中己经分别给了C++和Java的代码，你可以直接把这个代码拷贝过去作为自

己的代码提交。

请特别注意，Java的主类名必须是Main。

基础练习

1.数列排序

时间限制：1.0s内存限制：512.OMB

问题描述

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

输入格式

第一行为一个整数n。

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

输出格式

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

样例输入

5

83649

样例输出

34689

十六进制转八进制

时间限制：1.0s内存限制：512.0MB

问题描述

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

输入格式

输入的第一行为一个正整数n(l<=n<=10)»

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

进制数长度不超过100000o

输出格式

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

【注意】

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

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

样例输入

2

39

123ABC

样例输出

71

4435274

【提示】

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

十六进制转十进制

时间限制:1.0s内存限制:512.0MB

问题描述

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

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

样例输入

FFFF

样例输出

65535

十进制转十六进制

时间限制：1.0s内存限制:512.0MB

问题描述

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

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

样例输出

IE

特殊回文数

时间限制：1.0s内存限制:512.0MB

问题描述

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

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

输入格式

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

输出格式

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

样例输入

52

样例输出

899998

989989

998899

数据规模和约定

l〈=n<=54。

回文数

时间限制：1.0s内存限制:512.0MB

问题描述

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

输出格式

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

特殊的数字

时间限制:1.0s内存限制:512.0MB

问题描述

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

足这种条件的三位十进制数。

输出格式

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

杨辉三角形

时间限制：1.0s内存限制:256.0MB

问题描述

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

它的一个重要性质是：三角形中的每个数字等于它两肩上的数字相加。

下面给出了杨辉三角形的前4行：

1

11

121

1331

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

输入格式

输入包含一个数no

输出格式

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

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

样例输入

4

样例输出

1

11

121

1331

数据规模与约定

1<=n<=34。

查找整数

时间限制：1.0s内存限制:256.0MB

问题描述

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

输入格式

第一行包含一个整数n。

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

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

输出格式

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

样例输入

6

194839

9

样例输出

2

数据规模与约定

1<=n<=1000«

数列特征

时间限制:1.0s内存限制:256.0MB

问题描述

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

输入格式

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

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

输出格式

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

示这些数的和。

样例输入

5

13-245

样例输出

5

-2

11

数据规模与约定

1<=n<=10000c

字母图形

时间限制：1.0s内存限制：256.OMB

问题描述

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

ABCDEFG

BABCDEF

CBABCDE

DCBABCD

EDCBABC

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

输入格式

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

输出格式

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

样例输入

57

样例输出

ABCDEFG

BABCDEF

CBABCDE

DCBABCD

EDCBABC

数据规模与约定

1<=n,m<=26。

01字串

时间限制：1.0s内存限制;256.0MB

问题描述

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

00000

00001

00010

00011

00100

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

输入格式

本试题没有输入。

输出格式

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

样例输出

00000

00001

00010

00011

〈以下部分省略〉

闰年判断

时间限制：1.0s内存限制：256.0MB

问题描述

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

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

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

2,年份是400的倍数。

其他的年份都不是闰年。

输入格式

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

输出格式

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

说明：当试题指定你输出一个字符串作为结果（比如本题的yes或者no,你需要严格按照试题中给定

的大小写，写错大小写将不得分。

样例输入

2013

样例输出

no

样例输入

2016

样例输出

yes

数据规模与约定

1990<=y<=2050,

算法训练

C++CH0801

时间限制:1.0s内存限制:256.0MB

问题描述

已知一个有理数类Zrf_Ratio,实现如下的操作符重载形式：

friendstd::ostream&operator«(std::ostream&,constzrf_Ratio&);〃输出最简分数

friendstd::istream&operator»(std::istreamft,zrfRatio&);

friendbooloperator==(constzrf_Ratio&,constzrf_Ratio&);

friendbooloperator<(constzrf_Ratio&,constzrf_Ratio&);

测试

测试时主程序会输入四个整数a,b,c,d,表示两个分数a/b和c/d。要求输出最简分数以及两个分

数相等和大小的比较结果。

样例输入

172625

样例输出

zrfis:1/7;sshis:26/25

(zrf==ssh)is:0;(zrf<ssh)is:1

Interval

时间限制：1.0s内存限制:256.0MB

问题描述

这里写问题描述。

输入格式

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

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

表示输入的矩阵。

输出格式

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

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

样例输入

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

例：

22

12

34

样例输出

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

例：

10

数据规模和约定

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

例：0<n,m<100,0〈=矩阵中的每个数〈=1000。

6-1递归求二项式系数值

时间限制:10.0s内存限制：256.0MB

问题描述

已知公=已一卜=°或卜=1使用递归方法求哈,

I瑞_1+C㈡Q<k<n

样例输入

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

310

样例输出

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

数据规模和约定

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

例：结果在int表示时不会溢出。

5-1最小公倍数

时间限制:1.0s内存限制：256.0MB

问题描述

编写一函数1cm,求两个正整数的最小公倍数。

样例输入

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

例：

35

样例输出

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

例：

35

工5请按任意键继续・.・

数据规模和约定

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

例：两个数都小于65536。

P1103

时间限制：1.0s内存限制:256.0MB

编程实现两个复数的运算。设有两个复数和，则他们的运算公式为:

要求：(1)定义一个结构体类型来描述复数。

(2)复数之间的加法、减法、乘法和除法分别用不用的函数来实现。

(3)必须使用结构体指针的方法把函数的计算结果返回。

说明：用户输入：运算符号(+,-,*,/)abed.

输出：a+bi,输出时不管a,b是小于0或等于0都按该格式输出，输出时a,b都保留两位。

输入：

-2.53.61.54.9

输出：

1.00+-1.30i

LiftandThrow

时间限制：3.0s内存限制：256.OMB

问题描述

给定一条标有整点(1,2,3,...)的射线.定义两个点之间的距离为其下标之差的绝对值.

Lahar1,Etna,Flonne一开始在这条射线上不同的三个点，他们希望其中某个人能够到达下标最大的

点.

每个角色只能进行下面的3种操作，且每种操作不能每人不能进行超过一次.

1.移动一定的距离

2.把另一个角色高举过头

3.将举在头上的角色扔出一段距离

每个角色有一个movementrange参数，他们只能移动到没有人的位置，并且起点和终点的距离不超过

movementrange.

如果角色A和另一个角色B距离为1,并且角色B没有被别的角色举起，那么A就能举起B.同时，B

会移动到A的位置,B原来所占的位置变为没有人的位置.被举起的角色不能进行任何操作，举起别人的角

色不能移动.同时，每个角色还有一个throwingrange参数，即他能把举起的角色扔出的最远的距离.注

意，一个角色只能被扔到没有别的角色占据的位置.我们认为一个角色举起另一个同样举起一个角色的角

色是允许的.这种情况下会出现3个人在同一个位置的情况.根据前面的描述，这种情况下上面的两个角

色不能进行任何操作，而最下面的角色可以同时扔出上面的两个角色.你的任务是计算这些角色能够到达

的位置的最大下标，即最大的数字x,使得存在一个角色能够到达X.

输入格式

输入共三行，分别为Lahar1,Etna,Floone的信息.

每一行有且仅有3个整数，描述对应角色的初始位置，movementrange,throwingrange.

数据保证3个角色的初始位置两两不相同且所有的数字都在1到L0之间.</div>

输出格式

仅有1个整数，即Laha个,Etna,Flonne之一能到达的最大距离.

样例输入

933

431

233

样例输出

15

样例说明

一开始Lahar1在位置9,Etna在位置4,Flonne在位置2.

首先，Lahar1移动到6.

然后Flonne移动到位置5并且举起Etna.

Lahar1举起Flonne将其扔到位置9.

Flonne把Etna扔到位置12.

Etna移动到位置15.

Multithreading

时间限制:1.0s内存限制:256.OMB

问题描述

现有如下一个算法：

repeatnitimes

yi:二y

y:=yi+1

endrepeat

令n[l]为你需要算加法的第一个数字，n[2]为第二个，...n[N]为第N个数字（N为需要算加法的数字

个数），

并令y初始值为0,先令i=l运行这个算法（如上所示，重复n[i]次），然后令i=2运行这个算法。。

直到i=No注意y值一直不要清零。最后y的值就是你需要的加法答案。

你想知道，有没有某种运算顺序能使答案等于也

一个循环中的全部语句，是不能改变在总的语句排列中的相对顺序的.

（这里的第i个循环是指这n[i]*2条语句。就是你把属于第i个循环的语句抽出来看，它们需要按照

原顺序排列。在你没有运行完这个循环的最靠前一条未完成的语句的时候，你是不能跳过它先去完成这个

循环后面的语句的。你能做的仅是把若干个循环按照你所规定的顺序“归并”起来。）

举个例子，n[l]=2,n[2]=l,W=l.一种可行的运算顺序是"211112"，数字为几表示运行第几

个算法的下一条语句（你可以看到“1”出现了4次，是因为n[l]=2即循环两次，而每次循环里面有两条

语句，所以2*2=4次）

y值y[l]值y⑵

执行0条语句过后000

执行1条过后(y[2]=y)000

执行2条过后(y[l]=y)000

执行3条过后(y=y[l]+l)100

执行4条过后(y[l]=y)110

执行5条过后(y=y[l]+l)210

执行6条过后(y=y[2]+l)110

可以看到，最后y值变成了1,也就完成了我们的任务。

输入格式

第一行你会得到用空格分开的两个整数N(K=N<=100)和W(-10-9<=W<=10-9),(N为需要算加法的数字

个数，W是你希望算出的数)。

第二行你会得到n个整数n[i](l<=n[i]<=1000).

输出格式

第一行您应该输出Yes(若能以某种顺序使得这个算法得出W的值)或Noo

如果第一行是No,接下来就不用继续输出了。

如果是Yes,请在第2行输出2*sigma(n[i])个用空格隔开的数，表示任意一种满足条件的运算顺序.

样例输入

110

11

样例输出

样例输入

23

44

样例输出

Yes

1121222221211112

样例输入

36

123

样例输出

Yes

112222333333

数据规模和约定

对于30%的数据,n<=4,n[i]的和小于10.

对于100%的数据，n<=100,-10^9<=W<=10^9,K=n[i]<=1000

TrickyandCleverPassword

时间限制:2.Os内存限制:256.OMB

问题描述

在年轻的时候，我们故事中的英雄一一国王Copa一一他的私人数据并不是完全安全地隐蔽。对他来说

是，这不可接受的。因此，他发明了一种密码，好记又难以破解。后来，他才知道这种密码是一个长度为

奇数的回文串。

Copa害怕忘记密码，所以他决定把密码写在一张纸上.他发现这样保存密码不安全，于是他决定按下

述方法加密密码：他选定一个整数X,保证X不小于0,且2X严格小于串长度。然后他把密码分成3

段，最前面的X个字符为一段，最后面的X个字符为一段，剩余的字符为一段。不妨把这三段依次称之

为prefix,suffix,middle。显然，middle的长度为一个大于0的奇数，且prefix、suffix的长

度相等。他加密后的密码即为A+prefix+B+middle+C+suffix,其中A、B、C是三个由Copa

选定的字符串，且都有可能为空，+表示字符串相连。

许多年过去了。Copa昨天找到了当年写下加密后字符串的那张纸。但是，Copa把原密码、A、B、C都

忘了。现在，他请你找一个尽量长的密码，使得这个密码有可能被当年的Copa发明、加密并写下。

输入格式

输入包含一个只含有小写拉丁字母的字符串，长度在1到10~5之内。

输出格式

第一行包含一个整数k,表示你找到的原密码分成的3个部分中有多少个非空字符串。显然kin{1,

3}o接下来k行，每行2个用空格分开的整数xi1J,表示这一部分的起始位置和长度。要求输出

的x_i递增。

起始位置x_i应该在1到加密后的字符串长度之间。l_i必须是正整数，因为你只要输出非空部分

的信息。middle的长度必须为奇数。

如果有多组答案，任意一组即可。提示：你要最大化的是输出的1」的总和，而不是kO

样例输入

abacaba

样例输出

1

17

样例输入

axbya

样例输出

3

11

21

51

样例输入

xabyczba

样例输出

3

22

41

72

数据规模和约定

对于10%的数据：n<=10

对于30%的数据：n<=100

对于100%的数据：n<=100000

存在20%的数据，输出文件第一行为1。

TrickyandCleverPassword

时间限制：2.0s内存限制:256.0MB

问题描述

在年轻的时候，我们故事中的英雄一一国王Copa一一他的私人数据并不是完全安全地隐蔽。对他来说

是，这不可接受的。因此，他发明了一种密码，好记又难以破解。后来，他才知道这种密码是一个长度为

奇数的回文串。

Copa害怕忘记密码，所以他决定把密码写在一张纸上。他发现这样保存密码不安全，于是他决定按下

述方法加密密码：他选定一个整数X,保证X不小于0,且2X严格小于串长度。然后他把密码分成3

段，最前面的X个字符为一段，最后面的X个字符为一段，剩余的字符为一段。不妨把这三段依次称之

为prefix,suffix,middle。显然，middle的长度为一个大于0的奇数，且prefix、suffix的长

度相等。他加密后的密码即为A+prefix+B+middle+C+suffix,其中A、B、C是三个由Copa

选定的字符串，且都有可能为空，+表示字符串相连。

许多年过去了。Copa昨天找到了当年写下加密后字符串的那张纸。但是，Copa把原密码、A、B、C都

忘了。现在，他请你找一个尽量长的密码，使得这个密码有可能被当年的Copa发明、加密并写下。

输入格式

输入包含一个只含有小写拉丁字母的字符串，长度在1到10"5之内。

输出格式

第一行包含一个整数k,表示你找到的原密码分成的3个部分中有多少个非空字符串。显然kin{1,

3}。接下来k行，每行2个用空格分开的整数x_il_i,表示这一部分的起始位置和长度。要求输出

的x_i递增。

起始位置x_i应该在1到加密后的字符串长度之间。1」必须是正整数，因为你只要输出非空部分

的信息。middle的长度必须为奇数。

如果有多组答案，任意一组即可。提示：你要最大化的是输出的1」的总和，而不是ko

样例输入

abacaba

样例输出

1

17

样例输入

axbya

样例输出

3

11

21

51

样例输入

xabyczba

样例输出

3

22

41

72

数据规模和约定

对于10%的数据：n<=10

对于30%的数据：n<=100

对于100%的数据：n<=100000

存在20%的数据，输出文件第一行为1。

Beaver'sCalculator

时间限制：3.0s内存限制：256.0MB

问题描述

从万能词典来的聪明的海狸已经使我们惊讶了一次。他开发了一种新的计算器，他将此命名为

“Beaver'sCalculator1.0"。它非常特别，并且被计划使用在各种各样的科学问题中。

为了测试它，聪明的海狸邀请了n位科学家，编号从1到n。第i位科学家给这个计算器带来了k.

个计算题。第i个科学家带来的问题编号1到n,并且它们必须按照编号一个一个计算，因为对于每个问题

的计算都必须依赖前一个问题的计算结果。

每个教授的每个问题都用一个数a,.,来描述，i(lWiWn)是科学家的编号，j(lWjWk,)是

问题的编号，a..,表示解决这个问题所需资源单位的数量。

这个计算器非常不凡。它一个接一个的解决问题。在一个问题解决后，并且在下一个问题被计算前，

计算器分配或解放资源。

计算器中最昂贵的操作是解放资源，解放远远慢于分配。所以对计算器而言，每一个接下来的问题所

需的资源不少于前一个，是非常重要的。

给你关于这些科学家所给问题的相关信息。你需要给这些问题安排一个顺序，使得“坏对”尽可能少。

所谓“坏对”，就是相邻两个问题中，后一个问题需求的资源比前一个问题少。别忘了，对于同一个

科学家给出的问题，计算它们的相对顺序必须是固定的。

输入格式

第一行包含一个整数n,表示科学家的人数。接下来n行每行有5个整数，左，a,„x“y,,m.(0

Wa一〈如W10”，1W居y.W10"),分别表示第i个科学家的问题个数，第1个问题所需资源单

位数，以及3个用来计算a.,的参量。a…=(a,.>,*x,+y,)modm；

输出格式

第一行输出一个整数，表示最优顺序下最少的“坏对”个数。

如果问题的总个数不超过200000,接下来输出£自行，表示解决问题的最优顺序。每一行两个用

空格隔开的整数，表示这个问题所需的资源单位数和提供这个问题的科学家的编号。

样例输入

2

211110

231110

样例输出

11

21

32

42

数据规模和约定

20%的数据〃=2,1W鼠W2000；

另外30%的数据n=2,\Wk,W200000；

剩下50%的数据1W〃W5000,1WLW5000»

Cowboys

时间限制:2.0s内存限制：256.0MB

问题描述

一个间不容发的时刻：n个牛仔站立于一个环中，并且每个牛仔都用左轮手枪指着他旁边的人！每个牛

仔指着他顺时针或者逆时针方向上的相邻的人。正如很多西部片那样，在这一刻，绳命是入刺的不可惜……

对峙的场景每秒都在变化。每秒钟牛仔们都会分析局势，当一对相邻的牛仔发现他们正在互指的时候，就

会转过身。一秒内每对这样的牛仔都会转身。所有的转身都同时在一瞬间发生。我们用字母来表示牛仔所

指的方向。“A”表示顺时针方向，“B”表示逆时针方向。如此，一个仅含“A”“B”的字符串便用来表

示这个由牛仔构成的环。这是由第一个指着顺时针方向的牛仔做出的记录。例如，牛仔环“ABBBABBBA”在

一秒后会变成“BABBBABBA”；而牛仔环“BABBA”会变成“ABABB"。这幅图说明了“BABBA”怎么变成"ABABB”

一秒过去了，现在用字符串s来表示牛仔们的排列。你的任务是求出一秒前有多少种可能的排列。如果某

个排列中一个牛仔指向顺时针，而在另一个排列中他指向逆时针，那么这两个排列就是不同的。

输入格式

输入数据包括一个字符串S,它只含有“A”和“B”。

输出格式

输出你求出来的一秒前的可能排列数。

数据规模和约定

s的长度为3到100(包含3和100)

样例输入

BABBBABBA

样例输出

2

样例输入

ABABB

样例输出

2

样例输入

ABABAB

样例输出

4

样例说明

测试样例一中，可能的初始排列为："ABBBABBAB"和"ABBBABBBA"。

测试样例二中，可能的初始排列为："AABBB"和"BABBA”。

数字三角形

时间限制:1.0s内存限制:256.0MB

问题描述

(图3.1—1)示出了一个数字三角形。请编一个程序计算从顶至底的某处的一条路

径，使该路径所经过的数字的总和最大。

・每一步可沿左斜线向下或右斜线向下走；

•1〈三角形行数W100；

•三角形中的数字为整数0,1,…99；

7

38

810

2744

45265.

（图3.1—1）

输入格式

文件中首先读到的是三角形的行数。

接下来描述整个三角形

输出格式

最大总和（整数）

样例输入

5

7

38

810

2744

45265

样例输出

30

未名湖边的烦恼

时间限制：LOs内存限制：256.OMB

问题描述

每年冬天，北大未名湖上都是滑冰的好地方。北大体育组准备了许多冰鞋，可是人太多了，每天下午

收工后，常常一双冰鞋都不剩。

每天早上，租鞋窗口都会排起长龙，假设有还鞋的m个，有需要租鞋的n个。现在的问题是，这些人

有多少种排法，可以避免出现体育组没有冰鞋可租的尴尬场面。（两个同样需求的人（比如都是租鞋或都

是还鞋）交换位置是同一种排法）

输入格式

两个整数，表示in和n

输出格式

一个整数，表示队伍的排法的方案数。

样例输入

32

样例输出

5

数据规模和约定

m,[0,18]

问题分析

最大的算式

时间限制：1.0s内存限制:256.0MB

问题描述

题目很简单，给出N个数字，不改变它们的相对位置，在中间加入K个乘号和N-KT个加号，(括号

随便加)使最终结果尽量大。因为乘号和加号一共就是N-1个了，所以恰好每两个相邻数字之间都有一个

符号。例如：

N=5,K=2,5个数字分别为1、2、3、4、5,可以加成：

1*2*(3+4+5)=24

1*(2+3)*(4+5)=45

(1*2+3)*(4+5)=45

输入格式

输入文件共有二行，第一行为两个有空格隔开的整数，表示N和K,其中(2<=N<=15,0<=K<=N-l)o

第二行为N个用空格隔开的数字(每个数字在0到9之间)。

输出格式

输出文件仅一行包含一个整数，表示要求的最大的结果

样例输入

52

12345

样例输出

120

样例说明

(1+2+3)*4*5=120

图形显示

时间限制：1.0s内存限制：512.0MB

问题描述

编写一个程序，首先输入一个整数，例如5,然后在屏幕上显示如下的图形（5表示行数）：

****

***

**

*

排序

时间限制:1.0s内存限制：512.0MB

问题描述

编写一个程序，输入3个整数，然后程序将对这三个整数按照从大到小进行排列。

输入格式：输入只有一行，即三个整数，中间用空格隔开。

输出格式：输出只有一行，即排序后的结果。

输入输出样例

样例输入

9230

样例输出

3092

2的次塞表示

时间限制：1.0s内存限制：512.0MB

问题描述

任何一个正整数都可以用2进制表示，例如：137的2进制表示为10001001c

将这种2进制表示写成2的次暴的和的形式，令次事高的排在前面，可得到如下表达式：

137=2-7+2-3+2-0

现在约定募次用括号来表示，即a~b表示为a(b)

此时，137可表示为：2(7)+2(3)+2(0)

进一步：7=212+2+2-。(21用2表示)

3=2+2'0

所以最后137可表示为：2(2(2)+2+2(0))+2(2+2(0))+2(0)

又如：1315=210+2~8+2.5+2+1

所以1315最后可表示为：

2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0)

输入格式

正整数(1烂n<=20000)

输出格式

符合约定的n的0,2表示(在表示中不能有空格)

样例输入

137

样例输出

2(2(2)+2+2(0))+2(2+2(0))+2(0)

样例输入

1315

样例输出

2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0)

提示

用递归实现会比较简单，可以一边递归一边输出

前缀表达式

时间限制：1.0s内存限制:512.OMB

问题描述

编写一个程序，以字符串方式输入一个前缀表达式，然后计算它的值•输入格式为：“运算符对象1对

象2"，其中，运算符为“+”(加法)、(减法)、“*”(乘法)或“/”(除法)，运算对象为不

超过10的整数，它们之间用一个空格隔开。要求：对于加、减、乘、除这四种运算，分别设计相应的函数

来实现。

输入格式：输入只有一行，即一个前缀表达式字符串。

输出格式：输出相应的计算结果（如果是除法，直接采用C语言的“/”运算符，结果为整数）。

输入输出样例

样例输入

+52

样例输出

7

Anagrams问题

时间限制：1.0s内存限制:512.0MB

问题描述

Anagrams指的是具有如下特性的两个单词：在这两个单词当中，每一个英文字母（不区分大小写）所

出现的次数都是相同的。例如，“Unclear”和“Nuclear"、“Rimon”和“MinOR”都是Anagrams。编写

一个程序，输入两个单词，然后判断一下，这两个单词是否是Anagrams。每一个单词的长度不会超过80个

字符，而且是大小写无关的。

输入格式：输入有两行，分别为两个单词。

输出格式：输出只有一个字母Y或N,分别表示Yes和No。

输入输出样例

样例输入

Unclear

Nuclear

样例输出

Y

出现次数最多的整数

时间限制：1.0s内存限制：512.OMB

问题描述

编写一个程序，读入一组整数，这组整数是按照从小到大的顺序排列的，它们的个数N也是由用户输

入的，最多不会超过20。然后程序将对这个数组进行统计，把出现次数最多的那个数组元素值打印出来。

如果有两个元素值出现的次数相同，即并列第一，那么只打印比较小的那个值。

输入格式：第一行是一个整数儿N£20；接下来有/V行，每一行表示一个整数，并且按照从小

到大的顺序排列。

输出格式：输出只有一行，即出现次数最多的那个元素值。

输入输出样例

样例输入

5

100

150

150

200

250

样例输出

150

字串统计

时间限制：1.0s内存限制:512.0MB

问题描述

给定一个长度为n的字符串S,还有一个数字L,统计长度大于等于L的出现次数最多的子串（不同的

出现可以相交），如果有多个，输出最长的，如果仍然有多个，输出第一次出现最早的。

输入格式

第一行一个数字L。

第二行是字符串So

L大于0,且不超过S的长度。

输出格式

一行，题目要求的字符串。

输入样例1：

4

bbaabbaaaaa

输出样例1:

bbaa

输入样例2：

2

bbaabbaaaaa

输出样例2：

aa

数据规模和约定

n〈=60

S中所有字符都是小写英文字母。

提示

枚举所有可能的子串，统计出现次数，找出符合条件的那个

矩阵乘法

时间限制：1.0s内存限制：512.0MB

问题描述

输入两个矩阵，分别是m*s,s*n大小。输出两个矩阵相乘的结果。

输入格式

第一行，空格隔开的三个正整数m,s,n(均不超过200)。

接下来m行，每行s个空格隔开的整数，表示矩阵A(i,j)。

接下来s行，每行n个空格隔开的整数，表示矩阵B(i,J)«

输出格式

m行，每行n个空格隔开的整数，输出相乘彳爰的矩阵C(i,j)的值。

样例输入

232

10-1

11-3

03

12

31

样例输出

-32

-82

提示

矩阵C应该是m行n歹IJ,其中C(i,j)等于矩阵A第i行行向量与矩阵B第j列列向量的内积。

例如样例中C(1,1)=(1,0,-1)*(0,1,3)=1*0+0*1+(-1)*3=-3

大小写转换

时间限制:1.0s内存限制:512.0MB

问题描述

编写一个程序，输入一个字符串（长度不超过20）,然后把这个字符串内的每一个字符进行大小写变

换，即将大写字母变成小写，小写字母变成大写，然后把这个新的字符串输出。

输入格式：输入一个字符串，而且这个字符串当中只包含英文字母，不包含其他类型的字符，也没有

空格。

输出格式：输出经过转换后的字符串。

输入输出样例

样例输入

AeDb

样例输出

aEdB

动态数组使用

时间限制:1.0s内存限制:512.0MB

从键盘读入n个整数，使用动态数组存储所读入的整数，并计算它们的和与平均值分别输

出。要求尽可能使用函数实现程序代码。平均值为小数的只保留其整数部分。

样例输入：

5

34002

样例输出：

91

样例输入：

7