蓝桥杯题库中的算法训练试题

1、登录后才能查看试题。1. 算法训练 P1103  时间限制：1.0s   内存限制：256.0MB锦囊1锦囊2锦囊3编程实现两个复数的运算。设有两个复数 和 ，则他们的运算公式为：要求：（1）定义一个结构体类型来描述复数。（2）复数之间的加法、减法、乘法和除法分别用不用的函数来实现。（3）必须使用结构体指针的方法把函数的计算结果返回。说明：用户输入：运算符号(+,-,*,/) a b c d.输出：a+bi，输出时不管a,b是小于0或等于0都按该格式输出，输出时a,b都保留两位。输入：- 2.5 3.6 1.5 4.9输出：1.00+-1.30i2. 算法训练 Lift a

2、nd Throw  时间限制：3.0s   内存限制：256.0MB锦囊1锦囊2锦囊3问题描述给定一条标有整点(1, 2, 3, .)的射线. 定义两个点之间的距离为其下标之差的绝对值.Laharl, Etna, Flonne一开始在这条射线上不同的三个点, 他们希望其中某个人能够到达下标最大的点.每个角色只能进行下面的3种操作, 且每种操作不能每人不能进行超过一次.1.移动一定的距离2.把另一个角色高举过头3.将举在头上的角色扔出一段距离每个角色有一个movement range参数, 他们只能移动到没有人的位置, 并且起点和终点的距离不超过movement range.

3、如果角色A和另一个角色B距离为1, 并且角色B没有被别的角色举起, 那么A就能举起B. 同时, B会移动到A的位置,B原来所占的位置变为没有人的位置. 被举起的角色不能进行任何操作, 举起别人的角色不能移动.同时, 每个角色还有一个throwing range参数, 即他能把举起的角色扔出的最远的距离. 注意, 一个角色只能被扔到没有别的角色占据的位置. 我们认为一个角色举起另一个同样举起一个角色的角色是允许的. 这种情况下会出现3个人在同一个位置的情况. 根据前面的描述, 这种情况下上面的两个角色不能进行任何操作, 而最下面的角色可以同时扔出上面的两个角色. 你的任务是计算这些角色能够到达的

4、位置的最大下标, 即最大的数字x, 使得存在一个角色能够到达x.输入格式输入共三行, 分别为Laharl, Etna, Floone的信息.每一行有且仅有3个整数, 描述对应角色的初始位置, movement range, throwing range.数据保证3个角色的初始位置两两不相同且所有的数字都在1到10之间.</div>输出格式仅有1个整数, 即Laharl, Etna, Flonne之一能到达的最大距离.样例输入9 3 34 3 12 3 3样例输出15样例说明一开始Laharl在位置9, Etna在位置4, Flonne在位置2.首先, Laharl移动到6.然后Fl

5、onne移动到位置5并且举起Etna.Laharl举起Flonne将其扔到位置9.Flonne把Etna扔到位置12.Etna移动到位置15.3. 算法训练 Multithreading  时间限制：1.0s   内存限制：256.0MB锦囊1锦囊2锦囊3问题描述现有如下一个算法：repeat ni timesyi := yy := yi+1end repeat令n1为你需要算加法的第一个数字，n2为第二个，.nN为第N个数字（N为需要算加法的数字个数），并令y初始值为0，先令i=1运行这个算法（如上所示，重复ni次），然后令i=2运行这个算法。直到i=N。注意y值一直不要

6、清零。最后y的值就是你需要的加法答案。你想知道，有没有某种运算顺序能使答案等于W。一个循环中的全部语句，是不能改变在总的语句排列中的相对顺序的。（这里的第i个循环是指这ni*2条语句。就是你把属于第i个循环的语句抽出来看，它们需要按照原顺序排列。在你没有运行完这个循环的最靠前一条未完成的 语句的时候，你是不能跳过它先去完成这个循环后面的语句的。你能做的仅是把若干个循环按照你所规定的顺序“归并”起来。）举个例子，n1= 2 ,n2=1, W=1.一种可行的运算顺序是“2 1 1 1 1 2”，数字为几表示运行第几个算法的下一条语句（你可以看到”1”出现了4次，是因为n1=2即循环两次，而每次循环

