难度为三的挑战题南洋理工.docx

难度为三的挑战题南洋理工.docx

《难度为三的挑战题南洋理工.docx》由会员分享，可在线阅读，更多相关《难度为三的挑战题南洋理工.docx（25页珍藏版）》请在冰点文库上搜索。

难度为三的挑战题南洋理工

括号配对问题

描述

现在，有一行括号序列，请你检查这行括号是否配对。

输入

第一行输入一个数N（0

后面的N行输入多组输入数据，每组输入数据都是一个字符串S（S的长度小于10000，且S不是空串），测试数据组数少于5组。

数据保证S中只含有"[","]","（","）"四种字符

输出

每组输入数据的输出占一行，如果该字符串中所含的括号是配对的，则输出Yes,如果不配对则输出No

样例输入

3

[（]）

（]）

（[[]（）]）

样例输出

No

No

Yes

BinaryStringMatching

描述

GiventwostringsAandB,whosealphabetconsistonly‘0’and‘1’.YourtaskisonlytotellhowmanytimesdoesAappearasasubstringofB?

Forexample,thetextstringBis‘1001110110’whilethepatternstringAis‘11’,youshouldoutput3,becausethepatternAappearedattheposit

输入

ThefirstlineconsistonlyoneintegerN,indicatesNcasesfollows.Ineachcase,therearetwolines,thefirstlinegivesthestringA,length（A）<=10,andthesecondlinegivesthestringB,length（B）<=1000.AnditisguaranteedthatBisalwayslongerthanA.

输出

Foreachcase,outputasinglelineconsistasingleinteger,tellshowmanytimesdoBappearsasasubstringofA.

样例输入

3

11

1001110110

101

110010010010001

1010

110100*********

样例输出

3

0

3

喷水装置

（一）

描述

现有一块草坪，长为20米，宽为2米，要在横中心线上放置半径为Ri的喷水装置，每个喷水装置的效果都会让以它为中心的半径为实数Ri（0

选择尽量少的喷水装置，把整个草坪的全部湿润。

输入

第一行m表示有m组测试数据

每一组测试数据的第一行有一个整数数n，n表示共有n个喷水装置，随后的一行，有n个实数ri，ri表示该喷水装置能覆盖的圆的半径。

输出

输出所用装置的个数

样例输入

2

5

23.244.56

10

123121.231.112

样例输出

2

5

一种排序

描述

现在有很多长方形，每一个长方形都有一个编号，这个编号可以重复；还知道这个长方形的宽和长，编号、长、宽都是整数；现在要求按照一下方式排序（默认排序规则都是从小到大）；

1.按照编号从小到大排序

2.对于编号相等的长方形，按照长方形的长排序；

3.如果编号和长都相同，按照长方形的宽排序；

4.如果编号、长、宽都相同，就只保留一个长方形用于排序,删除多余的长方形；最后排好序按照指定格式显示所有的长方形；

输入

第一行有一个整数0

每一组第一行有一个整数0

说明这是一个正方形（数据约定长宽与编号都小于10000）；

输出

顺序输出每组数据的所有符合条件的长方形的编号长宽

样例输入

1

8

111

111

112

121

122

211

212

221

样例输出

111

121

122

211

221

吝啬的国度

描述

在一个吝啬的国度里有N个城市，这N个城市间只有N-1条路把这个N个城市连接起来。

现在，Tom在第S号城市，他有张该国地图，他想知道如果自己要去参观第T号城市，必须经过的前一个城市是几号城市（假设你不走重复的路）。

输入

第一行输入一个整数M表示测试数据共有M（1<=M<=5）组

每组测试数据的第一行输入一个正整数N（1<=N<=100000）和一个正整数S（1<=S<=100000），N表示城市的总个数，S表示参观者所在城市的编号

随后的N-1行，每行有两个正整数a,b（1<=a,b<=N），表示第a号城市和第b号城市之间有一条路连通。

