蓝桥杯VIP练习题(DOC)(DOC 117页).doc

1、 1.基础练习 阶乘计算 时间限制：1.0s 内存限制：512.0MB问题描述输入一个正整数n，输出n!的值。其中n!=1*2*3*n。算法描述n!可能很大，而计算机能表示的整数范围有限，需要使用高精度计算的方法。使用一个数组A来表示一个大整数a，A0表示a的个位，A1表示a的十位，依次类推。将a乘以一个整数k变为将数组A的每一个元素都乘以k，请注意处理相应的进位。首先将a设为1，然后乘2，乘3，当乘到n时，即得到了n!的值。输入格式输入包含一个正整数n，n=1000。输出格式输出n!的准确值。样例输入10样例输出36288002.基础练习 高精度加法 时间限制：1.0s 内存限制：512.0

2、MB问题描述输入两个整数a和b，输出这两个整数的和。a和b都不超过100位。算法描述由于a和b都比较大，所以不能直接使用语言中的标准数据类型来存储。对于这种问题，一般使用数组来处理。定义一个数组A，A0用于存储a的个位，A1用于存储a的十位，依此类推。同样可以用一个数组B来存储b。计算c=a+b的时候，首先将A0与B0相加，如果有进位产生，则把进位（即和的十位数）存入r，把和的个位数存入C0，即C0等于(A0+B0)%10。然后计算A1与B1相加，这时还应将低位进上来的值r也加起来，即C1应该是A1、B1和r三个数的和如果又有进位产生，则仍可将新的进位存入到r中，和的个位存到C1中。依此类推，

3、即可求出C的所有位。最后将C输出即可。输入格式输入包括两行，第一行为一个非负整数a，第二行为一个非负整数b。两个整数都不超过100位，两数的最高位都不是0。输出格式输出一行，表示a+b的值。样例输入201001222010012212345678902010012220100122样例输出201001222030112334546680123.基础练习 Huffuman树 时间限制：1.0s 内存限制：512.0MB问题描述Huffman树在编码中有着广泛的应用。在这里，我们只关心Huffman树的构造过程。给出一列数pi=p0,p1, ,pn-1，用这列数构造Huffman树的过程如下：1.

4、 找到pi中最小的两个数，设为pa和pb，将pa和pb从pi中删除掉，然后将它们的和加入到pi中。这个过程的费用记为pa+pb。2. 重复步骤1，直到pi中只剩下一个数。在上面的操作过程中，把所有的费用相加，就得到了构造Huffman树的总费用。本题任务：对于给定的一个数列，现在请你求出用该数列构造Huffman树的总费用。例如，对于数列pi=5, 3, 8, 2, 9，Huffman树的构造过程如下：1. 找到5, 3, 8, 2, 9中最小的两个数，分别是2和3，从pi中删除它们并将和5加入，得到5, 8, 9, 5，费用为5。2. 找到5, 8, 9, 5中最小的两个数，分别是5和5，从

5、pi中删除它们并将和10加入，得到8, 9, 10，费用为10。3. 找到8, 9, 10中最小的两个数，分别是8和9，从pi中删除它们并将和17加入，得到10, 17，费用为17。4. 找到10, 17中最小的两个数，分别是10和17，从pi中删除它们并将和27加入，得到27，费用为27。5. 现在，数列中只剩下一个数27，构造过程结束，总费用为5+10+17+27=59。输入格式输入的第一行包含一个正整数n（n=100）。接下来是n个正整数，表示p0,p1, ,pn-1，每个数不超过1000。输出格式输出用这些数构造Huffman树的总费用。样例输入55 3 8 2 9样例输出594.基础

6、练习 2n皇后问题 时间限制：1.0s 内存限制：512.0MB问题描述给定一个n*n的棋盘，棋盘中有一些位置不能放皇后。现在要向棋盘中放入n个黑皇后和n个白皇后，使任意的两个黑皇后都不在同一行、同一列或同一条对角线上，任意的两个白皇后都不在同一行、同一列或同一条对角线上。问总共有多少种放法？n小于等于8。输入格式输入的第一行为一个整数n，表示棋盘的大小。接下来n行，每行n个0或1的整数，如果一个整数为1，表示对应的位置可以放皇后，如果一个整数为0，表示对应的位置不可以放皇后。输出格式输出一个整数，表示总共有多少种放法。样例输入41 1 1 11 1 1 11 1 1 11 1 1 1样例输出