7、里面有两条语句，所以2*2=4次）y值y1 值y2 值执行0条语句过后000执行1条过后(y2=y)000执行2条过后(y1=y)000执行3条过后(y=y1+1)100执行4条过后(y1=y)110执行5条过后(y=y1+1)210执行6条过后(y=y2+1)110可以看到，最后y值变成了1，也就完成了我们的任务。输入格式第一行你会得到用空格分开的两个整数N(1<=N<=100)和W(-109<=W<=109)，（N为需要算加法的数字个数，W是你希望算出的数）。第二行你会得到n个整数ni (1<=ni<=1000).输出格式第一行您应该输出Yes(若能以某

8、种顺序使得这个算法得出W的值) 或No。如果第一行是No，接下来就不用继续输出了。如果是Yes, 请在第2行输出2*sigma(ni)个用空格隔开的数，表示任意一种满足条件的运算顺序。样例输入1 1011样例输出No样例输入2 34 4样例输出Yes1 1 2 1 2 2 2 2 2 1 2 1 1 1 1 2样例输入3 61 2 3样例输出Yes1 1 2 2 2 2 3 3 3 3 3 3数据规模和约定对于30%的数据，n<=4, ni的和小于10.对于100%的数据，n<=100 , -109<=W<=109, 1<=ni<=10004. 算法训练 T

9、ricky and Clever Password  时间限制：2.0s   内存限制：256.0MB锦囊1锦囊2锦囊3问题描述在年轻的时候，我们故事中的英雄国王 Copa他的私人数据并不是完全安全地隐蔽。对他来说是，这不可接受的。因此，他发明了一种密码，好记又难以破解。后来，他才知道这种密码是一个长度为奇数的回文串。Copa 害怕忘记密码，所以他决定把密码写在一张纸上。他发现这样保存密码不安全，于是他决定按下述方法加密密码：他选定一个整数 X ，保证 X 不小于 0 ，且 2X 严格小于串长度。然后他把密码分成 3 段，最前面的 X 个字符为一段，最后面的 X 个字符为一

10、段，剩余的字符为一段。不妨把这三段依次称之为 prefix, suffix, middle 。显然， middle 的长度为一个大于 0 的奇数，且 prefix 、 suffix 的长度相等。他加密后的密码即为 A + prefix + B + middle + C + suffix ，其中 A 、 B 、 C 是三个由 Copa 选定的字符串，且都有可能为空， + 表示字符串相连。许多年过去了。Copa 昨天找到了当年写下加密后字符串的那张纸。但是，Copa 把原密码、A、B、C 都忘了。现在，他请你找一个尽量长的密码，使得这个密码有可能被当年的 Copa 发明、加密并写下。输入格式输入包

11、含一个只含有小写拉丁字母的字符串，长度在 1 到 105 之内。输出格式第一行包含一个整数 k ，表示你找到的原密码分成的 3 个部分中有多少个非空字符串。显然 k in 1, 3 。接下来 k 行，每行 2 个用空格分开的整数 x_i l_i ，表示这一部分的起始位置和长度。要求输出的 x_i 递增。起始位置 x_i 应该在 1 到加密后的字符串长度之间。 l_i 必须是正整数，因为你只要输出非空部分的信息。 middle 的长度必须为奇数。如果有多组答案，任意一组即可。提示：你要最大化的是输出的 l_i 的总和，而不是 k 。样例输入abacaba样例输出11 7样例输入axbya样例输出

12、31 12 15 1样例输入xabyczba样例输出32 24 17 2数据规模和约定对于 10% 的数据： n <= 10对于 30% 的数据： n <= 100对于 100% 的数据： n <= 100000存在 20% 的数据，输出文件第一行为 1 。5. 算法训练 Beaver's Calculator  时间限制：3.0s   内存限制：256.0MB锦囊1锦囊2锦囊3问题描述从万能词典来的聪明的海狸已经使我们惊讶了一次。他开发了一种新的计算器，他将此命名为"Beaver's Calculator 1.0"。它

13、非常特别，并且被计划使用在各种各样的科学问题中。为了测试它，聪明的海狸邀请了n位科学家，编号从1到n。第i位科学家给这个计算器带来了 ki个计算题。第i个科学家带来的问题编号1到n，并且它们必须按照编号一个一个计算，因为对于每个问题的计算都必须依赖前一个问题的计算结果。每个教授的每个问题都用一个数 ai,j 来描述，i（1in）是科学家的编号，j（1j ki ）是问题的编号， ai,j 表示解决这个问题所需资源单位的数量。这个计算器非常不凡。它一个接一个的解决问题。在一个问题解决后，并且在下一个问题被计算前，计算器分配或解放资源。计算器中最昂贵的操作是解放资源，解放远远慢于分配。所以对计算器而

