一、实操题
1、水下探测器
水下探测器可以潜入湖中在任意水深进行科学探索。湖水的最大深度为h米即它在湖底时到水面的距离，0<=h<=100;探测器最初的水下深度 s米，0<=s<=100;
当探测器不在水面(当前深度大于 0) 时，每个指令可使它上浮1米，而当探测器在水面时，u指令是无效的;
当探测器不在湖底(当前深度小于 h) 时，每个d指令可使它下沉 1米，而当探测器在湖底时，d指令是无效的;
在执行到无效指令时，探测器不做任何操作而继续执行下一指令。编程实现:
根据给定的 h、s和一个指令序列(由字符u、d组成的字符串，长度不超过 100)，求出执行完整的指令序列后，探测器的水下深度。
输入:
第一行:h和s，以空格分开。0<=s<=h<=100第二行:长度不超过 100的指令字符串，串中仅包含字母u或 d
输出:
代表探测器在执行指令后的水下深度的数字
样例输入:
9 1 uduudd
样例输出:
2
样例数据分析:水深9米,探测器在水下1米处
字符u代表向上1米,探测器上浮到0米处
字符d代表向下1米,探测器下沉到1米处
字符u代表向上1米,探测器上浮到0米处字符u代表向上1米探测器已经在水面,不能上浮,依然在0米处字符d代表向下1米,探测器下沉到1米处字符d代表向下1米,探测器下沉到2米处
最终结果为2
参考答案：根据给定的h、s和一个指令序列，我们可以编写一个程序来模拟探测器水下深度的变化。首先，我们需要读取输入的h和s，然后读取指令序列。对于每个指令，我们可以根据当前的深度和h的大小来确定指令是否有效，并根据指令的类型进行相应的上浮或下沉操作。最后，返回最终的深度。
解析：【喵呜刷题小喵解析】：
首先，我们需要理解题目中给出的水下探测器的行为规则。当探测器不在水面时，每个u指令可以使它上浮1米；当探测器不在湖底时，每个d指令可以使它下沉1米。当探测器在水面或湖底时，相应的指令是无效的。
根据题目要求，我们需要编写一个程序来模拟探测器水下深度的变化。程序需要读取输入的h和s，以及指令序列。然后，程序需要遍历指令序列，对于每个指令，根据当前的深度和h的大小来确定指令是否有效，并根据指令的类型进行相应的上浮或下沉操作。最后，程序返回最终的深度。
在样例数据中，水深h为9米，探测器最初的水下深度s为1米。指令序列为uduudd。首先，探测器在水下1米处，执行u指令，探测器上浮到水面，深度变为0米。然后，执行d指令，探测器下沉到1米处。接着，再次执行u指令，探测器上浮到水面，深度再次变为0米。然后，执行d指令，探测器下沉到1米处。最后，执行d指令，探测器下沉到2米处。最终结果为2，符合题目要求。
2、猫吃鱼
明明家从1号站点出发，开车去旅游，一共要经过n个站点，依次为 2、3......n。由于明明带上了心爱的小猫，在每个站点都要为小猫提供一条鱼用做美餐(包括1号站点)。除了1号站点只能吃1号站点买的鱼，其他站点既可以吃当地买的鱼，也可吃之前经过的站点买了存入车载冰箱中的鱼。
但车载冰箱消耗的电能来自汽油，所以每条鱼用冰箱保存到下一站的费用与各个站点的汽油价格有关为使问题简化，我们约定:
(1)车从某站开出时油箱中都是此站点刚加的汽油
(2)车载冰箱能容纳一路上需要的所有鱼。
即:每条鱼的费用既包括购买时的费用，也包括用冰箱保存鱼的费用。
编程实现:
为了降低小猫吃鱼的总代价，明明预先上网查到了这n个站点的鱼价和汽油价格。并据此算出每个站点买一条鱼的费用以及从该站点到下一站用冰箱保存一条鱼的费用。你能帮明明算出这一路上小猫吃鱼的最小总费用吗?
输入:
第一行: 站点数n，1<n<100
接下来的n行:每行两个以空格分隔的正整数，表示:这一站买一条鱼的费用，以及从这一站把每条鱼保存到下一站的费用，两个费用均为小于 10000 的正整数
输出:
最小总费用，是一个正整数
样例输入:
5 63 71 32 83 95
样例输出
29
样例数据分析:
第一行数据5代表一共5站
第二行数据63代表本站购买鱼6元,运费3元,第一站必须一定先购买一条 总花费6元
第三行数据71代表本站购买鱼7元,运费1元,从上一站最小花费+运费9元大于本站购买的费用7,所以选择从本站购买鱼总花费 6+7=13元
第四行数据32代表本站购买鱼3元,运费2元,从上一站最小花费+运费8元大于本站购买的费用3,所以选择从本站购买鱼,总花费 6+7+3=16元
第五行数据83代表本站购买鱼8元,运费3元从上一站最小花费+运费5元,小于本站购买的费用8,所以选择从上站花费加上本站运费总花费6+7+3+5=21元
第六行数据95代表本站购买鱼9元 运费5元,从上一站最小花费+运费8元,小于本站购买的费用9,所以选择从上一站花费加上本站运费总花费6+7+3+5+8=29元
最终总花费为29元
参考答案：这是一个动态规划的问题。首先，我们创建一个大小为n+1的一维数组dp，dp[i]表示小猫在到达第i个站点时，吃到鱼的最小总费用。然后，我们遍历每个站点，对于每个站点i，我们有两种选择：1. 在当前站点i买鱼，那么费用就是dp[i-1] + cost[i] + fee[i]，其中dp[i-1]表示到达上一个站点时吃到鱼的最小总费用，cost[i]表示在当前站点买鱼的费用，fee[i]表示将鱼保存到下一站的费用。2. 在之前的某个站点j（j 解析：【喵呜刷题小喵解析】： 3、评选最佳品牌 n个评委投票，在m个商品中评选一个最佳品牌。 评选采用多轮淘汰制，即:每轮投票，淘汰掉得票最少的候选品牌(得票并列最少的品牌一起淘汰)。 如此一轮轮淘汰下去，如果最后只剩下一个品牌当选，即告评选成功。 但如果在某轮投票中，当时未被淘汰的所有候选品牌(大于等于两个品牌)都并列得票最少，即告评选失败。 如果评选成功就输出当选品牌号。否则输出最后一轮评选时唯一选票数的相反数。 在评选流程中，每个评委的态度都可用一个序列来表示，例如当m=5 时，某评委的评选态度序列为: 3、5、1、2、4则表示该评委: 优先投3号，当3 号被淘汰时投5号，当3和5都被淘汰时投 1，当3、5、1都被淘汰时投 2，仅剩 4 号时才投 4 号品牌的票。 选票的序列中可以表示弃权，用0来表示，例如当 m=5 时，某评委的评选态度序列为: 3、5、0，则表示该评委:优先投3号，当3号被淘汰时投5号，其它情况下不投任何品牌的票编程实现: 请你编一个程序，模拟各轮投票的过程，得到评选结果 输入: 第一行: m(0<m<10,表示参加评选的品牌数)和 N(1n<1000,表示参加投票的评委数)，之间以空格分隔接下来的n行: 每行都是长度不超 m 的数字字符串，每个字符串表示一个评委的评选态度。 输出: 评选结果。 样例1输入: 样例1输出: 样例2输入: 样例2输出: 样例数据分析 样例1: 第一行3 4代表3个品牌,4个评委 第一轮投票,3个评委优先选择1号品牌,1个评委选择2号品牌,品牌3得票最少,淘汰掉 第二轮投票3个评委优先选择1号品牌,1个评委选择2号品牌,品牌2得票最少,淘汰掉,淘汰2号品牌后,只剩一个1号品牌,1号品牌胜出 最终结果1 样例2: 第一行34代表3个品牌4个评委 第一轮投票,2个评委选择2号品牌,两个评委选择3号品牌,1号得票最少,淘汰掉 第二轮投票,2个评委选择2号品牌,两个评委选择3号品牌,由于只剩下两个品牌,且并列最少,都是2票代表评选失败需要输出最后一轮票数2的相反数-2 最终结果-2 参考答案：```pythonm, n = map(int, input().split())votes = []for _ in range(n):votes.append(list(map(int, input().split())))while m > 1:counts = [0] * (m + 1)for vote in votes:counts[vote[0]] += 1min_votes = min(counts[1:])for i in range(1, m + 1):if counts[i] == min_votes:counts[i] = -1m = counts.index(-1)print(m)``` 解析：【喵呜刷题小喵解析】： 4、最大购物优惠 小惠听说超市正在打折促销，要制订一个得到最大优惠的购物计划。 小惠的体力可以提起 w 单位重量的东西，还有一个能装V个单位体积的购物袋，并详细了解了各打折商品的重量、体积及此商品实际优惠的金额。她想在自己体力的限度和购物袋容积限度内，尽可能多地得到购物优惠。 超市规定这些打折商品每种只能购买一件。 编程实现: 请你编写程序，制定一个购买商品的计划，求出小惠能得到的最大优惠金额和实际应购买的各商品序号。 输入: 第一行:依次为w、v和n(n为商品种类数)，所有数值均为不超过100的正整数 接下来的 n 行:每行有三个整数，依次为某种商品的重量、体积和让利金额，数值间以空格分开，所有数值均为不超过100的正整数 输出: 第一行:小惠能够得到的最大让利金额 第二行:依次为从小到大排列的商品序号，序号从1开始，序号间用空格分开。若第二行输出的序列不唯一，则输出其最小字典序。 样例输入: 样例输出: 样例数据分析: 第一行数据1094代表最多能提起重量10购物袋体积9,4种商品 第二行数据代表第1件商品重量8体积3,让利金额4 第三行数据代表第2件商品重量5,体积4,让利金额5 第四行数据代表第3件商品重量3,体积7,让利金额7 第五行数据代表第4件商品重量4体积5让利金额4 创建一个三维数组 yh[n+1][w+1][v+1] 记录在第n个物品,w重量,v体积时 最优策略2 只考虑一个物品的时候(纵向代表重量,横向代表体积,数据代表最大优惠) 考虑前两个物品的时候 考虑前三个物品的时候 考虑前四个物品的时候 最终结果,最大优惠为9.同时需要额外记录在在不同商品数量,不同重量和体积的情况下,如何购买商品 参考答案：```#include 解析：【喵呜刷题小喵解析】： 5、蓝桥杯赛迷宫 把一个n行m 列的字符阵列看做一个迷宫，迷宫仅包含L、Q、B、S中的大写字母(蓝桥杯赛的汉语拼音首字母)。 初始时，你可以从任意一个“L"字母开始，移向相邻的“Q"字母，然后从此“Q"字母出发，移向相邻的“B字母，然后从此“B”字母出发，移向相邻的“S”字母......。这样，你就算是走过了一个“LQBS”字符序列。接下来，仍然可以从此“S”字母出发，移向相邻的“L”字母.......重复上述的动作，你就可以不断地走过“LQBS”序列。 请注意，所谓相邻仅包含上、下、左、右4个方向，且只能从L->Q，从Q->B，从B->S，从S-L.可以想像，由于选择的出发点不同，我们有可能在迷宫中走过无数次的“LQBS”，或者是有限次的LQBS” 或者一次也走不了 编程实现: 请你编写程序，求出在给定的迷宫中，我们最多可以走过多少次“LQBS”? 输入: 第一行:正整数n,m，表示迷宫的规模为n行m列，0<m<100，0<n<100 接下来的n行:每行 m个符合题意的字母，字母间无空格 输出: 一个整数。即:如果在迷宫中可以无限次的走过“LQBS”，输出-1，否则，输出可以走过“LQBS”的最多次数。 样例1输入: 样例1输出: 样例2输入: 样例2输出: 样例3输入: 样例3输出: 样例数据分析: 样例1: 第一行数据33代表是3行3列的迷宫 第1步,寻找L LSB QBQ BSL 第2步在L的上下左右寻找Q LSB QBQ BSL 第3步在Q的上下左右寻找B LsB QBQ BSL 第4步在B的上下左右寻找S LSB QBQ BSL 如此当重复到10次的时候,仍可以继续走,代表进入无限循环 因为3行3列最多9个格子,能走10步就代表一定进入无限循环 输出-1 样例2: 第一行数据44代表是4行4列的迷宫 第1步,寻找起点L BLQB BBQS SBQL QQQQ 第2步在L的上下左右寻找Q BLQB BBQS SBQL QQQQ 第3步在Q的上下左右寻找B BLQB BBQS SBQL QQQQ 第4步在B的上下左右寻找S BLQB BBQS SBQL QQQQ 第5步在S的上下左右寻找L BLQB BBQS SBQL QQQQ 第6步在L的上下左右寻找Q BLQB BBQS SBQL QQQQ 第7步在Q的上下左右寻找B BLQB BBQS SBQL QQQQ 第8步在B的上下左右寻找S BLQB BBQS SBQL QQQQ 第9步在S的上下左右寻找L 因为找不到L了,则代表迷宫走到尽头,一共走了8步,LQBS一共4个字符,所以走了8/4=2共计2次LQBS,输出2 参考答案：输入迷宫的规模n和m，然后遍历迷宫，找到起始点L，再寻找相邻的Q，接着寻找相邻的B，最后寻找相邻的S。每走一次LQBS，计数器加1。当找不到起始点L时，结束遍历，输出计数器的值。如果计数器值无限大（比如大于迷宫中格子数的4倍），则输出-1表示可以无限次走过LQBS。 解析：【喵呜刷题小喵解析】： 喵呜刷题：让学习像火箭一样快速，快来微信扫码，体验免费刷题服务，开启你的学习加速器！
这个问题是一个典型的动态规划问题，可以使用动态规划的方法来解决。动态规划是一种将问题分解为多个子问题，通过求解子问题的最优解来得到原问题的最优解的方法。在这个问题中，我们可以将问题分解为n个子问题，每个子问题表示小猫到达第i个站点时，吃到鱼的最小总费用。
首先，我们创建一个大小为n+1的一维数组dp，dp[i]表示小猫在到达第i个站点时，吃到鱼的最小总费用。然后，我们遍历每个站点，对于每个站点i，我们有两种选择：在当前站点i买鱼，或者在之前的某个站点j（j
具体实现时，我们可以使用一个循环来遍历每个站点，对于每个站点i，我们再使用一个循环来遍历之前的每个站点j（j
在这个问题中，我们需要注意一个问题，就是每个站点的鱼价和汽油价格不同，因此我们不能直接将买鱼的费用和保存到下一站的费用相加得到总费用。我们需要将买鱼的费用和保存到下一站的费用分别存储在一个数组中，然后在进行选择时，根据这两个数组计算出总费用。
此外，由于这是一个动态规划的问题，我们需要将子问题的解保存下来，以便在求解子问题时使用。我们可以使用一个一维数组dp来保存子问题的解，dp[i]表示小猫在到达第i个站点时，吃到鱼的最小总费用。在求解子问题时，我们可以直接使用这个数组来得到子问题的解，而不需要重新计算。3 4
123
213
132
1 0
1
3 4
321
213
231
312
-2
这个问题是一个模拟投票过程的问题，我们需要模拟多轮投票，直到评选出最佳品牌或者评选失败。
首先，我们读入品牌数 m 和评委数 n，然后读入每个评委的投票序列。
在每一轮投票中，我们需要统计每个品牌的得票数，找出得票最少的品牌，将其淘汰。如果所有未被淘汰的品牌得票数相同，那么评选失败，输出最后一轮得票数的相反数。
我们可以使用一个长度为 m+1 的数组 counts 来记录每个品牌的得票数，初始时所有品牌的得票数都为 0。然后遍历每个评委的投票序列，将对应品牌的得票数加 1。
然后，我们找出得票最少的品牌，将其得票数设为 -1，表示已经被淘汰。同时，我们将变量 m 更新为被淘汰品牌的编号，这样在下一轮投票中可以直接淘汰掉该品牌。
最后，如果 m 大于 1，表示还有多个品牌存在，我们可以进行下一轮投票；否则，输出变量 m 的值，表示评选结果。如果 m 的值为正数，表示评选成功，当选品牌为 m；如果 m 的值为负数，表示评选失败，最后一轮得票数的相反数为 -m。10 9 4
8 3 6
5 4 5
3 7 7
4 5 4
9
2 4
此题可以使用动态规划的方法来解决。定义dp[i][j][k]为考虑到前i个商品，且当前重量为j，体积为k时，所能获得的最大优惠金额。flag[i][j][k]记录的是dp[i][j][k]对应的商品序号。
首先，对于每个商品，我们遍历所有可能的重量和体积，如果当前商品的重量和体积小于等于当前考虑的重量和体积，且购买当前商品后，所获得的最大优惠金额大于之前考虑的最大优惠金额，则更新dp和flag。
然后，从最后一个商品开始，根据flag的值，将对应的商品序号加入到答案中，并更新当前重量和体积。最后，按照从小到大的顺序输出答案。
需要注意的是，在动态规划的过程中，需要逆向遍历商品，即先遍历到最后一个商品，因为一旦选择了某个商品，就不能再选择它之前的商品了。另外，对于dp和flag的初始化，可以使用memset函数将其初始化为0。
上述代码的时间复杂度为O(n^3)，其中n为商品种类数。1 2
L Q
0
3 3
LSB
QBQ
BSL
-1
4 4
BLQB
BBQS
SBQL
QQQQ
2
这道题目要求我们计算在给定的迷宫中最多可以走过多少次LQBS序列。首先，我们需要理解题目中的规则：只能从L到Q，从Q到B，从B到S，从S到L。我们需要找到起始点L，然后按照规则遍历迷宫，每走一次LQBS，计数器加1。当找不到起始点L时，遍历结束，输出计数器的值。如果计数器值无限大（比如大于迷宫中格子数的4倍），则输出-1表示可以无限次走过LQBS。
具体实现时，我们可以使用深度优先搜索（DFS）或广度优先搜索（BFS）来遍历迷宫。由于题目中迷宫的规模较小（n和m都不超过100），使用DFS或BFS都可以得到正确答案。在遍历过程中，我们需要记录当前的位置和已经走过的LQBS序列的次数，当找不到起始点L时，结束遍历，输出计数器的值。
需要注意的是，由于题目中迷宫的规模较小，我们可以使用暴力枚举的方法来解决这个问题。具体来说，我们可以遍历迷宫中的每个格子，找到起始点L，然后按照规则遍历迷宫，计算可以走过的LQBS序列的次数。如果无法遍历完整个迷宫，说明可以无限次走过LQBS序列，输出-1。
对于更大的迷宫，我们需要使用更高效的算法来解决问题。我们可以使用图论的知识来建立迷宫的模型，然后使用图论算法来遍历迷宫。例如，我们可以使用深度优先搜索或广度优先搜索来遍历迷宫，使用拓扑排序或最短路径算法来找到可以走过的LQBS序列的次数。这些算法需要更深入的图论知识和算法设计技巧，但可以有效地解决更大的迷宫问题。