输出

每组测试数据输N个正整数，其中，第i个数表示从S走到i号城市，必须要经过的上一个城市的编号。

（其中i=S时，请输出-1）

样例输入

1

101

19

18

810

103

86

12

104

95

37

样例输出

-111010983118

孪生素数问题

时间限制：

3000ms|内存限制：

65535KB

难度：

3

描述

写一个程序，找出给出素数范围内的所有孪生素数的组数。

一般来说，孪生素数就是指两个素数距离为2，近的不能再近的相邻素数。

有些童鞋一看到题就开始写程序，不仔细看题，咱们为了遏制一下读题不认真仔细的童鞋，规定，两个素数相邻为1的也成为孪生素数。

输入

第一行给出N（0

接下来组测试数据给出m，表示找出m之前的所有孪生素数。

（0

输出

每组测试数据输出占一行，该行为m范围内所有孪生素数组数。

样例输入

1

14

样例输出

4

大数阶乘

时间限制：

3000ms|内存限制：

65535KB

描述

我们都知道如何计算一个数的阶乘，可是，如果这个数很大呢，我们该如何去计算它并输出它？

输入

输入一个整数m（0

输出

输出m的阶乘，并在输出结束之后输入一个换行符

样例输入

50

样例输出

30414093201713378043612608166064768844377641568960512000000000000

组合数

时间限制：

3000ms|内存限制：

65535KB

难度：

3

描述

找出从自然数1、2、...、n（0

输入

输入n、r。

输出

按特定顺序输出所有组合。

特定顺序：

每一个组合中的值从大到小排列，组合之间按逆字典序排列。

样例输入

53

样例输出

543

542

541

532

531

521

432

431

421

321

最长公共子序列

描述

咱们就不拐弯抹角了，如题，需要你做的就是写一个程序，得出最长公共子序列。

tip：

最长公共子序列也称作最长公共子串（不要求连续），英文缩写为LCS（LongestCommonSubsequence）。

其定义是，一个序列S，如果分别是两个或多个已知序列的子序列，且是所有符合此条件序列中最长的，则S称为已知序列的最长公共子序列。

输入

第一行给出一个整数N（0

接下来每组数据两行，分别为待测的两组字符串。

每个字符串长度不大于1000.

输出

每组测试数据输出一个整数，表示最长公共子序列长度。

每组结果占一行。

样例输入

2

asdf

adfsd

123abc

abc123abc

棋盘覆盖

时间限制：

3000ms|内存限制：

65535KB

难度：

3

描述

在一个2k×2k（1<=k<=100）的棋盘中恰有一方格被覆盖，如图1（k=2时），现用一缺角的2×2方格（图2为其中缺右下角的一个），去覆盖2k×2k未被覆盖过的方格，求需要类似图2方格总的个数s。

如k=1时，s=1;k=2时，s=5

图1

图2

输入

第一行m表示有m组测试数据；

每一组测试数据的第一行有一个整数数k;

输出

输出所需个数s;

样例输入

3

1

2

3

样例输出

1

5

21

最少乘法次数

描述

给你一个非零整数，让你求这个数的n次方，每次相乘的结果可以在后面使用，求至少需要多少次乘。

如24：

2*2=22（第一次乘），22*22=24（第二次乘），所以最少共2次；

输入

第一行m表示有m（1<=m<=100）组测试数据；

每一组测试数据有一整数n（0

输出

输出每组测试数据所需次数s;

样例输入

3

2

3

4

样例输出

1

2

2

无聊的小明

描述

这天小明十分无聊，没有事做，但不甘于无聊的小明聪明的想到一个解决无聊的办法，因为他突然对数的正整数次幂产生了兴趣。

　　众所周知，2的正整数次幂最后一位数总是不断的在重复2，4，8，6，2，4，8，6……我们说2的正整数次幂最后一位的循环长度是4（实际上4的倍数都可以说是循环长度，但我们只考虑最小的循环长度）。