14、言，每一个接下来的问题所需的资源不少于前一个，是非常重要的。给你关于这些科学家所给问题的相关信息。你需要给这些问题安排一个顺序，使得“坏对”尽可能少。所谓“坏对”，就是相邻两个问题中，后一个问题需求的资源比前一个问题少。别忘了，对于同一个科学家给出的问题，计算它们的相对顺序必须是固定的。输入格式第一行包含一个整数n，表示科学家的人数。接下来n行每行有5个整数，ki, ai,1, xi, yi, mi (0ai,1<mi109, 1xi,yi109) ，分别表示第i个科学家的问题个数，第1个问题所需资源单位数，以及3个用来计算 ai,j 的参量。ai,j=(ai,j-1*xi+yi)mod

15、 mi。输出格式第一行输出一个整数，表示最优顺序下最少的“坏对”个数。如果问题的总个数不超过200000,接下来输出 行，表示解决问题的最优顺序。每一行两个用空格隔开的整数，表示这个问题所需的资源单位数和提供这个问题的科学家的编号。样例输入22 1 1 1 102 3 1 1 10样例输出01 12 13 24 2数据规模和约定20%的数据 n=2, 1ki2000；另外30%的数据 n=2, 1ki200000；剩下50%的数据 1n5000, 1ki5000。6. 算法训练 Cowboys  时间限制：2.0s   内存限制：256.0MB锦囊1锦囊2锦囊3问题描述一个

16、间不容发的时刻：n个牛仔站立于一个环中，并且每个牛仔都用左轮手枪指着他旁边的人！每个牛仔指着他顺时针或者逆时针方向上的相邻的人。正如很多西部片那样，在这一刻，绳命是入刺的不可惜对峙的场景每秒都在变化。每秒钟牛仔们都会分析局势，当一对相邻的牛仔发现他们正在互指的时候，就会转过身。一秒内每对这样的牛仔都会转身。所有的转身都同时在一瞬间发生。我们用字母来表示牛仔所指的方向。“A”表示顺时针方向，“B”表示逆时针方向。如此，一个仅含“A”“B”的字符串便用来表示这个由牛仔构成的环。这是由第一个指着顺时针方向的牛仔做出的记录。例如，牛仔环“ABBBABBBA”在一秒后会变成“BABBBABBA”；而牛仔

17、环“BABBA”会变成“ABABB”。 这幅图说明了“BABBA”怎么变成“ABABB” 一秒过去了，现在用字符串s来表示牛仔们的排列。你的任务是求出一秒前有多少种可能的排列。如果某个排列中一个牛仔指向顺时针，而在另一个排列中他指向逆时针，那么这两个排列就是不同的。输入格式输入数据包括一个字符串s，它只含有“A”和“B”。输出格式输出你求出来的一秒前的可能排列数。数据规模和约定s的长度为3到100（包含3和100）样例输入BABBBABBA样例输出2样例输入ABABB样例输出2样例输入ABABAB样例输出4样例说明测试样例一中，可能的初始排列为："ABBBABBAB"和 &

18、quot;ABBBABBBA"。测试样例二中，可能的初始排列为："AABBB"和"BABBA"。7. 算法训练 数字三角形  时间限制：1.0s   内存限制：256.0MB锦囊1锦囊2锦囊3问题描述（图.）示出了一个数字三角形。 请编一个程序计算从顶至底的某处的一条路径，使该路径所经过的数字的总和最大。每一步可沿左斜线向下或右斜线向下走；1三角形行数100；三角形中的数字为整数0，1，99；.（图.）输入格式文件中首先读到的是三角形的行数。接下来描述整个三角形输出格式最大总和（整数）样例输入573 88 1 02 7 4

19、44 5 2 6 5样例输出308. 算法训练 未名湖边的烦恼  时间限制：1.0s   内存限制：256.0MB锦囊1锦囊2锦囊3问题描述每年冬天，北大未名湖上都是滑冰的好地方。北大体育组准备了许多冰鞋，可是人太多了，每天下午收工后，常常一双冰鞋都不剩。每天早上，租鞋窗口都会排起长龙，假设有还鞋的m个，有需要租鞋的n个。现在的问题是，这些人有多少种排法，可以避免出现体育组没有冰鞋可租的尴尬场面。（两个同样需求的人（比如都是租鞋或都是还鞋）交换位置是同一种排法）输入格式两个整数，表示m和n输出格式一个整数，表示队伍的排法的方案数。样例输入3 2样例输出5数据规模和约定m,n

