4 2
数据规模与约定
对于30%的数据，n,m<=100； 对于100%的数据，n,m<=1000； 保证k<=(r-l+1)，序列中的数<=106。
34. 法训练 P1102 VIP
时间限制：1.0s 内存限制：256.0MB
定义一个学生结构体类型student，包括4个字段，姓名、性别、年龄和成绩。然后在主函数中定义一个结构体数组（长度不超过1000），并输入每个元素的值，程序使用冒泡排序法将学生按照成绩从小到大的顺序排序，然后输出排序的结果。
输入格式：第一行是一个整数N（N<1000），表示元素个数；接下来N行每行描述一个元素，姓名、性别都是长度不超过20的字符串，年龄和成绩都是整型。
输出格式：按成绩从小到大输出所有元素，若多个学生成绩相同则成绩相同的同学之间保留原来的输入顺序。 输入： 3
Alice female 18 98 Bob male 19 90 Miller male 17 92 输出：
Bob male 19 90 Miller male 17 92 Alice female 18 98
35. 算法训练 P1101
时间限制：1.0s 内存限制：256.0MB
有一份提货单，其数据项目有：商品名（MC）、单价（DJ）、数量（SL）。定义一个结构体prut，其成员是上面的三项数据。在主函数中定义一个prut类型的结构体数组，输入每个元素的值，计算并输出提货单的总金额。
输入格式：第一行是数据项个数N(N<100)，接下来每一行是一个数据项。商品名是长度不超过100的字符串，单价为double类型，数量为整型。 输出格式：double类型的总金额。 输入： 4
book 12.5 3 pen 2.5 10
26
computer 3200 1 flower 47 5 输出：
3497.500000
36. 算法训练 s01串
时间限制：1.0s 内存限制：256.0MB
问题描述
s01串初始为\ 按以下方式变换 0变1，1变01 输入格式
1个整数(0~19) 输出格式
n次变换后s01串 样例输入 3 样例输出 101
数据规模和约定 0~19
37. 算法训练 Representative Sampling
(30_points)
时间限制：2.0s 内存限制：256.0MB
【题目描述】
来自ABBYY的小明有一个与―细胞与遗传学研究所‖的合作。最近，研究所用一个新的题目考验小明。题目如下。
有由n个细胞组成的一个集合（不一定不同）每个细胞是一个由小写拉丁字母组成的字符串。科学家给小明提出的问题是从给定集合中选出一个大小为k的子集，使得所选子集的代表值最大。
小明做了些研究并得出了一个结论，即一个蛋白质集合的代表制可以用一个方便计算的整数来表示。我们假设当前的集合为{a1,?...,?ak}，包含了k个用以表示蛋白质的字符串。那么蛋白质集合的代表值可以用如下的式子来表示：
27
其中f(x,?y)表示字符串x和y的最长公共前缀的长度，例如： f(\，f(\\
因此，蛋白质集合{\的代表值等于6，集合{\的代表值等于2。
在发现了这个之后，小明要求赛事参与者写一个程序选出，给定蛋白质的集合中的大小为k的子集中，能获得最大可能代表性值得一个子集。帮助他解决这个问题吧！ 【输入格式】
输入数据第一行包含2个正整数n和k（1≤k≤n），由一个空格隔开。接下来的n行每一行都包含对蛋白质的描述。每个蛋白质都是一个仅有不超过500个小写拉丁字母组成的非空字符串。有些字符串可能是相等的。 输出格式
输出一个整数，表示给定蛋白质集合的大小为k的子集的代表值最大可能是多少。
【数据规模】
20%的数据保证：1?≤?n?≤?20 50%的数据保证：1?≤?n?≤?100 100%的数据保证：1?≤?n?≤?2000
【样例输入1】 3 2 aba bzd abq 【样例输出1】 2
【样例输入2】 4 3 eee rrr ttt qqq 【样例输出2】 0
【样例输入3】 4 3 aaa abba abbc abbd
28
【样例输出3】 9
38. 算法训练 Buying Sets
时间限制：2.0s 内存限制：256.0MB
问题描述
给定n个集合, 要求选出其中某些集合, 使得这些集合的并集的势, 等于选出的集合的数目.
对于任意的k(1<=k<=n), 满从中选出任意k个集合, 这k个集合的并集的势一定大于等于k.
每个集合有一个权值, 每个选择方案的代价是所选的集合的权值的和. 请输出代价最小的选择方案的代价.
当然, 不选择任何一个集合是一个可行的方案(权值和为0), 但不一定最优(权值和可以为负). 输入格式
第一行一个正整数n(1<=n<=300), 为集合个数. 在接下来n行中, 第i行描述第i个集合:
首先给出一个正整数m[i]为该集合的势, 显然1<=m[i]<=n. 接下来m[i]个在1到n之间的整数, 表示该集合中的元素. 最后一行n个整数, 为每个集合的权值, 绝对值不超过1e6. 输出格式
仅一个整数, 为代价最小的选择方案的代价. 样例输入 3 1 1 2 2 3 1 3
10 20 -3 样例输出 -3 样例输入 5
2 1 2 2 2 3 2 3 4 2 4 5
29
2 5 1
1 -1 1 -1 1 样例输出 0 样例输入 5
2 1 2 2 2 3 2 3 4 2 4 5 2 5 1
-1 1 -1 1 -1 样例输出 -1
39. 算法训练 Don't fear, DravDe is kind
时间限制：2.0s 内存限制：256.0MB
问题描述
这一天，有一列车子排起了一排长队，必经之路是一个被魔王笼罩的山洞。每辆车的司机害怕魔王程度不同，所以每个司机有一些要求。 车子有n台，排成一条长队，每辆车有4个属性:
V ——这辆车的总价值，价值就是比如它其中的乘客和货物的价值
c ——这辆车里面的人数量（司机表示自己也算一个乘客，司机和乘客不用区分开来） l ——在这辆车的前面需要总量正好为多少乘客的车（不多也不少），这车才敢开 r ——在这辆车的后面需要总量正好为多少乘客的车（不多也不少），这车才敢开 ―前面需要总量正好为多少乘客的车‖指的是驶在这辆车前面所有的车的乘客总数。 ―后面需要总量正好为多少乘客的车‖指的是驶在这辆车后面所有的车的乘客总数。 你不能改变每辆车在车队的相对顺序，但你可以安排某些车退出车队，保证依然在车队的每辆车都敢开了，即满足上述条件，并且剩下车的v的总量最大。 -----------------------------
简单来说，给您按输入顺序排列的n辆车，您需要删去里面的一些车（剩下的车仍然按原相对顺序排列）。
使得对于每辆车，若它没被删去，设其为输入的第i辆车， 要满足
l[i]= sigma{c[j] | ji 且第j辆车没被删去}
在满足这些条件前提下，要求sigma{V[i] | i没被删去} 最大， 请输出这个最大值，并且递增输出没有被删去的车的标号。
30