类似的，其余的数字的正整数次幂最后一位数也有类似的循环现象。

　　这时小明的问题就出来了：

是不是只有最后一位才有这样的循环呢？

对于一个整数n的正整数次幂来说，它的后k位是否会发生循环？

如果循环的话，循环长度是多少呢？

注意：

　　1.如果n的某个正整数次幂的位数不足k，那么不足的高位看做是0。

　　2.如果循环长度是L，那么说明对于任意的正整数a，n的a次幂和a+L次幂的最后k位都相同。

输入

第一行输入一个整数N（0

输出

每组测试数据输出包括一行，这一行只包含一个整数，表示循环长度。

如果循环不存在，输出-1。

样例输入

1

322

样例输出

4

懒省事的小明描述

小明很想吃果子，正好果园果子熟了。

在果园里，小明已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。

小明决定把所有的果子合成一堆。

因为小明比较懒，为了省力气，小明开始想点子了:

　　每一次合并，小明可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。

可以看出，所有的果子经过n-1次合并之后，就只剩下一堆了。

小明在合并果子时总共消耗的体力等于每次合并所耗体力之和。

　　因为还要花大力气把这些果子搬回家，所以小明在合并果子时要尽可能地节省体力。

假定每个果子重量都为1，并且已知果子的种类数和每种果子的数目，你的任务是设计出合并的次序方案，使小明耗费的体力最少，并输出这个最小的体力耗费值。

　　例如有3种果子，数目依次为1，2，9。

可以先将1、2堆合并，新堆数目为3，耗费体力为3。

接着，将新堆与原先的第三堆合并，又得到新的堆，数目为12，耗费体力为12。

所以小明总共耗费体力=3+12=15。

可以证明15为最小的体力耗费值。

输入

第一行输入整数N（0

接下来每组测试数据输入包括两行，第一行是一个整数n（1<＝n<=12000），表示果子的种类数。

第二行包含n个整数，用空格分隔，第i个整数ai（1<＝ai<=20000）是第i种果子的数目。

输出

每组测试数据输出包括一行，这一行只包含一个整数，也就是最小的体力耗费值。

样例输入

1

3

129

样例输出

15

小猴子下落

描述

有一颗二叉树，最大深度为D,且所有叶子的深度都相同。

所有结点从左到右从上到下的编号为1,2,3，·····，2的D次方减1。

在结点1处放一个小猴子，它会往下跑。

每个内结点上都有一个开关，初始全部关闭，当每次有小猴子跑到一个开关上时，它的状态都会改变，当到达一个内结点时，如果开关关闭，小猴子往左走，否则往右走，直到走到叶子结点。

一些小猴子从结点1处开始往下跑，最后一个小猴儿会跑到哪里呢？

输入

输入二叉树叶子的深度D,和小猴子数目I，假设I不超过整棵树的叶子个数，D<=20.最终以00结尾

输出

输出第I个小猴子所在的叶子编号。

样例输入

42

34

00

样例输出

12

7

三点顺序

描述：

现在给你不共线的三个点A,B,C的坐标，它们一定能组成一个三角形，现在让你判断A，B，C是顺时针给出的还是逆时针给出的？

如：

图1：

顺时针给出

图2：

逆时针给出

输入

每行是一组测试数据，有6个整数x1,y1,x2,y2,x3,y3分别表示A,B,C三个点的横纵坐标。

（坐标值都在0到10000之间）

输入000000表示输入结束

测试数据不超过10000组

输出

如果这三个点是顺时针给出的，请输出1，逆时针给出则输出0

样例输入

001113

011000

000000

样例输出

0

1

阶乘因式分解

（二）

描述

给定两个数n，m,其中m是一个数。

将n（0<=n<=2^31）的阶乘分解质因数，求其中有多少个m。

注：

^为求幂符号。

输入

第一行是一个整数s（0

随后的s行,每行有两个整数n，m。