20、0,18问题分析9. 算法训练 最大的算式  时间限制：1.0s   内存限制：256.0MB锦囊1锦囊2锦囊3问题描述题目很简单，给出N个数字，不改变它们的相对位置，在中间加入K个乘号和N-K-1个加号，（括号随便加）使最终结果尽量大。因为乘号和加号一共就是N-1个了，所以恰好每两个相邻数字之间都有一个符号。例如：N=5，K=2，5个数字分别为1、2、3、4、5，可以加成：1*2*(3+4+5)=241*(2+3)*(4+5)=45(1*2+3)*(4+5)=45输入格式输入文件共有二行，第一行为两个有空格隔开的整数，表示N和K，其中（2<=N<=15, 0&

21、lt;=K<=N-1）。第二行为 N个用空格隔开的数字（每个数字在0到9之间）。输出格式输出文件仅一行包含一个整数，表示要求的最大的结果样例输入5 21 2 3 4 5样例输出120样例说明(1+2+3)*4*5=12010. 算法训练 图形显示  时间限制：1.0s   内存限制：512.0MB锦囊1锦囊2锦囊3问题描述编写一个程序，首先输入一个整数，例如5，然后在屏幕上显示如下的图形（5表示行数）：* * * * * * * * * * *11. 算法训练 排序  时间限制：1.0s   内存限制：512.0MB锦囊1锦囊2锦囊3问题描述编写一

22、个程序，输入3个整数，然后程序将对这三个整数按照从大到小进行排列。输入格式：输入只有一行，即三个整数，中间用空格隔开。输出格式：输出只有一行，即排序后的结果。输入输出样例样例输入9 2 30样例输出30 9 2登录后才能查看试题。12. 算法训练 2的次幂表示  时间限制：1.0s   内存限制：512.0MB锦囊1锦囊2锦囊3问题描述任何一个正整数都可以用2进制表示，例如：137的2进制表示为10001001。将这种2进制表示写成2的次幂的和的形式，令次幂高的排在前面，可得到如下表达式：137=27+23+20现在约定幂次用括号来表示，即ab表示为a（b）此时，137可表

23、示为：2（7）+2（3）+2（0）进一步：7=22+2+20 （21用2表示）3=2+20 所以最后137可表示为：2（2（2）+2+2（0）+2（2+2（0）+2（0）又如：1315=210+28+25+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

24、)+2+2(0)提示用递归实现会比较简单，可以一边递归一边输出13. 算法训练 前缀表达式  时间限制：1.0s   内存限制：512.0MB锦囊1锦囊2锦囊3问题描述编写一个程序，以字符串方式输入一个前缀表达式，然后计算它的值。输入格式为：“运算符 对象1 对象2”，其中，运算符为“+”（加法）、“-”（减法）、“*”（乘法）或“/”（除法），运算对象为不超过10的整数，它们之间用一个空格隔开。要求：对于加、减、乘、除这四种运算，分别设计相应的函数来实现。输入格式：输入只有一行，即一个前缀表达式字符串。输出格式：输出相应的计算结果（如果是除法，直接采用c语言的“/”运算符

25、，结果为整数）。输入输出样例样例输入+ 5 2样例输出714. 算法训练 Anagrams问题  时间限制：1.0s   内存限制：512.0MB锦囊1锦囊2锦囊3问题描述Anagrams指的是具有如下特性的两个单词：在这两个单词当中，每一个英文字母（不区分大小写）所出现的次数都是相同的。例如，“Unclear”和“Nuclear”、“Rimon”和“MinOR”都是Anagrams。编写一个程序，输入两个单词，然后判断一下，这两个单词是否是Anagrams。每一个单词的长度不会超过80个字符，而且是大小写无关的。输入格式：输入有两行，分别为两个单词。输出格式：输出只有一个

26、字母Y或N，分别表示Yes和No。输入输出样例样例输入UnclearNuclear样例输出Y15. 算法训练 出现次数最多的整数  时间限制：1.0s   内存限制：512.0MB锦囊1锦囊2锦囊3问题描述编写一个程序，读入一组整数，这组整数是按照从小到大的顺序排列的，它们的个数N也是由用户输入的，最多不会超过20。然后程序将对这个数组进行统计，把出现次数最多的那个数组元素值打印出来。如果有两个元素值出现的次数相同，即并列第一，那么只打印比较小的那个值。输入格式：第一行是一个整数N，N £ 20；接下来有N行，每一行表示一个整数，并且按照从小到大的顺序排列。输出格

