第十四届蓝桥杯国赛PythonA题解
A 跑步计划
题意简述：小蓝计划在某天的日期或星期中出现数字"1"时跑5千米，否则只跑1千米。计算2023年全年跑步的总距离。
解题思路：使用Python的datetime模块遍历2023年的每一天，检查日期或星期中是否包含"1"。
代码：
print(1333)
B 残缺的数字
题意简述：给定一个有缺失数字的数，每个缺失位可能是0-9中的任意数字，问所有可能情况的数目。
解题思路：统计每个缺失位置的可能性数量，使用乘法原理计算总数。
代码：
print(254016000)
C 整数变换
题意简述：每分钟数字会变为当前数字减去其各位数字之和，直到变为0，求变换次数。
解题思路：直接模拟变换过程，直到数字变为0。
代码：
n = int(input())
ans = 0
while n != 0:tot = sum(int(ch) for ch in str(n))n -= totans += 1
print(ans)
D 2023
题意简述：构造特定条件的数字串，使用容斥原理计算。
解题思路：使用二进制反演处理容斥问题，预处理阶乘和逆元。
代码：
import mathN, maxn = 10**5+5, 10**5
fact, inv = [1]*N, [1]*N
mod = 998244353def init():for i in range(1, maxn+1):fact[i] = fact[i-1] * i % modinv[maxn] = pow(fact[maxn], mod-2, mod)for i in range(maxn-1, 0, -1):inv[i] = inv[i+1] * (i+1) % moddef comb(n, m):if n < m:return 0return fact[n] * inv[m] % mod * inv[n-m] % modinit()
n, m = map(int, input().split())
k = n // 4
ans = 0
for i in range(m, k+1):ans = (ans + (-1)**(i-m) * comb(i, m) % mod * comb(n-3*i, i) % mod * pow(10, n-4*i, mod) % mod) % mod
print(ans)
E 火车运输
题意简述：将物品装入两个容量分别为a和b的火车，求能装载的最大总量。
解题思路：二维动态规划，状态表示当前两火车装载量。
代码：
n, a, b = map(int, input().split())
w = list(map(int, input().split()))
dp = [[0]*1005 for _ in range(1005)]
for weight in w:for j in range(a, -1, -1):for k in range(b, -1, -1):if j >= weight:dp[j][k] = max(dp[j][k], dp[j-weight][k] + weight)if k >= weight:dp[j][k] = max(dp[j][k], dp[j][k-weight] + weight)
print(dp[a][b])
F 走方格
题意简述：在n×n网格中从左上角到右下角，求最短步数。
解题思路：BFS搜索最短路，考虑常规移动和特殊移动规则。
代码：
from collections import dequen = int(input())
mp = [list(map(int, input().split())) for _ in range(n)]
vis = [[0]*n for _ in range(n)]
q = deque([(0, 0, 0)])
vis[0][0] = 1while q:x, y, t = q.popleft()if x == n-1 and y == n-1:print(t)break# 常规移动if x+1 < n and not vis[x+1][y]:vis[x+1][y] = 1q.append((x+1, y, t+1))if y+1 < n and not vis[x][y+1]:vis[x][y+1] = 1q.append((x, y+1, t+1))# 特殊移动for i in range(y+1, n):if mp[x][i] < mp[x][i-1] and not vis[x][i]:vis[x][i] = 1q.append((x, i, t+1))else:breakfor i in range(y-1, -1, -1):if mp[x][i] < mp[x][i+1] and not vis[x][i]:vis[x][i] = 1q.append((x, i, t+1))else:break
G 等腰三角形
题意简述：分类讨论几何问题。
解题思路：待补充。
H 彩色二叉树
题意简述：在完全二叉树上进行染色操作和查询操作。
解题思路：利用完全二叉树性质，可以快速求出两点距离,然后由于染色具有覆盖性,故从后往前处理染色操作。
n, q = map(int, input().split())
history = []def distance(a, b):cnt = 0while a != b:if a > b:a = a // 2else:b = b // 2cnt += 1return cntdef query(node):for i in range(len(history)-1, -1, -1):x, y, z = history[i]if distance(node, x) <= y:return zreturn 0for _ in range(q):cmd = list(map(int, input().split()))if cmd[0] == 1:history.append((cmd[1], cmd[2], cmd[3]))else:print(query(cmd[1]))
I 选段排序
题意简述：通过排序子数组使特定位置的差值最大化。
解题思路：使用堆维护区间极值，考虑左右扩展的影响。
代码：
import heapqn, p, q = map(int, input().split())
a = [0] + list(map(int, input().split()))
res = 0# 处理初始区间[p,q]
max_heap = []
min_heap = []
for i in range(p, q+1):heapq.heappush(max_heap, -a[i])heapq.heappush(min_heap, a[i])current_max = -max_heap[0]
current_min = min_heap[0]
res = max(res, current_max - current_min)# 向右扩展
for i in range(q+1, n+1):current_min = min(current_min, a[i])heapq.heappush(max_heap, -a[i])heapq.heappop(max_heap)current_max = -max_heap[0]res = max(res, current_max - current_min)# 向左扩展
max_heap = [-a[i] for i in range(p, q+1)]
heapq.heapify(max_heap)
current_max = -max_heap[0]
current_min = min_heap[0]for i in range(p-1, 0, -1):current_max = max(current_max, a[i])heapq.heappush(min_heap, a[i])heapq.heappop(min_heap)current_min = min_heap[0]res = max(res, current_max - current_min)print(res)
J 最长同类子串
题意简述：找两个字符串的最长子串，使得字符出现位置同类。
解题思路：字符串哈希（示例为30%暴力解法）。
代码：
s, t = input(), input()
n, m = len(s), len(t)def check(k):for i in range(n-k+1):for j in range(m-k+1):pattern1 = [[] for _ in range(26)]pattern2 = [[] for _ in range(26)]for l in range(k):pattern1[ord(s[i+l])-ord('a')].append(l)pattern2[ord(t[j+l])-ord('a')].append(l)if sorted(pattern1) == sorted(pattern2):return Truereturn Falseleft, right = 0, min(n, m)
while left < right:mid = (left + right + 1) // 2if check(mid):left = midelse:right = mid - 1
print(left)