输出

输出m的个数

样例输入

3

1005

162

100000000013

样例输出

24

15

83333329

超级台阶

时间限制：

1000ms|内存限制：

65535KB

难度：

3

描述

有一楼梯共m级，刚开始时你在第一级，若每次只能跨上一级或二级，要走上第m级，共有多少走法？

注：

规定从一级到一级有0种走法。

输入

输入数据首先包含一个整数n（1<=n<=100），表示测试实例的个数，然后是n行数据，每行包含一个整数m，（1<=m<=40）,表示楼梯的级数。

输出

对于每个测试实例，请输出不同走法的数量。

样例输入

2

2

3

样例输出

1

2

拦截导弹

描述

某国为了防御敌国的导弹袭击，发展中一种导弹拦截系统。

但是这种导弹拦截系统有一个缺陷：

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

某天，雷达捕捉到敌国导弹来袭。

由于该系统还在试用阶段，所以只用一套系统，因此有可能不能拦截所有的导弹。

输入

第一行输入测试数据组数N（1<=N<=10）

接下来一行输入这组测试数据共有多少个导弹m（1<=m<=20）

接下来行输入导弹依次飞来的高度，所有高度值均是大于0的正整数。

输出

输出最多能拦截的导弹数目

样例输入

2

8

38920715530029917015865

3

883465

样例输出

6

2

阶乘的0

描述

计算n!

的十进制表示最后有多少个0

输入

第一行输入一个整数N表示测试数据的组数（1<=N<=100）

每组测试数据占一行，都只有一个整数M（0<=M<=10000000）

输出

输出M的阶乘的十进制表示中最后0的个数

比如5!

=120则最后的0的个数为1

样例输入

6

3

60

100

1024

23456

8735373

样例输出

0

14

24

253

5861

2183837

找球号

（一）

描述

在某一国度里流行着一种游戏。

游戏规则为：

在一堆球中，每个球上都有一个整数编号i（0<=i<=100000000）,编号可重复，现在说一个随机整数k（0<=k<=100000100），判断编号为k的球是否在这堆球中（存在为"YES",否则为"NO"），先答出者为胜。

现在有一个人想玩玩这个游戏，但他又很懒。

他希望你能帮助他取得胜利。

输入

第一行有两个整数m，n（0<=n<=100000，0<=m<=1000000）；m表示这堆球里有m个球，n表示这个游戏进行n次。

接下来输入m+n个整数，前m个分别表示这m个球的编号i，后n个分别表示每次游戏中的随机整数k

输出

输出"YES"或"NO"

样例输入

64

233446768343343

2423343

样例输出

NO

NO

YES

YES

整数划分

描述

将正整数n表示成一系列正整数之和：

n=n1+n2+…+nk，

其中n1≥n2≥…≥nk≥1，k≥1。

正整数n的这种表示称为正整数n的划分。

求正整数n的不

同划分个数。

例如正整数6有如下11种不同的划分：

6；

5+1；

4+2，4+1+1；

3+3，3+2+1，3+1+1+1；

2+2+2，2+2+1+1，2+1+1+1+1；

1+1+1+1+1+1。

输入

第一行是测试数据的数目M（1<=M<=10）。

以下每行均包含一个整数n（1<=n<=10）。

输出

输出每组测试数据有多少种分法。

样例输入

1

6

样例输出

11

阶乘之和

描述

给你一个非负数整数n，判断n是不是一些数（这些数不允许重复使用，且为正数）的阶乘之和，如9=1！

+2!

+3!

，如果是，则输出Yes，否则输出No；

输入

第一行有一个整数0

每组测试数据有一个正整数n<1000000;

输出

如果符合条件，输出Yes，否则输出No;

样例输入

2

9

10

样例输出

Yes

No

众数问题

描述

所谓众数，就是对于给定的含有N个元素的多重集合，每个元素在S中出现次数最多的成为该元素的重数，

