一、实操题
1、明明的随机数
【问题描述】
明明想在学校中请一些同学一起做一项问卷调查，为了实验的客观性，他先用计算机生成了N个1到1000之间的随机整数（N≤100），对于其中重复的数字，只保留一个，把其余相同的数去掉，不同的数对应着不同的学生的学号。然后再把这些数从小到大排序，按照排好的顺序去找同学做调查。请你协助明明完成“去重”与“排序”的工作。
【输入文件】
输入文件random.in 有2行，第1行为1个正整数，表示所生成的随机数的个数：
N
第2行有N个用空格隔开的正整数，为所产生的随机数。
【输出文件】
输出文件random.out 也是2行，第1行为1个正整数M，表示不相同的随机数的个数。第2行为M个用空格隔开的正整数，为从小到大排好序的不相同的随机数。
【输入样例】
10
20 40 32 67 40 20 89 300 400 15
【输出样例】
8
15 20 32 40 67 89 300 400
参考答案：1. 首先读取输入文件random.in，获取第一行的N，表示随机数的个数。2. 读取第二行的N个用空格隔开的正整数，存储到一个列表中。3. 使用Python的set数据结构去除列表中的重复元素，得到一个新的列表。4. 对新的列表进行排序。5. 输出第一行为不相同的随机数的个数，即新列表的长度。6. 输出第二行为排序后的不相同的随机数列表。
解析：【喵呜刷题小喵解析】：
本题要求实现的功能包括去重和排序。去重可以使用Python的set数据结构来实现，因为set会自动去除重复元素。排序则可以使用Python的sorted函数来实现。
具体步骤如下：
1. 读取输入文件random.in，获取第一行的N，表示随机数的个数。
2. 读取第二行的N个用空格隔开的正整数，存储到一个列表中。
3. 使用Python的set数据结构去除列表中的重复元素，得到一个新的列表。
4. 对新的列表进行排序，可以使用Python的sorted函数来实现。
5. 输出第一行为不相同的随机数的个数，即新列表的长度。
6. 输出第二行为排序后的不相同的随机数列表。
需要注意的是，本题要求输出到文件random.out，因此在输出时需要使用文件操作。具体可以使用Python的open函数来打开文件，然后使用文件的write方法将结果写入文件。最后需要记得关闭文件。
2、开心的金明
【问题描述】
金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间他自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过N元钱就行”。今天一早金明就开始做预算，但是他想买的东西太多了，肯定会超过妈妈限定的N元。于是，他把每件物品规定了一个重要度，分为5等：用整数1~5表示，第5等最重要。他还从因特网上查到了每件物品的价格（都是整数元）。他希望在不超过N元（可以等于N元）的前提下，使每件物品的价格与重要度的乘积的总和最大。
设第j件物品的价格为v[j]，重要度为w[j]，共选中了k件物品，编号依次为j1，j2，……，jk，则所求的总和为：
v[j1]*w[j1]+v[j2]*w[j2]+ …+v[jk]*w[jk]。（其中*为乘号）
请你帮助金明设计一个满足要求的购物单。
【输入文件】
输入文件happy.in 的第1行，为两个正整数，用一个空格隔开：
N m
（其中N（<30000）表示总钱数，m（<25）为希望购买物品的个数。）
从第2行到第m+1行，第j行给出了编号为j-1的物品的基本数据，每行有2个非负整数
v p
（其中v表示该物品的价格(v<=10000)，p表示该物品的重要度(1~5)）
【输出文件】
输出文件happy.out只有一个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值（<100000000）。
【输入样例】
1000 5
800 2
400 5
300 5
400 3
200 2
【输出样例】
3900
参考答案：本题要求在给定的预算内，选择物品使得物品的价格与重要度的乘积之和最大。可以使用01背包问题的思想来解决。具体思路如下：1. 定义一个二维数组dp[i][j]，其中dp[i][j]表示在前i个物品中选择若干个物品，且总钱数不超过j时，所能得到的物品价格与重要度乘积的最大值。2. 对于第i个物品，其重要度为w[i]，价格为v[i]。则可以选择买或不买。如果选择买，则在前i-1个物品中选择若干个物品，且总钱数不超过j-v[i]时，所能得到的物品价格与重要度乘积的最大值加上v[i]*w[i]。如果选择不买，则在前i个物品中选择若干个物品，且总钱数不超过j时，所能得到的物品价格与重要度乘积的最大值即为dp[i-1][j]。3. 因此，状态转移方程为：dp[i][j] = max(dp[i-1][j], dp[i-1][j-v[i]]+v[i]*w[i])。4. 最终答案为dp[m][N]。
解析：【喵呜刷题小喵解析】：
本题是一个典型的优化问题，可以使用动态规划来解决。在动态规划中，我们定义状态dp[i][j]，表示在前i个物品中选择若干个物品，且总钱数不超过j时，所能得到的物品价格与重要度乘积的最大值。根据物品的重要度和价格，我们可以选择买或不买。如果选择买，则在前i-1个物品中选择若干个物品，且总钱数不超过j-v[i]时，所能得到的物品价格与重要度乘积的最大值加上v[i]*w[i]。如果选择不买，则在前i个物品中选择若干个物品，且总钱数不超过j时，所能得到的物品价格与重要度乘积的最大值即为dp[i-1][j]。因此，我们可以使用状态转移方程dp[i][j] = max(dp[i-1][j], dp[i-1][j-v[i]]+v[i]*w[i])来求解。最终答案为dp[m][N]。
3、Jam的计数法
【问题描述】
Jam是个喜欢标新立异的科学怪人。他不使用阿拉伯数字计数，而是使用小写英文字母计数，他觉得这样做，会使世界更加丰富多彩。在他的计数法中，每个数字的位数都是相同的（使用相同个数的字母），英文字母按原先的顺序，排在前面的字母小于排在它后面的字母。我们把这样的“数字”称为Jam数字。在Jam数字中，每个字母互不相同，而且从左到右是严格递增的。每次，Jam还指定使用字母的范围，例如，从2到10，表示只能使用{b,c,d,e,f,g,h,i,j}这些字母。如果再规定位数为5，那么，紧接在Jam数字“bdfij”之后的数字应该是“bdghi”。（如果我们用U、V依次表示Jam数字“bdfij”与“bdghi”，则U<V< span>，且不存在Jam数字P，使U<P<V< span>）。你的任务是：对于从文件读入的一个Jam数字，按顺序输出紧接在后面的5个Jam数字，如果后面没有那么多Jam数字，那么有几个就输出几个。
【输入文件】
输入文件counting.in 有2行，第1行为3个正整数，用一个空格隔开：
s t w
（其中s为所使用的最小的字母的序号，t为所使用的最大的字母的序号。w为数字的位数，这3个数满足：1≤s<T< span>≤26, 2≤w≤t-s ）
第2行为具有w个小写字母的字符串，为一个符合要求的Jam数字。
所给的数据都是正确的，不必验证。
【输出文件】
输出文件counting.out 最多为5行，为紧接在输入的Jam数字后面的5个Jam数字，如果后面没有那么多Jam数字，那么有几个就输出几个。每行只输出一个Jam数字，是由w个小写字母组成的字符串，不要有多余的空格。
【输入样例】
2 10 5
bdfij
【输出样例】
bdghi
bdghj
bdgij
bdhij
befgh
参考答案：br />bdghibdghjbdgijbdhijbegih
解析：【喵呜刷题小喵解析】
根据题目描述，Jam使用小写英文字母计数，每个数字的位数都是相同的，英文字母按原先的顺序，排在前面的字母小于排在它后面的字母。题目要求输出紧接在输入的Jam数字后面的5个Jam数字。
首先，从输入文件中读取三个正整数s、t和w，分别表示所使用的最小的字母的序号、所使用的最大的字母的序号以及数字的位数。
然后，读取输入的Jam数字，记为U。
接下来，我们需要找到紧接在U后面的5个Jam数字。由于Jam数字的每个字母互不相同，而且从左到右是严格递增的，因此，我们可以按照字母的顺序，逐个增加每个字母，直到达到或超过t为止。
具体步骤如下：
1. 从U的最后一个字母开始，逐个增加每个字母，直到达到或超过t为止。
2. 如果增加后的字母超过了t，则将该字母替换为s，并将后面的字母逐个增加，直到达到或超过t为止。
3. 如果增加后的字母超过了w，则将该字母替换为s，并将后面的字母从s开始逐个增加，直到达到或超过t为止。
4. 如果增加后的字母没有超过w，则将后面的字母从当前字母的下一个字母开始逐个增加，直到达到或超过t为止。
重复以上步骤，直到找到5个Jam数字为止。
最后，将找到的5个Jam数字按顺序输出到输出文件中。如果后面没有那么多Jam数字，那么有几个就输出几个。每行只输出一个Jam数字，是由w个小写字母组成的字符串，不要有多余的空格。
根据题目给出的输入样例，我们可以得到输出样例中的结果。
4、数列
【问题描述】
给定一个正整数k(3≤k≤15),把所有k的方幂及所有有限个互不相等的k的方幂之和构成一个递增的序列，例如，当k=3时，这个序列是：
1，3，4，9，10，12，13，…
（该序列实际上就是：30，31，30+31，32，30+32，31+32，30+31+32，…）
请你求出这个序列的第N项的值（用10进制数表示）。
例如，对于k=3，N=100，正确答案应该是981。
【输入文件】
输入文件sequence.in 只有1行，为2个正整数，用一个空格隔开：
k N
（k、N的含义与上述的问题描述一致，且3≤k≤15，10≤N≤1000）。
【输出文件】
输出文件sequence.out 为计算结果，是一个正整数（在所有的测试数据中，结果均不超过2.1*109）。（整数前不要有空格和其他符号）。
【输入样例】
3 100
【输出样例】
981
参考答案：为了求解这个数列的第N项的值，我们可以使用一种基于动态规划的方法。首先，我们需要计算出k的幂次方序列，然后利用这个序列来构建递增的数列。具体步骤如下：1. 初始化一个数组dp，用于存储k的幂次方序列。dp[i]表示k的i次方的值。2. 计算k的幂次方序列：从dp[0]开始，依次计算dp[i] = dp[i-1] * k，直到dp[i]的值超过N。3. 初始化一个变量sum，用于记录当前递增数列的和。sum的初始值为0。4. 从0开始遍历dp数组，对于每个dp[i]，计算当前递增数列的和sum_i = sum + dp[i]。* 如果sum_i == N，说明第N项的值就是dp[i]。直接返回dp[i]即可。* 如果sum_i < N，说明第N项的值在dp[i]之后，继续遍历下一个dp[i+1]。* 如果sum_i > N，说明第N项的值在dp[i]之前，但已经超过了N，因此结束遍历。5. 如果遍历完整个dp数组都没有找到第N项的值，说明N超出了递增数列的范围，直接返回-1。
解析：【喵呜刷题小喵解析】：
本题要求求解一个特定的数列的第N项的值。这个数列是由k的幂次方及有限个互不相等的k的幂次方之和构成的递增序列。
首先，我们需要理解这个数列的构造规则。对于给定的k，我们可以计算出k的幂次方序列，例如当k=3时，幂次方序列为1, 3, 9, 27,...。然后，我们可以利用这个幂次方序列来构建递增的数列。
具体地，我们可以从幂次方序列的第一个数开始，依次将后面的数加到当前数列的和上，形成递增的数列。例如，当k=3时，递增数列的前几项为1, 3, 4, 9, 10, 12,...。
为了求解这个数列的第N项的值，我们可以使用一种基于动态规划的方法。首先，我们计算出k的幂次方序列，然后利用这个序列来构建递增的数列。在构建递增数列的过程中，我们记录下每个数的和，并检查这个和是否等于N。如果等于N，我们就找到了第N项的值。
最后，我们需要注意的是，当N超出了递增数列的范围时，我们应该返回-1，表示无法找到第N项的值。
喵呜刷题：让学习像火箭一样快速，快来微信扫码，体验免费刷题服务，开启你的学习加速器！