7、2样例输入41 0 1 11 1 1 11 1 1 11 1 1 1样例输出05. 基础练习 报时助手 时间限制：1.0s 内存限制：512.0MB问题描述给定当前的时间，请用英文的读法将它读出来。时间用时h和分m表示，在英文的读法中，读一个时间的方法是：如果m为0，则将时读出来，然后加上“oclock”，如3:00读作“three oclock”。如果m不为0，则将时读出来，然后将分读出来，如5:30读作“five thirty”。时和分的读法使用的是英文数字的读法，其中020读作：0:zero, 1: one, 2:two, 3:three, 4:four, 5:five, 6:six,

8、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 sev

9、en”，0:15读作“zero fifteen”。输入格式输入包含两个非负整数h和m，表示时间的时和分。非零的数字前没有前导0。h小于24，m小于60。输出格式输出时间时刻的英文。样例输入0 15样例输出zero fifteen6.基础练习 回形取数 时间限制：1.0s 内存限制：512.0MB问题描述回形取数就是沿矩阵的边取数，若当前方向上无数可取或已经取过，则左转90度。一开始位于矩阵左上角，方向向下。输入格式输入第一行是两个不超过200的正整数m, n，表示矩阵的行和列。接下来m行每行n个整数，表示这个矩阵。输出格式输出只有一行，共mn个数，为输入矩阵回形取数得到的结果。数之间用一个空格

10、分隔，行末不要有多余的空格。样例输入3 31 2 34 5 67 8 9样例输出1 4 7 8 9 6 3 2 5样例输入3 21 23 45 6样例输出1 3 5 6 4 27.基础练习 龟兔赛跑预测 时间限制：1.0s 内存限制：512.0MB问题描述话说这个世界上有各种各样的兔子和乌龟，但是研究发现，所有的兔子和乌龟都有一个共同的特点喜欢赛跑。于是世界上各个角落都不断在发生着乌龟和兔子的比赛，小华对此很感兴趣，于是决定研究不同兔子和乌龟的赛跑。他发现，兔子虽然跑比乌龟快，但它们有众所周知的毛病骄傲且懒惰，于是在与乌龟的比赛中，一旦任一秒结束后兔子发现自己领先t米或以上，它们就会停下来休息

11、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=

12、10;l=10000且为v1,v2的公倍数)输出格式输出包含两行，第一行输出比赛结果一个大写字母“T”或“R”或“D”，分别表示乌龟获胜，兔子获胜，或者两者同时到达终点。第二行输出一个正整数，表示获胜者（或者双方同时）到达终点所耗费的时间（秒数）。样例输入10 5 5 2 20样例输出D4样例输入10 5 5 1 20样例输出R3样例输入10 5 5 3 20样例输出T48. 基础练习 芯片测试 时间限制：1.0s 内存限制：512.0MB问题描述有n（2n20）块芯片，有好有坏，已知好芯片比坏芯片多。每个芯片都能用来测试其他芯片。用好芯片测试其他芯片时，能正确给出被测试芯片是好还是坏。而用坏

13、芯片测试其他芯片时，会随机给出好或是坏的测试结果（即此结果与被测试芯片实际的好坏无关）。给出所有芯片的测试结果，问哪些芯片是好芯片。输入格式输入数据第一行为一个整数n，表示芯片个数。第二行到第n+1行为n*n的一张表，每行n个数据。表中的每个数据为0或1，在这n行中的第i行第j列（1i, jn）的数据表示用第i块芯片测试第j块芯片时得到的测试结果，1表示好，0表示坏，i=j时一律为1（并不表示该芯片对本身的测试结果。芯片不能对本身进行测试）。输出格式按从小到大的顺序输出所有好芯片的编号样例输入31 0 10 1 01 0 1样例输出1 39. 基础练习 FJ的字符串 时间限制：1.0s 内存限