27、式：输出只有一行，即出现次数最多的那个元素值。输入输出样例样例输入5100150150200250样例输出15016. 算法训练 字串统计  时间限制：1.0s   内存限制：512.0MB锦囊1锦囊2锦囊3问题描述给定一个长度为n的字符串S，还有一个数字L，统计长度大于等于L的出现次数最多的子串（不同的出现可以相交），如果有多个，输出最长的，如果仍然有多个，输出第一次出现最早的。输入格式第一行一个数字L。第二行是字符串S。L大于0，且不超过S的长度。输出格式一行，题目要求的字符串。输入样例1：4bbaabbaaaaa输出样例1：bbaa输入样例2：2bbaabbaaaaa

28、输出样例2：aa数据规模和约定n<=60S中所有字符都是小写英文字母。提示枚举所有可能的子串，统计出现次数，找出符合条件的那个17. 算法训练 矩阵乘法  时间限制：1.0s   内存限制：512.0MB锦囊1锦囊2锦囊3问题描述输入两个矩阵，分别是m*s，s*n大小。输出两个矩阵相乘的结果。输入格式第一行，空格隔开的三个正整数m,s,n（均不超过200）。接下来m行，每行s个空格隔开的整数，表示矩阵A（i，j）。接下来s行，每行n个空格隔开的整数，表示矩阵B（i，j）。输出格式m行，每行n个空格隔开的整数，输出相乘後的矩阵C（i，j）的值。样例输入2 3 21 0

29、-11 1 -30 31 23 1样例输出-3 2-8 2提示矩阵C应该是m行n列，其中C(i,j)等于矩阵A第i行行向量与矩阵B第j列列向量的内积。例如样例中C(1,1)=(1,0,-1)*(0,1,3) = 1 * 0 +0*1+(-1)*3=-318. 算法训练 大小写转换  时间限制：1.0s   内存限制：512.0MB锦囊1锦囊2锦囊3问题描述编写一个程序，输入一个字符串（长度不超过20），然后把这个字符串内的每一个字符进行大小写变换，即将大写字母变成小写，小写字母变成大写，然后把这个新的字符串输出。输入格式：输入一个字符串，而且这个字符串当中只包含英文字母，不

30、包含其他类型的字符，也没有空格。输出格式：输出经过转换后的字符串。输入输出样例样例输入AeDb样例输出aEdB19. 算法训练 动态数组使用  时间限制：1.0s   内存限制：512.0MB锦囊1锦囊2锦囊3从键盘读入n个整数，使用动态数组存储所读入的整数，并计算它们的和与平均值分别输出。要求尽可能使用函数实现程序代码。平均值为小数的只保留其整数部分。样例输入: 5 3 4 0 0 2样例输出:9 1样例输入: 73 2 7 5 2 9 1样例输出:29 420. 算法训练 删除数组零元素  时间限制：1.0s   内存限制：512.0MB 

31、   锦囊1锦囊2锦囊3从键盘读入n个整数放入数组中，编写函数CompactIntegers，删除数组中所有值为0的元素，其后元素向数组首端移动。注意，CompactIntegers函数需要接受数组及其元素个数作为参数，函数返回值应为删除操作执行后数组的新元素个数。输出删除后数组中元素的个数并依次输出数组元素。样例输入: （输入格式说明：5为输入数据的个数，3 4 0 0 2 是以空格隔开的5个整数）5 3 4 0 0 2样例输出:（输出格式说明：3为非零数据的个数，3 4 2 是以空格隔开的3个非零整数）33 4 2样例输入: 70 0 7 0 0 9 0样例输出:27 9样例输入

32、: 30 0 0样例输出:021. 算法训练 最小乘积(基本型)  时间限制：1.0s   内存限制：512.0MB锦囊1锦囊2锦囊3问题描述给两组数，各n个。请调整每组数的排列顺序，使得两组数据相同下标元素对应相乘，然后相加的和最小。要求程序输出这个最小值。例如两组数分别为:1 3-5和-2 4 1那么对应乘积取和的最小值应为：(-5) * 4 + 3 * (-2) + 1 * 1 = -25输入格式第一个行一个数T表示数据组数。后面每组数据，先读入一个n，接下来两行每行n个数，每个数的绝对值小于等于1000。n<=8,T<=1000输出格式一个数表示答案。样

33、例输入231 3 -5-2 4 151 2 3 4 51 0 1 0 1样例输出-256登录后才能查看试题。22. 算法训练 Torry的困惑(基本型)  时间限制：1.0s   内存限制：512.0MB锦囊1锦囊2锦囊3问题描述Torry从小喜爱数学。一天，老师告诉他，像2、3、5、7这样的数叫做质数。Torry突然想到一个问题，前10、100、1000、10000个质数的乘积是多少呢？他把这个问题告诉老师。老师愣住了，一时回答不出来。于是Torry求助于会编程的你，请你算出前n个质数的乘积。不过，考虑到你才接触编程不久，Torry只要你算出这个数模上50000的值。输入