多重集合S重的重数最大的元素成为众数。

例如：

S={1,2,2,2,3,5}，则多重集S的众数是2，其重数为3。

现在你的任务是：

对于给定的由m个自然数组成的多重集S，计算出S的众数及其重数。

输入

第一行为n，表示测试数据组数。

（n<30）

每组测试的第一行是一个整数m，表示多重集S中元素的个数为m

接下来的一行中给出m（m<100）个不大于10万的自然数

（不会出现不同元素出现的次数相同的情况，如：

S={11,11,22,22,33,33}）。

输出

每组测试数据输出一行，包含两个数，第一个是众数，第二个是其重数，中间以空格隔开。

样例输入

1

6

122235

样例输出

23

次方求模

时间限制：

1000ms|内存限制：

65535KB

难度：

3

描述

求a的b次方对c取余的值

输入

第一行输入一个整数n表示测试数据的组数（n<100）

每组测试只有一行，其中有三个正整数a,b,c（1=

输出

输出a的b次方对c取余之后的结果

样例输入

3

235

310010

111234512345

样例输出

3

1

10481

A+BProblemII

描述

Ihaveaverysimpleproblemforyou.GiventwointegersAandB,yourjobistocalculatetheSumofA+B.

A,Bmustbepositive.

输入

ThefirstlineoftheinputcontainsanintegerT（1<=T<=20）whichmeansthenumberoftestcases.ThenTlinesfollow,eachlineconsistsoftwopositiveintegers,AandB.Noticethattheintegersareverylarge,thatmeansyoushouldnotprocessthembyusing32-bitinteger.Youmayassumethelengthofeachintegerwillnotexceed1000.

输出

Foreachtestcase,youshouldoutputtwolines.Thefirstlineis"Case#:

",#meansthenumberofthetestcase.Thesecondlineistheanequation"A+B=Sum",SummeanstheresultofA+B.Notetherearesomespacesinttheequation.

样例输入

2

12

112233445566778899998877665544332211

样例输出

Case1:

1+2=3

Case2:

112233445566778899+998877665544332211=111111*********1110

九的余数

描述

现在给你一个自然数n，它的位数小于等于一百万，现在你要做的就是求出这个数整除九之后的余数。

输入

第一行有一个整数m（1<=m<=8）,表示有m组测试数据；

随后m行每行有一个自然数n。

输出

输出n整除九之后的余数，每次输出占一行。

样例输入

3

4

5

465456541

样例输出

4

5

4

背包问题

描述

现在有很多物品（它们是可以分割的），我们知道它们每个物品的单位重量的价值v和重量w（1<=v,w<=10）；如果给你一个背包它能容纳的重量为m（10<=m<=20）,你所要做的就是把物品装到背包里，使背包里的物品的价值总和最大。

输入

第一行输入一个正整数n（1<=n<=5）,表示有n组测试数据；

随后有n测试数据，每组测试数据的第一行有两个正整数s，m（1<=s<=10）;s表示有s个物品。

接下来的s行每行有两个正整数v，w。

输出

输出每组测试数据中背包内的物品的价值和，每次输出占一行。

样例输入

1

315

510

28

39

样例输出

65

士兵杀敌

（一）

描述

南将军手下有N个士兵，分别编号1到N，这些士兵的杀敌数都是已知的。

小工是南将军手下的军师，南将军现在想知道第m号到第n号士兵的总杀敌数，请你帮助小工来回答南将军吧。

注意，南将军可能会问很多次问题。

输入

只有一组测试数据

第一行是两个整数N,M，其中N表示士兵的个数（1

随后的一行是N个整数，ai表示第i号士兵杀敌数目。

（0<=ai<=100）

随后的M行每行有两个整数m,n，表示南将军想知道第m号到第n号士兵的总杀敌数（1<=m,n<=N）。

输出

对于每一个询问，输出总杀敌数

每个输出占一行

样例输入

52

12345

13

24