14、制：512.0MB问题描述FJ在沙盘上写了这样一些字符串：A1 = “A”A2 = “ABA”A3 = “ABACABA”A4 = “ABACABADABACABA” 你能找出其中的规律并写所有的数列AN吗？输入格式仅有一个数：N 26。输出格式请输出相应的字符串AN，以一个换行符结束。输出中不得含有多余的空格或换行、回车符。样例输入3样例输出ABACABA10.基础练习 Sine之舞 时间限制：1.0s 内存限制：512.0MB问题描述最近FJ为他的奶牛们开设了数学分析课，FJ知道若要学好这门课，必须有一个好的三角函数基本功。所以他准备和奶牛们做一个“Sine之舞”的游戏，寓教于乐，提高奶牛

15、们的计算能力。不妨设An=sin(1sin(2+sin(3sin(4+.sin(n).)Sn=(.(A1+n)A2+n-1)A3+.+2)An+1FJ想让奶牛们计算Sn的值，请你帮助FJ打印出Sn的完整表达式，以方便奶牛们做题。输入格式仅有一个数：N201。输出格式请输出相应的表达式Sn，以一个换行符结束。输出中不得含有多余的空格或换行、回车符。样例输入3样例输出(sin(1)+3)sin(1sin(2)+2)sin(1sin(2+sin(3)+111.基础练习 数的读法 时间限制：1.0s 内存限制：512.0MB问题描述Tom教授正在给研究生讲授一门关于基因的课程，有一件事情让他颇为头疼：

16、一条染色体上有成千上万个碱基对，它们从0开始编号，到几百万，几千万，甚至上亿。比如说，在对学生讲解第1234567009号位置上的碱基时，光看着数字是很难准确的念出来的。所以，他迫切地需要一个系统，然后当他输入12 3456 7009时，会给出相应的念法：十二亿三千四百五十六万七千零九用汉语拼音表示为shi er yi san qian si bai wu shi liu wan qi qian ling jiu这样他只需要照着念就可以了。你的任务是帮他设计这样一个系统：给定一个阿拉伯数字串，你帮他按照中文读写的规范转为汉语拼音字串，相邻的两个音节用一个空格符格开。注意必须严格按照规范，比如说

17、“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 jiu12.基础练习 完美的代价 时间限制：1.0s 内存限制：512.0MB问题

18、描述回文串，是一种特殊的字符串，它从左往右读和从右往左读是一样的。小龙龙认为回文串才是完美的。现在给你一个串，它不一定是回文的，请你计算最少的交换次数使得该串变成一个完美的回文串。交换的定义是：交换两个相邻的字符例如mamad第一次交换 ad : mamda第二次交换 md : madma第三次交换 ma : madam (回文！完美！)输入格式第一行是一个整数N，表示接下来的字符串的长度(N = 8000)第二行是一个字符串，长度为N.只包含小写字母输出格式如果可能，输出最少的交换次数。否则输出Impossible样例输入5mamad样例输出313.基础练习 矩形面积交 时间限制：1.0s

19、内存限制：512.0MB问题描述平面上有两个矩形，它们的边平行于直角坐标系的X轴或Y轴。对于每个矩形，我们给出它的一对相对顶点的坐标，请你编程算出两个矩形的交的面积。输入格式输入仅包含两行，每行描述一个矩形。在每行中，给出矩形的一对相对顶点的坐标，每个点的坐标都用两个绝对值不超过107的实数表示。输出格式输出仅包含一个实数，为交的面积，保留到小数后两位。样例输入1 1 3 32 2 4 4样例输出1.0014.基础练习 矩阵乘法 时间限制：1.0s 内存限制：512.0MB问题描述给定一个N阶矩阵A，输出A的M次幂（M是非负整数）例如：A =1 23 4A的2次幂7 1015 22输入格式第一

20、行是一个正整数N、M（1=N=30, 0=M=5），表示矩阵A的阶数和要求的幂数接下来N行，每行N个绝对值不超过10的非负整数，描述矩阵A的值输出格式输出共N行，每行N个整数，表示A的M次幂所对应的矩阵。相邻的数之间用一个空格隔开样例输入2 21 23 4样例输出7 1015 2215.基础练习 字符串对比 时间限制：1.0s 内存限制：512.0MB问题描述给定两个仅由大写字母或小写字母组成的字符串(长度介于1到10之间)，它们之间的关系是以下4中情况之一：1：两个字符串长度不等。比如 Beijing 和 Hebei2：两个字符串不仅长度相等，而且相应位置上的字符完全一致(区分大小写)，比如

21、 Beijing 和 Beijing3：两个字符串长度相等，相应位置上的字符仅在不区分大小写的前提下才能达到完全一致（也就是说，它并不满足情况2）。比如 beijing 和 BEIjing4：两个字符串长度相等，但是即使是不区分大小写也不能使这两个字符串一致。比如 Beijing 和 Nanjing编程判断输入的两个字符串之间的关系属于这四类中的哪一类，给出所属的类的编号。输入格式包括两行，每行都是一个字符串输出格式仅有一个数字，表明这两个字符串的关系编号样例输入BEIjingbeiJing 样例输出316. 基础练习 分解质因数 时间限制：1.0s 内存限制：512.0MB问题描述求出区间a

22、,b中所有整数的质因数分解。输入格式输入两个整数a，b。输出格式每行输出一个数的分解，形如k=a1*a2*a3.(a1=a2=a3.，k也是从小到大的)(具体可看样例)样例输入3 10样例输出3=34=2*25=56=2*37=78=2*2*29=3*310=2*5提示先筛出所有素数，然后再分解。数据规模和约定2=a=b=1000017.基础练习 时间转换 时间限制：1.0s 内存限制：512.0MB问题描述给定一个以秒为单位的时间t，要求用“:”的格式来表示这个时间。表示时间，表示分钟，而表示秒，它们都是整数且没有前导的“0”。例如，若t=0，则应输出是“0:0:0”；若t=3661，则输出

23、“1:1:1”。输入格式输入只有一行，是一个整数t（0=t=86399）。输出格式输出只有一行，是以“:”的格式所表示的时间，不包括引号。样例输入0样例输出0:0:0样例输入5436样例输出1:30:3618.算法训练 A+B problem 时间限制：1.0s 内存限制：1.0GB问题描述Given two integersAandB, your task is to output their sum,A+B.输入格式The input contains of only one line, consisting of two integersAandB. (0 A,B 1 000)输出格式T

24、he output should contain only one number that isA+B.样例输入1 1样例输出219. 算法训练 猴子分苹果 时间限制：1.0s 内存限制：256.0MB问题描述秋天到了，n只猴子采摘了一大堆苹果放到山洞里，约定第二天平分。这些猴子很崇拜猴王孙悟空，所以都想给他留一些苹果。第一只猴子悄悄来到山洞，把苹果平均分成n份，把剩下的m个苹果吃了,然后藏起来一份，最后把剩下的苹果重新合在一起。这些猴子依次悄悄来到山洞，都做同样的操作，恰好每次都剩下了m个苹果。第二天，这些猴子来到山洞，把剩下的苹果分成n分，巧了，还是剩下了m个。问，原来这些猴子至少采了多少

25、个苹果。输入格式两个整数，n m输出格式一个整数，表示原来苹果的数目样例输入5 1样例输出15621数据规模和约定0mn920.算法训练 学做菜 时间限制：1.0s 内存限制：256.0MB问题描述涛涛立志要做新好青年，他最近在学做菜。由于技术还很生疏，他只会用鸡蛋，西红柿，鸡丁，辣酱这四种原料来做菜，我们给这四种原料标上字母A,B,C,D。涛涛现在会做的菜有五种：1、 西红柿炒鸡蛋 原料：AABDD2、 酸辣鸡丁 原料：ABCD3、 宫保鸡丁 原料：CCD4、 水煮西红柿 原料：BBB5、 怪味蛋 原料：AD这天早上，开开去早市给涛涛买了一些原料回来。由于事先没有什么计划，涛涛决定，对于现存

26、的原料，每次尽量做菜单上靠前（即编号小）的菜。现在请你写一个程序，判断一下开开和涛涛中午能吃到哪些菜。输入格式共4个整数a,b,c,d。分别表示开开买的A,B,C,D这4种原料的数量。每种原料不会超过30份。输出格式输出5行。其中第i行表示涛涛做的第i种菜的数目。样例输入3124样例输出1010121.算法训练 寂寞的数 时间限制：1.0s 内存限制：256.0MB问题描述道德经曰：一生二，二生三，三生万物。对于任意正整数n，我们定义d(n)的值为为n加上组成n的各个数字的和。例如，d(23)=23+2+3=28, d(1481)=1481+1+4+8+1=1495。因此，给定了任意一个n作为

27、起点，你可以构造如下一个递增序列：n,d(n),d(d(n),d(d(d(n).例如，从33开始的递增序列为：33, 39, 51, 57, 69, 84, 96, 111, 114, 120, 123, 129, 141, .我们把n叫做d(n)的生成元，在上面的数列中，33是39的生成元，39是51的生成元，等等。有一些数字甚至可以有两个生成元，比如101，可以由91和100生成。但也有一些数字没有任何生成元，如42。我们把这样的数字称为寂寞的数字。输入格式一行，一个正整数n。输出格式按照升序输出小于n的所有寂寞的数字，每行一个。样例输入40样例输出135792031数据规模和约定n=10

28、00022.算法训练 连续正整数的和 时间限制：1.0s 内存限制：256.0MB问题描述78这个数可以表示为连续正整数的和，1+2+3，18+19+20+21，25+26+27。输入一个正整数 n(=10000)输出 m 行(n有m种表示法)，每行是两个正整数a，b，表示a+(a+1)+.+b=n。对于多种表示法，a小的方案先输出。样例输入78样例输出1 1218 2125 2723.算法训练 友好数 时间限制：1.0s 内存限制：256.0MB问题描述有两个整数，如果每个整数的约数和（除了它本身以外）等于对方，我们就称这对数是友好的。例如：9的约数和有：1+3=44的约数和有：1+2=3所

29、以9和4不是友好的。220的约数和有：1 2 4 5 10 11 20 22 44 55 110=284284的约数和有：1 2 4 71 142=220所以220和284是友好的。编写程序，判断两个数是否是友好数。输入格式一行，两个整数，由空格分隔输出格式如果是友好数，输出yes，否则输出no，注意不包含引号。样例输入220 284样例输出yes数据规模和约定两个整数都小于1000024. 算法训练 和为T 时间限制：1.0s 内存限制：256.0MB问题描述从一个大小为n的整数集中选取一些元素，使得它们的和等于给定的值T。每个元素限选一次，不能一个都不选。输入格式第一行一个正整数n，表示整

30、数集内元素的个数。第二行n个整数，用空格隔开。第三行一个整数T，表示要达到的和。输出格式输出有若干行，每行输出一组解，即所选取的数字，按照输入中的顺序排列。若有多组解，优先输出不包含第n个整数的；若都包含或都不包含，优先输出不包含第n-1个整数的，依次类推。最后一行输出总方案数。样例输入5-7 -3 -2 5 90样例输出-3 -2 5-7 -2 92数据规模和约定1=n=22T=maxlongint集合中任意元素的和都不超过long的范围25.算法训练 黑白无常 时间限制：1.0s 内存限制：256.0MB问题描述某寝室的同学们在学术完之后准备玩一个游戏：游戏是这样的，每个人头上都被贴了一张

31、白色或者黑色的纸，现在每个人都会说一句话“我看到x张白色纸条和y张黑色的纸条”，又已知每个头上贴着白色纸的人说的是真话、每个头上贴着黑色纸的人说的是谎话，现在要求你判断哪些人头上贴着的是白色的纸条，如果无解输出“NoSolution.”；如果有多组解，则把每个答案中贴白条的人的编号按照大小排列后组成一个数（比如第一个人和第三个人头上贴着的是白纸条，那么这个数就是13；如果第6、7、8个人都贴的是白纸条，那么这个数就是678）输出最小的那个数（如果全部都是黑纸条也满足情况的话，那么输出0）输入格式第一行为一个整数n，接下来n行中的第i行有两个整数x和y，分别表示第i个人说“我看到x张白色纸条和y

32、张黑色的纸条”。输出格式一行。如果无解输出“NoSolution.”。否则输出答案中数值（具体见问题描述）最小的那个，如果全部都是黑纸条也满足情况的话，那么输出0样例输入21 01 0样例输出0样例输入53 10 41 34 01 3样例输出35数据规模和约定n=826.算法训练 数的统计 时间限制：1.0s 内存限制：256.0MB问题描述在一个有限的正整数序列中，有些数会多次重复出现在这个序列中。如序列：3，1，2，1，5，1，2。其中1就出现3次，2出现2次，3出现1 次，5出现1次。你的任务是对于给定的正整数序列，从小到大依次输出序列中出现的数及出现的次数。输入格式第一行正整数n，表示

33、给定序列中正整数的个数。第二行是n 个用空格隔开的正整数x，代表给定的序列。输出格式若干行，每行两个用一个空格隔开的数，第一个是数列中出现的数，第二个是该数在序列中出现的次数。样例输入128 2 8 2 2 11 1 1 8 1 13 13样例输出1 32 38 311 113 2数据规模和约定数据：n=1000；0x=1000,000。27.算法训练 暗恋 时间限制：1.0s 内存限制：256.0MB问题描述同在一个高中，他却不敢去找她，虽然在别人看来，那是再简单不过的事。暗恋，是他唯一能做的事。他只能在每天课间操的时候，望望她的位置，看看她倾心的动作，就够了。操场上的彩砖啊，你们的位置，就

34、是他们能够站立的地方，他俩的关系就像砖与砖之间一样固定，无法动摇。还记得当初铺砖的工人，将整个操场按正方形铺砖（整个操场可视为R行C列的矩阵，矩阵的每个元素为一块正方形砖块），正方形砖块有两种，一种为蓝色，另一种为红色。我们定义他和她之间的“爱情指标”为最大纯色正方形的面积，请你写一个程序求出“爱情指标”。输入格式第一行两个正整数R和C。接下来R行C列描述整个操场，红色砖块用1来表示，蓝色砖块用0来表示。输出格式一个数，表示他和她之间的“爱情指标”。样例输入5 80 0 0 1 1 1 0 11 1 0 1 1 1 1 10 1 1 1 1 1 0 11 0 1 1 1 1 1 01 1 1

35、0 1 1 0 1样例输出9数据规模和约定40%的数据R,C=10;70%的数据R,C=50;100%的数据R,C=200;28.算法训练 明明的随机数 时间限制：1.0s 内存限制：256.0MB问题描述明明想在学校中请一些同学一起做一项问卷调查，为了实验的客观性，他先用计算机生成了N个1到1000之间的随机整数（N100），对于其中重复的数字，只保留一个，把其余相同的数去掉，不同的数对应着不同的学生的学号。然后再把这些数从小到大排序，按照排好的顺序去找同学做调查。请你协助明明完成“去重”与“排序”的工作。输入格式输入有2行，第1行为1个正整数，表示所生成的随机数的个数：N第2行有N个用空格

36、隔开的正整数，为所产生的随机数。输出格式输出也是2行，第1行为1个正整数M，表示不相同的随机数的个数。第2行为M个用空格隔开的正整数，为从小到大排好序的不相同的随机数。样例输入1020 40 32 67 40 20 89 300 400 15样例输出815 20 32 40 67 89 300 400题目来源计13李震摘编自NOIP06PJ0129.算法训练 字符串的展开 时间限制：1.0s 内存限制：256.0MB在初赛普及组的“阅读程序写结果”的问题中，我们曾给出一个字符串展开的例子：如果在输入的字符串中，含有类似于“d-h”或者“4-8”的字串，我们就把它当作一种简写，输出时，用连续递增

37、的字母获数字串替代其中的减号，即，将上面两个子串分别输出为“defgh”和“45678”。在本题中，我们通过增加一些参数的设置，使字符串的展开更为灵活。具体约定如下：(1) 遇到下面的情况需要做字符串的展开：在输入的字符串中，出现了减号“-”，减号两侧同为小写字母或同为数字，且按照ASCII码的顺序，减号右边的字符严格大于左边的字符。(2) 参数p1：展开方式。p1=1时，对于字母子串，填充小写字母；p1=2时，对于字母子串，填充大写字母。这两种情况下数字子串的填充方式相同。p1=3时，不论是字母子串还是数字字串，都用与要填充的字母个数相同的星号“*”来填充。(3) 参数p2：填充字符的重复个

38、数。p2=k表示同一个字符要连续填充k个。例如，当p2=3时，子串“d-h”应扩展为“deeefffgggh”。减号两边的字符不变。(4) 参数p3：是否改为逆序：p3=1表示维持原来顺序，p3=2表示采用逆序输出，注意这时候仍然不包括减号两端的字符。例如当p1=1、p2=2、p3=2时，子串“d-h”应扩展为“dggffeeh”。(5) 如果减号右边的字符恰好是左边字符的后继，只删除中间的减号，例如：“d-e”应输出为“de”，“3-4”应输出为“34”。如果减号右边的字符按照ASCII码的顺序小于或等于左边字符，输出时，要保留中间的减号，例如：“d-d”应输出为“d-d”，“3-1”应输出

39、为“3-1”。输入格式输入包括两行：第1行为用空格隔开的3个正整数，一次表示参数p1，p2，p3。第2行为一行字符串，仅由数字、小写字母和减号“-”组成。行首和行末均无空格。输出格式输出只有一行，为展开后的字符串。输入输出样例1输入输出1 2 1abcs-w1234-9s-4zzabcsttuuvvw1234556677889s-4zz输入输出样例2输入输出2 3 2a-d-daCCCBBBd-d输入输出样例3输入输出3 4 2di-jkstra2-6dijkstra2*6数据规模和约定40%的数据满足：字符串长度不超过5100%的数据满足：1=p1=3，1=p2=8，1=p3=2。字符串长度

40、不超过10030.算法训练 貌似化学 时间限制：1.0s 内存限制：256.0MB问题描述现在有a,b,c三种原料，如果他们按x:y:z混合，就能产生一种神奇的物品d。当然不一定只产生一份d，但a,b,c的最简比一定是x:y:z现在给你3种可供选择的物品:每个物品都是由a,b,c以一定比例组合成的，求出最少的物品数，使得他们能凑出整数个d物品（这里的最少是指三者个数的总和最少）输入格式第一行三个整数，表示d的配比（x,y,z）接下来三行，表示三种物品的配比，每行三个整数（=10000）。输出格式四个整数，分别表示在最少物品总数的前提下a,b,c,d的个数（d是由a,b,c配得的）目标答案=10

41、000如果不存在满足条件的方案，输出NONE样例输入3 4 51 2 33 7 12 1 2样例输出8 1 5 7 31.算法训练 最大体积 时间限制：1.0s 内存限制：256.0MB问题描述每个物品有一定的体积（废话），不同的物品组合，装入背包会战用一定的总体积。假如每个物品有无限件可用，那么有些体积是永远也装不出来的。为了尽量装满背包，附中的OIER想要研究一下物品不能装出的最大体积。题目保证有解，如果是有限解，保证不超过2，000，000，000如果是无限解，则输出0输入格式第一行一个整数n（n=10），表示物品的件数第2行到N+1行: 每件物品的体积(1= =500)输出格式一个整数ans，表示不能用这些物品得到的最大体积。样例输入33610样例输出1732. 算法训练 9-7链表数据求和操作 时间限制：1.0s 内存限制：512.0MB读入10个复数，建立对应链表，然后求所有复数的和。样例输入1 21 34 52 33 12 14 22 23 31 1样例输出23+23i33.算法训练 6-3判定字符位置 时间限制：1.0s 内存限制：512.0MB返回给定字符串s中元音字母的首次出现位置。英语元音字母只有a、e、i、o、u五个。若字符串中没有元音字母，则返回0。只考虑小写的情况。样例输入and样例输出1