34、格式仅包含一个正整数n，其中n<=100000。输出格式输出一行，即前n个质数的乘积模50000的值。样例输入1样例输出2登录后才能查看试题。23. 算法训练 寻找数组中最大值  时间限制：1.0s   内存限制：512.0MB锦囊1锦囊2锦囊3问题描述对于给定整数数组a,寻找其中最大值，并返回下标。输入格式整数数组a,数组元素个数小于1等于100。输出数据分作两行：第一行只有一个数，表示数组元素个数；第二行为数组的各个元素。输出格式输出最大值，及其下标样例输入33 2 1样例输出3 024. 算法训练 关联矩阵  时间限制：1.0s   内存限制

35、：512.0MB锦囊1锦囊2锦囊3问题描述有一个n个结点m条边的有向图，请输出他的关联矩阵。输入格式第一行两个整数n、m，表示图中结点和边的数目。n<=100,m<=1000。接下来m行，每行两个整数a、b，表示图中有(a,b)边。注意图中可能含有重边，但不会有自环。输出格式输出该图的关联矩阵，注意请勿改变边和结点的顺序。样例输入5 91 23 11 52 52 32 33 24 35 4样例输出1 -1 1 0 0 0 0 0 0-1 0 0 1 1 1 -1 0 00 1 0 0 -1 -1 1 -1 00 0 0 0 0 0 0 1 -10 0 -1 -1 0 0 0 0 1

36、25. 算法训练 送分啦  时间限制：1.0s   内存限制：512.0MB锦囊1锦囊2锦囊3问题描述这题想得分吗？想，请输出“yes”；不想，请输出“no”。输出格式输出包括一行，为“yes”或“no”。 26. 算法训练 操作格子  时间限制：1.0s   内存限制：256.0MB锦囊1锦囊2锦囊3问题描述有n个格子，从左到右放成一排，编号为1-n。共有m次操作，有3种操作类型：1.修改一个格子的权值，2.求连续一段格子权值和，3.求连续一段格子的最大值。对于每个2、3操作输出你所求出的结果。输入格式第一行2个整数n，m。接下来一行n个整数

37、表示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 31 2 3 42 1 31 4 33 1 4 样例输出63 数据规模与约定对于20%的数据n <= 100，m <= 200。对于50%的数据n <= 5000，m <= 5000。对于100%的数据1 <= n <= 100000，m <= 100000，0

38、 <= 格子权值 <= 10000。27. 算法训练 逆序对  时间限制：1.0s   内存限制：256.0MB锦囊1锦囊2锦囊3问题描述Alice是一个让人非常愉跃的人!他总是去学习一些他不懂的问题，然后再想出许多稀奇古怪的题目。这几天，Alice又沉浸在逆序对的快乐当中，他已近学会了如何求逆序对对数，动态维护逆序对对数等等题目，他认为把这些题让你做简直是太没追求了，于是，经过一天的思考和完善，Alice终于拿出了一道他认为差不多的题目：有一颗2n-1个节点的二叉树，它有恰好n个叶子节点，每个节点上写了一个整数。如果将这棵树的所有叶子节点上的数从左到右写下来，

39、便得到一个序列a1an。现在想让这个序列中的逆序对数量最少，但唯一的操作就是选树上一个非叶子节点，将它的左右两颗子树交换。他可以做任意多次这个操作。求在最优方案下，该序列的逆序对数最少有多少。Alice自己已近想出了题目的正解，他打算拿来和你分享，他要求你在最短的时间内完成。输入格式第一行一个整数n。下面每行，一个数x。如果x=0，表示这个节点非叶子节点，递归地向下读入其左孩子和右孩子的信息，如果x0，表示这个节点是叶子节点，权值为x。输出格式输出一个整数，表示最少有多少逆序对。 样例输入300312 样例输出1 数据规模与约定对于20%的数据，n <= 5000。对于100%的数据，1

