在线编程题目之小试牛刀
熟悉基本的python语法刷题指南，助我一臂之力！
题目1: 字符串解密
题目描述
按照题目要求，从字符串开始位置依次切割长度为1,2,3…10,1,2,3…的子串。当剩余字符串长度不足当前需要切割的长度时，停止切割。
解题思路
从字符串开始位置依次切割长度为1,2,3…10,1,2,3…的子串，当剩余字符串长度不足当前需要切割的长度时，停止切割。
代码实现
def solve():# 读取输入的01字符串s = input().strip()# 存储切割结果result = []count = 0# 当前需要切割的长度，从1开始，到10后回到1cut_len = 1# 当字符串不为空且长度足够时继续切割while s:# 如果剩余长度不足当前需要切割的长度，停止切割if len(s) < cut_len:break# 切割指定长度的字符串cut_part = s[:cut_len]# 更新剩余字符串s = s[cut_len:]# 添加到结果列表result.append(cut_part)count += 1# 更新下次切割长度，到10后回到1cut_len = cut_len % 10 + 1# 输出结果print(count)for part in result:print(part)if __name__ == "__main__":solve()
题目2: 二进制截取
题目描述
给定一个二进制字符串，按照指定长度k截取所有可能的子串，并将每个子串转换为十进制数输出。
解题思路
遍历所有可能的起始位置，截取长度为k的子串，然后转换为十进制数输出。
代码实现
def solve():# 读取二进制字符串binary = input().strip()# 读取截取长度k = int(input().strip())# 存储结果results = []# 遍历所有可能的起始位置for i in range(len(binary) - k + 1):# 截取长度为k的子串substring = binary[i:i+k]# 转换为十进制数decimal_value = int(substring, 2)results.append(decimal_value)# 输出结果for result in results:print(result)if __name__ == "__main__":solve()
题目3: 最大极差和
题目描述
使用动态规划解决。dp[i][j]表示前i个元素分成j个子数组能得到的最大极差和。极差是子数组中最大值与最小值的差。
解题思路
使用动态规划方法，状态转移方程：dp[i][j] = max(dp[k][j-1] + range(k+1, i)) for all valid k，其中range(k+1, i)表示从索引k+1到i的子数组的极差。
代码实现
def solve():# 读取数组长度n = int(input().strip())# 读取数组元素arr = list(map(int, input().strip().split()))# 读取需要划分的子数组个数m = int(input().strip())# dp[i][j]表示前i个元素分成j个子数组的最大极差和# 初始化为负无穷，确保取不到无效状态dp = [[-float('inf')] * (m + 1) for _ in range(n + 1)]# 前0个元素分成0组极差和为0dp[0][0] = 0# 动态规划填表for i in range(1, n + 1):# 注意j的范围不能超过i和m的最小值for j in range(1, min(i, m) + 1):# 枚举第j个子数组的起始位置kfor k in range(j - 1, i):# 计算第j个子数组[k, i-1]的极差subarray = arr[k:i]range_value = max(subarray) - min(subarray)# 状态转移dp[i][j] = max(dp[i][j], dp[k][j-1] + range_value)# 输出结果print(dp[n][m])if __name__ == "__main__":solve()
题目4: 位置变换
题目描述
对数组进行k次遍历，第m次遍历时比较相邻元素模m的大小。如果arr[i] % m > arr[i+1] % m，则交换两元素位置。
解题思路
执行k次遍历，每次遍历时比较相邻元素模当前次数的大小，如果前一个元素模当前次数的值大于后一个元素模当前次数的值，则交换两个元素。
代码实现
def solve():# 读取数组长度n = int(input().strip())# 读取数组元素arr = list(map(int, input().strip().split()))# 读取遍历次数k = int(input().strip())# 执行k次遍历for m in range(1, k + 1):# 每次遍历都从头开始检查相邻元素i = 0while i < len(arr) - 1:# 如果前一个元素模m的值大于后一个元素模m的值，则交换if arr[i] % m > arr[i+1] % m:arr[i], arr[i+1] = arr[i+1], arr[i]i += 1# 输出结果print(' '.join(map(str, arr)))if __name__ == "__main__":solve()
题目5: 池化操作
题目描述
对二维数组不断进行池化操作，直到只剩一个元素。池化操作: 用2×2的窗口扫描数组，池化结果是窗口中第二大的数。由于n=2^k，每次池化后数组大小减半，最终会得到一个数。
解题思路
不断进行池化操作直到矩阵大小为1×1。池化操作是用2×2的窗口扫描数组，池化结果是窗口中第二大的数。
代码实现
def solve():# 读取矩阵大小n = int(input().strip())# 读取矩阵元素matrix = []for _ in range(n):row = list(map(int, input().strip().split()))matrix.append(row)# 不断进行池化操作直到矩阵大小为1×1while n > 1:# 创建新矩阵存储池化结果new_matrix = []# 以步长2遍历原矩阵for i in range(0, n, 2):new_row = []for j in range(0, n, 2):# 获取2×2窗口的四个值values = [matrix[i][j], matrix[i][j+1],matrix[i+1][j], matrix[i+1][j+1]]# 排序后取第二大的值（第二大值在排序后的索引为2，但因为是降序所以是索引1）values.sort(reverse=True)new_row.append(values[1]) # 第二大的值new_matrix.append(new_row)# 更新矩阵和大小matrix = new_matrixn //= 2# 输出最终结果print(matrix[0][0])if __name__ == "__main__":solve()
题目6: 小红的魔法
题目描述
根据牛客网链接的题目，这是一个关于魔法值的问题。通常这类问题涉及异或运算的性质。假设输入为n和一个长度为n的数组，计算数组中所有元素的异或和。
解题思路
计算数组中所有元素的异或和。
代码实现
def solve():# 读取数组长度n = int(input().strip())# 读取数组元素arr = list(map(int, input().strip().split()))# 计算魔法值（这里假设魔法值为数组中所有元素的异或和）magic_value = 0for num in arr:magic_value ^= num# 输出结果print(magic_value)if __name__ == "__main__":solve()
题目7: 最小购物花费
题目描述
使用贪心策略。为了使总花费最小，应该让价格高的商品使用折扣大的优惠。
解题思路
使用贪心策略。为了使总花费最小，应该让价格高的商品使用折扣大的优惠。具体做法：
- 将商品按价格从高到低排序
- 将折扣按从低到高排序（折扣越小越优惠）
- 价格最高的商品使用最优惠的折扣，以此类推
代码实现
def solve():# 读取商品数量n = int(input().strip())# 读取商品价格数组prices = list(map(int, input().strip().split()))# 读取折扣数组discounts = list(map(float, input().strip().split()))# 贪心策略: 价格高的商品用折扣大的优惠# 将商品按价格降序排列的索引price_indices = sorted(range(n), key=lambda i: prices[i], reverse=True)# 将折扣按升序排列的索引（折扣越小越优惠）discount_indices = sorted(range(n), key=lambda i: discounts[i])# 计算总花费total_cost = 0for i in range(n):# 价格最高的商品使用最优惠的折扣price_idx = price_indices[i]discount_idx = discount_indices[i]total_cost += prices[price_idx] * discounts[discount_idx]# 输出结果，保留三位小数print("{:.3f}".format(total_cost))if __name__ == "__main__":solve()
题目8: 横向棋盘移动
题目描述
模拟棋子在横向棋盘上的移动过程。棋盘编号1-2019，每次操作指定棋子向前移动一步，但如果前方有其他棋子则不能移动。需要模拟指定次数的操作后，输出指定棋子的位置。
解题思路
模拟棋子在横向棋盘上的移动过程。使用集合加快前方位置检查。
代码实现
def solve():# 读取棋子个数n = int(input().strip())# 读取棋子初始位置数组positions = list(map(int, input().strip().split()))# 使用集合加快前方位置检查position_set = set(positions)# 读取操作次数op_count = int(input().strip())# 读取要操作的棋子编号(从1开始)piece_id = int(input().strip())# 获取当前棋子位置current_pos = positions[piece_id - 1] # 棋子编号从1开始# 模拟棋子移动for _ in range(op_count):# 检查前方是否有棋子if (current_pos + 1) not in position_set:# 如果可以移动，则向前移动一步position_set.remove(current_pos)current_pos += 1position_set.add(current_pos)# 更新positions数组positions[piece_id - 1] = current_pos# 输出最终位置print(current_pos)if __name__ == "__main__":solve()
题目9: 学生分组
题目描述
使用动态规划解决分组问题。三种分组方式：三人组（要求成绩最大和最小差值<10）、二人组（要求成绩最大和最小差值<20）、一人组（没有要求）。
解题思路
使用动态规划解决分组问题。dp[i]表示前i个学生的最小分组数。状态转移方程：
- dp[i] = min(dp[i], dp[i-1] + 1) # 一人组
- dp[i] = min(dp[i], dp[i-2] + 1) # 二人组(如果满足条件)
- dp[i] = min(dp[i], dp[i-3] + 1) # 三人组(如果满足条件)
代码实现
def solve():# 读取学生数量n = int(input().strip())# 读取学生成绩scores = list(map(int, input().strip().split()))# 对成绩进行排序，便于判断分组条件scores.sort()# dp[i]表示前i个学生的最小分组数dp = [float('inf')] * (n + 1)# 前0个学生需要0组dp[0] = 0# 动态规划填表for i in range(1, n + 1):# 尝试一人组dp[i] = min(dp[i], dp[i-1] + 1)# 尝试二人组(需要满足成绩差值<20)if i >= 2 and scores[i-1] - scores[i-2] < 20:dp[i] = min(dp[i], dp[i-2] + 1)# 尝试三人组(需要满足成绩差值<10)if i >= 3 and scores[i-1] - scores[i-3] < 10:dp[i] = min(dp[i], dp[i-3] + 1)# 输出最小分组数print(dp[n])if __name__ == "__main__":solve()
题目10: 敏感词统计
题目描述
统计文章中所有敏感词出现的总次数。对于每个敏感词，在文章中查找其出现的所有位置并计数。使用字符串的find方法，从不同起始位置查找匹配。
解题思路
统计文章中所有敏感词出现的总次数。对于每个敏感词，在文章中查找其出现的所有位置并计数。使用字符串的find方法，从不同起始位置查找匹配。
代码实现
def solve():# 读取文章内容article = input().strip()# 读取敏感词数量n = int(input().strip())# 读取敏感词列表sensitive_words = []for _ in range(n):sensitive_words.append(input().strip())# 统计敏感词出现次数total_count = 0for word in sensitive_words:# 使用字符串查找统计出现次数start = 0while True:# 从start位置开始查找wordpos = article.find(word, start)if pos == -1:# 没有找到更多匹配break# 找到一个匹配，计数加1total_count += 1# 从下一个位置继续查找（允许重叠匹配）start = pos + 1# 输出结果print(total_count)if __name__ == "__main__":solve()
题目11: 二进制位置函数
题目描述
函数f(n)表示n的二进制表示中最右边的1所在位置代表的数值。例如: f(12) = f(1100) = 4，因为最右边的1在第3位(从右往左，从0开始计数)，值为2^2=4。可以使用位运算技巧: n & (-n) 可以直接得到最右边的1所代表的数值。
解题思路
使用位运算技巧: n & (-n) 可以直接得到最右边的1所代表的数值。
代码实现
def solve():# 读取nn = int(input().strip())# 计算f(i)/i的和total_sum = 0for i in range(1, n + 1):# 计算f(i): 找到i的二进制表示中最后一个1所在位置的值# 使用位运算技巧 n & (-n) 获取最后一个1的位置值f_i = i & -i # 这个运算可以直接得到最右边的1所代表的数值total_sum += f_i / i# 输出结果，保留6位小数print("{:.6f}".format(total_sum))if __name__ == "__main__":solve()
题目12: 最大表达式
题目描述
给定一个由数字和+、-组成的表达式，删除其中一个字符使表达式结果最大。注意: 如果删除字符后数字的首位为0，需要自动去除。
解题思路
枚举删除每个字符的情况，计算表达式值，取最大值。
代码实现
def solve():# 读取表达式expr = input().strip()# 初始化最大值和对应表达式max_value = float('-inf')max_expr = ""# 尝试删除每个字符for i in range(len(expr)):# 删除第i个字符new_expr = expr[:i] + expr[i+1:]# 处理首位为0的情况（但要保留单独的"0"）j = 0# 当首位是0且后面还有数字且下一位不是运算符时，跳过前导0while (j < len(new_expr) and new_expr[j] == '0' and j + 1 < len(new_expr) and new_expr[j+1] not in '+-'):j += 1# 如果全是0，则结果为"0"，否则去除前导0new_expr = new_expr[j:] if j < len(new_expr) else "0"# 特殊情况处理：如果去除前导0后为空，则为"0"if not new_expr:new_expr = "0"# 计算表达式的值try:value = eval(new_expr)if value > max_value:max_value = valuemax_expr = new_exprexcept:# 如果表达式无效则跳过continue# 输出结果print(max_expr)if __name__ == "__main__":solve()
题目13: 质数计数
题目描述
给定一个由数字组成的字符串，可以在相邻数字间添加加号形成表达式，求所有可能的表达式中质数数量的最大值。
解题思路
使用回溯法枚举所有可能的加号插入方式，对每种方式计算质数数量。
代码实现
def is_prime(n):"""判断一个数是否为质数"""if n <= 1:return Falseif n <= 3:return Trueif n % 2 == 0 or n % 3 == 0:return Falsei = 5while i * i <= n:if n % i == 0 or n % (i + 2) == 0:return Falsei += 6return Truedef solve():# 读取数字字符串digits = input().strip()n = len(digits)# 使用回溯法计算可能的加号插入方式中质数的最大数量def backtrack(start, current_num, prime_count):"""回溯函数start: 当前处理的位置current_num: 当前正在构建的数字prime_count: 当前已找到的质数数量"""# 如果处理完所有数字if start == n:return prime_countmax_count = prime_count# 尝试从当前位置开始构建不同长度的数字for end in range(start + 1, n + 1):# 构建数字num_str = digits[start:end]# 避免前导零（除非是单独的"0"）if len(num_str) > 1 and num_str[0] == '0':continuenum = int(num_str)# 递归处理剩余部分count = backtrack(end, 0, prime_count + (1 if is_prime(num) else 0))max_count = max(max_count, count)return max_count# 输出结果result = backtrack(0, 0, 0)print(result)if __name__ == "__main__":solve()
题目14: 小红的红色印章
题目描述
用2×2的印章盖章，要求印章之间不相邻、不对角。
解题思路
- 找出所有2×2的印章位置（即2×2区域内都是1的位置）
- 检查任意两个印章之间是否满足不相邻、不对角的要求
- 相邻：两个印章的中心距离为1或2
- 对角：两个印章的中心距离为sqrt(2)或sqrt(8)
- 满足要求：两个印章中心距离大于sqrt(8)
代码实现
def solve():"""题目14: 小红的红色印章解题思路:用2×2的印章盖章，要求印章之间不相邻、不对角。方法:1. 找出所有2×2的印章位置（即2×2区域内都是1的位置）2. 检查任意两个印章之间是否满足不相邻、不对角的要求- 相邻：两个印章的中心距离为1或2- 对角：两个印章的中心距离为sqrt(2)或sqrt(8)- 满足要求：两个印章中心距离大于sqrt(8)"""# 读取图案大小n, m = map(int, input().strip().split())# 读取图案pattern = []for _ in range(n):row = input().strip()pattern.append(row)# 找出所有2×2的印章位置（存储左上角坐标）stamp_positions = []for i in range(n - 1):for j in range(m - 1):# 检查2×2区域是否都是印章（标记为1）if (pattern[i][j] == '1' and pattern[i][j+1] == '1' andpattern[i+1][j] == '1' and pattern[i+1][j+1] == '1'):stamp_positions.append((i, j))# 检查印章之间是否符合要求（不相邻、不对角）valid = Truefor i in range(len(stamp_positions)):for j in range(i + 1, len(stamp_positions)):r1, c1 = stamp_positions[i]r2, c2 = stamp_positions[j]# 计算两个印章中心的距离# 印章中心在左上角坐标右下角一位的位置，即(r+0.5, c+0.5)# 但我们只需要比较相对距离，可以使用整数坐标(r+1, c+1)# 为了方便计算，我们比较左上角坐标，此时要求距离大于2dr = abs(r1 - r2)dc = abs(c1 - c2)# 如果两个印章在横向或纵向距离不超过2，且纵向或横向距离不超过2# 则说明它们相邻或对角，不符合要求if dr <= 2 and dc <= 2:# 但对角线分开的印章（如(0,0)和(2,2)）是符合要求的if not (dr == 2 and dc == 2):valid = Falsebreakif not valid:break# 输出结果print("Yes" if valid else "No")if __name__ == "__main__":solve()