第十五届蓝桥杯PythonC组题解

A题：拼正方形

问题描述

给定一定数量的 2×2 和 1×1 的方块，求能拼出的最大正方形边长。

解题思路

• 二分法：将奇数和偶数边长分开处理，通过二分法寻找最大满足条件的边长。
• 面积验证：总方块面积需大于等于目标正方形面积。

代码实现

x, y = 7385137888721, 10470245  # 样例输入值，需替换为实际输入def check(u):cnt = (u // 2) * (u // 2)cnt = min(cnt, x)return u * u <= cnt * 4 + y# 处理奇数和偶数边长
l, r = 1, int(1e18)
while l < r:mid = (l + r + 1) // 2if check(mid + mid % 2):l = midelse:r = mid - 1
res1 = l + l % 2l, r = 1, int(1e18)
while l < r:mid = (l + r + 1) // 2if check((mid + mid % 2) // 2):l = midelse:r = mid - 1
res2 = (l + l % 2) // 2print(max(res1, res2))

---

B题：最小公倍数

问题描述

求2024和1024的最小公倍数。

解题思路

• 公式法：利用 LCM(a, b) = a * b // GCD(a, b)。

代码实现

import math
a, b = 2024, 1024
print(a * b // math.gcd(a, b))  # 输出：259072

---

C题：质数数位和

问题描述

求1到1000000中，数位和为23的质数个数。

解题思路

1. 筛法求质数：埃拉托斯特尼筛法筛选质数。
2. 数位和计算：遍历质数列表，计算每个数的数位和是否为23。

代码实现

def count_primes():max_num = 10**6is_prime = [True] * (max_num + 1)is_prime[0], is_prime[1] = False, Falsefor i in range(2, int(max_num**0.5)+1):if is_prime[i]:for j in range(i*i, max_num+1, i):is_prime[j] = Falseprimes = [i for i, val in enumerate(is_prime) if val]count = 0for p in primes:if sum(map(int, str(p))) == 23:count += 1return countprint(count_primes())  # 输出：5503（模拟赛样例）

---

D题：密码锁

问题描述

通过最少操作将密码锁拨动到目标密码，每次操作可选择单个或多个连续圆环拨动到同一数字。

解题思路

• 动态规划：定义 dp[i][j] 为区间 [i,j] 的最少操作次数。
• 区间合并：根据字符相同性合并操作。

代码实现

n = int(input())
s = list(map(int, input().strip()))
a = [0] * (n + 2)
for i in range(1, n+1):a[i] = s[i-1]dp = [[0]*(n+2) for _ in range(n+2)]
for i in range(1, n+1):dp[i][i] = 1for i in range(n, 0, -1):for j in range(i+1, n+1):dp[i][j] = dp[i][j-1] + 1if a[j] == a[j-1]:dp[i][j] = min(dp[i][j], dp[i][j-1])if a[j] == a[i]:dp[i][j] = min(dp[i][j], dp[i+1][j-1] + 1)for k in range(i, j):dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j])print(dp[1][n])

---

E题：最大质因数

问题描述

求2024的最大质因数。

解题思路

• 质因数分解：从2开始试除，记录最大质因数。

代码实现

def max_prime_factor(n):max_factor = 1i = 2while i*i <= n:while n % i == 0:max_factor = in //= ii += 1return max_factor if n == 1 else nprint(max_prime_factor(2024))  # 输出：23

---

参考

• CSDN博客-蓝桥杯题解
• 洛谷题解专栏