40、 <= n <= 200000，0 <= ai<231。28. 算法训练 安慰奶牛  时间限制：1.0s   内存限制：256.0MB锦囊1锦囊2锦囊3问题描述Farmer John变得非常懒，他不想再继续维护供奶牛之间供通行的道路。道路被用来连接N个牧场，牧场被连续地编号为1到N。每一个牧场都是一个奶牛的家。FJ计划除去P条道路中尽可能多的道路，但是还要保持牧场之间 的连通性。你首先要决定那些道路是需要保留的N-1条道路。第j条双向道路连接了牧场Sj和Ej(1 <= Sj <= N; 1 <= Ej <= N; Sj !=

41、Ej)，而且走完它需要Lj的时间。没有两个牧场是被一条以上的道路所连接。奶牛们非常伤心，因为她们的交通系统被削减了。你需要到每一个奶牛的住处去安慰她们。每次你到达第i个牧场的时候(即使你已经到过)，你必须花去Ci的时间和奶牛交谈。你每个晚上都会在同一个牧场(这是供你选择的)过夜，直到奶牛们都从悲伤中缓过神来。在早上 起来和晚上回去睡觉的时候，你都需要和在你睡觉的牧场的奶牛交谈一次。这样你才能完成你的 交谈任务。假设Farmer John采纳了你的建议，请计算出使所有奶牛都被安慰的最少时间。输入格式第1行包含两个整数N和P。接下来N行，每行包含一个整数Ci。接下来P行，每行包含三个整数Sj, E

42、j和Lj。输出格式输出一个整数, 所需要的总时间(包含和在你所在的牧场的奶牛的两次谈话时间)。 样例输入5 71010206301 2 52 3 52 4 123 4 172 5 153 5 6 样例输出176 数据规模与约定5 <= N <= 10000，N-1 <= P <= 100000，0 <= Lj <= 1000，1 <= Ci <= 1,000。29. 算法训练 最短路  时间限制：1.0s   内存限制：256.0MB锦囊1锦囊2锦囊3问题描述给定一个n个顶点，m条边的有向图（其中某些边权可能为负，但保证没有负

43、环）。请你计算从1号点到其他点的最短路（顶点从1到n编号）。输入格式第一行两个整数n, m。接下来的m行，每行有三个整数u, v, l，表示u到v有一条长度为l的边。输出格式共n-1行，第i行表示1号点到i+1号点的最短路。 样例输入3 31 2 -12 3 -13 1 2 样例输出-1-2 数据规模与约定对于10%的数据，n = 2，m = 2。对于30%的数据，n <= 5，m <= 10。对于100%的数据，1 <= n <= 20000，1 <= m <= 200000，-10000 <= l <= 10000，保证从任意顶点都能到达其他

44、所有顶点。30. 算法训练 结点选择  时间限制：1.0s   内存限制：256.0MB锦囊1锦囊2锦囊3问题描述有一棵 n 个节点的树，树上每个节点都有一个正整数权值。如果一个点被选择了，那么在树上和它相邻的点都不能被选择。求选出的点的权值和最大是多少？输入格式第一行包含一个整数 n 。接下来的一行包含 n 个正整数，第 i 个正整数代表点 i 的权值。接下来一共 n-1 行，每行描述树上的一条边。输出格式输出一个整数，代表选出的点的权值和的最大值。 样例输入51 2 3 4 51 21 32 42 5 样例输出12 样例说明选择3、4、5号点，权值和为 3+4+5 =

45、12 。 数据规模与约定对于20%的数据， n <= 20。对于50%的数据， n <= 1000。对于100%的数据， n <= 100000。权值均为不超过1000的正整数。31. 算法训练 K好数  时间限制：1.0s   内存限制：256.0MB锦囊1锦囊2锦囊3问题描述如果一个自然数N的K进制表示中任意的相邻的两位都不是相邻的数字，那么我们就说这个数是K好数。求L位K进制数中K好数的数目。例如K = 4，L = 2的时候，所有K好数为11、13、20、22、30、31、33 共7个。由于这个数目很大，请你输出它对1000000007取模后的值。输

46、入格式输入包含两个正整数，K和L。输出格式输出一个整数，表示答案对1000000007取模后的值。 样例输入4 2 样例输出7 数据规模与约定对于30%的数据，KL <= 106；对于50%的数据，K <= 16， L <= 10；对于100%的数据，1 <= K,L <= 100。登录后才能查看试题。32. 算法训练 最大最小公倍数  时间限制：1.0s   内存限制：256.0MB锦囊1锦囊2锦囊3问题描述已知一个正整数N，问从1N中任选出三个数，他们的最小公倍数最大可以为多少。输入格式输入一个正整数N。输出格式输出一个整数，表示你找到的最

47、小公倍数。样例输入9样例输出504数据规模与约定1 <= N <= 106。登录后才能查看试题。33. 算法训练 区间k大数查询  时间限制：1.0s   内存限制：256.0MB锦囊1锦囊2锦囊3问题描述给定一个序列，每次询问序列中第l个数到第r个数中第K大的数是哪个。输入格式第一行包含一个数n，表示序列长度。第二行包含n个正整数，表示给定的序列。第三个包含一个正整数m，表示询问个数。接下来m行，每行三个数l,r,K，表示询问序列从左往右第l个数到第r个数中，从大往小第K大的数是哪个。序列元素从1开始标号。输出格式总共输出m行，每行一个数，表示询问的答案。 样

48、例输入51 2 3 4 521 5 22 3 2 样例输出42 数据规模与约定对于30%的数据，n,m<=100；对于100%的数据，n,m<=1000；保证k<=(r-l+1)，序列中的数<=106。34. 法训练 P1102  VIP时间限制：1.0s   内存限制：256.0MB锦囊1锦囊2锦囊3定义一个学生结构体类型student，包括4个字段，姓名、性别、年龄和成绩。然后在主函数中定义一个结构体数组（长度不超过1000），并输入每个元素的值，程序使用冒泡排序法将学生按照成绩从小到大的顺序排序，然后输出排序的结果。输入格式：第一行是一个整数N

49、（N<1000），表示元素个数；接下来N行每行描述一个元素，姓名、性别都是长度不超过20的字符串，年龄和成绩都是整型。输出格式：按成绩从小到大输出所有元素，若多个学生成绩相同则成绩相同的同学之间保留原来的输入顺序。输入：3Alice female 18 98Bob male 19 90Miller male 17 92输出：Bob male 19 90Miller male 17 92Alice female 18 9835. 算法训练 P1101  时间限制：1.0s   内存限制：256.0MB 锦囊1锦囊2锦囊3有一份提货单，其数据项目有：商品名（MC）、单价（

50、DJ）、数量（SL）。定义一个结构体prut，其成员是上面的三项数据。在主函数中定义一个prut类型的结构体数组，输入每个元素的值，计算并输出提货单的总金额。输入格式：第一行是数据项个数N(N<100)，接下来每一行是一个数据项。商品名是长度不超过100的字符串，单价为double类型，数量为整型。输出格式：double类型的总金额。输入：4book 12.5 3pen 2.5 10computer 3200 1flower 47 5输出：3497.50000036. 算法训练 s01串  时间限制：1.0s   内存限制：256.0MB锦囊1锦囊2锦囊3问题描述s0

51、1串初始为"0"按以下方式变换0变1，1变01输入格式1个整数(019)输出格式n次变换后s01串样例输入3样例输出101数据规模和约定01937. 算法训练 Representative Sampling (30_points)  时间限制：2.0s   内存限制：256.0MB锦囊1锦囊2锦囊3【题目描述】来自ABBYY的小明有一个与“细胞与遗传学研究所”的合作。最近，研究所用一个新的题目考验小明。题目如下。有由n个细胞组成的一个集合（不一定不同）每个细胞是一个由小写拉丁字母组成的字符串。科学家给小明提出的问题是从给定集合中选出一个大小为k的子集，使

52、得所选子集的代表值最大。小明做了些研究并得出了一个结论，即一个蛋白质集合的代表制可以用一个方便计算的整数来表示。我们假设当前的集合为a1,.,ak，包含了k个用以表示蛋白质的字符串。那么蛋白质集合的代表值可以用如下的式子来表示：其中f(x,y)表示字符串x和y的最长公共前缀的长度，例如：f("abc", "abd")=2 ， f("ab", "bcd")=0.因此，蛋白质集合"abc", "abd", "abe"的代表值等于6，集合"aaa&qu

53、ot;, "ba", "ba"的代表值等于2。在发现了这个之后，小明要求赛事参与者写一个程序选出，给定蛋白质的集合中的大小为k的子集中，能获得最大可能代表性值得一个子集。帮助他解决这个问题吧！【输入格式】输入数据第一行包含2个正整数n和k（1kn），由一个空格隔开。接下来的n行每一行都包含对蛋白质的描述。每个蛋白质都是一个仅有不超过500个小写拉丁字母组成的非空字符串。有些字符串可能是相等的。输出格式输出一个整数，表示给定蛋白质集合的大小为k的子集的代表值最大可能是多少。【数据规模】20%的数据保证：1n2050%的数据保证：1n100100%的数据保证：1n2000【样例输入1】3 2ababzdabq【样例输出1】2【样例输入2】4 3eeerrrtttqqq【样例输出2】0【样例输入3】4 3aaaabbaabbcabbd【样例输出3】938. 算法训练 Buying Sets  时间限制：2.0s   内存限制：256.0MB锦囊1锦囊2锦囊3问题描述给定n个集合, 要求选出其中某些集合, 使得这些集合的并集的势, 等于选出的集合的数目.对于任意的k(1<=k<=n), 满从中