第十三届蓝桥杯国赛PythonA题解

A 斐波那契与7

简要题意：求斐波那契数列的第1至202202011200项中，有多少项的个位是7。

解题思路：

• 直接暴力计算所有项不可行，因为数据量过大。
• 通过打表观察发现个位数每300项会出现循环规律。
• 预先计算循环周期内个位为7的项数（40个），然后计算完整周期数和剩余项数。

代码实现：

a = [14, 16, 17, 23, 34, 37, 43, 56, 74, 76, 77, 83, 94, 97,103, 116, 134, 136, 137, 143, 154, 157, 163, 176, 194, 196, 197,203, 214, 217, 223, 236, 254, 256, 257, 263, 274, 277, 283, 296]ans = 202202011200 // 300 * 40
mo = 202202011200 % 300
for x in a:if mo >= x:ans += 1else:break
print(ans)

B 火柴棒数字

简要题意：用300根火柴棒拼出最大的整数。

解题思路：

• 要使数字最大，首先位数要尽可能多。
• 统计各数字的火柴消耗，优先使用消耗少的数字（1消耗最少，但0不能作为前导）。
• 发现可以正好用9,7,5,4,3,2,1各10个拼出最大数字。

代码实现：

print(9999999999777777777755555555554444444444333333333322222222221111111111)

C 取模

简要题意：给定n,m，判断是否存在不同的x,y满足1≤x<y≤m且n mod x = n mod y。

解题思路：

• 使用鸽巢原理，若n mod i必须等于i-1才能避免重复。
• 这个条件非常严格，实际只需检查前几项即可快速判断。

代码实现：

t = int(input())
for _ in range(t):n, m = map(int, input().split())f = 0for i in range(1, m + 1):if n % i != i - 1:print("Yes")f = 1breakif not f:print("No")

D 最大公约数

简要题意：求满足gcd(x,y)=k的数对个数。

解题思路：

• 使用莫比乌斯反演来高效计算区间内的合法数对。
• 预处理莫比乌斯函数，然后通过分块计算加速。

代码实现：

import sys
import mathdef preprocess_mobius(max_n):max_n += 1is_prime = [True] * max_nis_prime[0] = is_prime[1] = Falsemu = [1] * max_nfor i in range(2, max_n):if is_prime[i]:for j in range(i, max_n, i):is_prime[j] = (j == i)mu[j] *= -1j = i * ifor k in range(j, max_n, j):mu[k] = 0return mumax_num = 5 * 10**4
mu = preprocess_mobius(max_num)
prefix_mu = [0] * (max_num + 1)
for i in range(1, max_num + 1):prefix_mu[i] = prefix_mu[i-1] + mu[i]def compute_f(a, b):min_val = min(a, b)res = 0i = 1while i <= min_val:q_a = a // iq_b = b // inext_i = min(a // q_a + 1, b // q_b + 1) if (q_a !=0 and q_b !=0) else min_val + 1next_i = min(next_i, min_val + 1)res += (prefix_mu[next_i - 1] - prefix_mu[i - 1]) * q_a * q_bi = next_ireturn resn = int(sys.stdin.readline())
for _ in range(n):a, b, c, d, k = map(int, sys.stdin.readline().split())a = (a - 1) // kb = b // kc = (c - 1) // kd = d // ktotal = compute_f(b, d) - compute_f(a, d) - compute_f(b, c) + compute_f(a, c)print(total)

E 数组个数

简要题意：构造满足特定条件的数组方案数。

解题思路：

• 枚举前两个数，然后动态规划计算后续数的可能情况。
• 检查每个位置的约束条件并累加合法方案。

代码实现：

mod = 1000000007
n = int(input())
a = list(map(int, input().split()))def check(x, y):res = 0dp = {}dp[(x, y)] = 1for h in range(2, n):new_dp = {}for i, j in dp:for k in range(11):if max(i, j, k) == a[h-1]:new_dp[(j, k)] = new_dp.get((j, k), 0) + dp[(i, j)]new_dp[(j, k)] %= moddp = new_dpfor i, j in dp:if max(i, j, x) == a[-1] and max(x, y, j) == a[0]:res += dp[(i, j)]res %= modreturn resans = 0
for x in range(11):for y in range(11):ans = (ans + check(x, y)) % mod
print(ans)

F 六六大顺

简要题意：计算特定数列的和。

解题思路：

• 发现数列有数学规律，可通过公式直接计算。
• 使用快速幂优化大数运算。

代码实现：

n = int(input())
ans = 4 * (pow(100, n + 1) - 22 * pow(10, n + 1) + 120 + 99 * n)
print(ans // 891)

G 环境治理

简要题意：通过调整道路灰尘使总灰尘达标的最小天数。

解题思路：

• 二分答案结合Floyd算法计算最短路径。
• 检查中间结果是否满足约束条件。

代码实现：

from copy import deepcopy
n, q = map(int, input().split())
d = [[0] * (n + 2) for _ in range(n + 2)]
low = [[0] * (n + 2) for _ in range(n + 2)]for i in range(1, n + 1):td = list(map(int, input().split()))for j in range(1, n + 1):d[i][j] = td[j - 1]for i in range(1, n + 1):td = list(map(int, input().split()))for j in range(1, n + 1):low[i][j] = td[j - 1]def floyd(dist):for k in range(1, n + 1):for i in range(1, n + 1):for j in range(1, n + 1):if dist[i][k] + dist[k][j] < dist[i][j]:dist[i][j] = dist[i][k] + dist[k][j]ans = 0for i in range(1, n + 1):for j in range(1, n + 1):ans += dist[i][j]return ansdef check(x):cd = deepcopy(d)for i in range(1, n + 1):tmp = x // n + (1 if x % n >= i else 0)for j in range(1, n + 1):cd[i][j] = max(cd[i][j] - tmp, low[i][j])cd[j][i] = max(cd[j][i] - tmp, low[j][i])res = floyd(cd)return res <= ql, r = 0, (1 << 32) + 5
while l + 1 < r:mid = l + r >> 1if check(mid):r = midelse:l = mid
print(r if r != (1 << 32) + 5 else -1)

H 宝石收集

简要题意：强连通分量相关题目（待补充详细思路）

I 图书借阅

简要题意：优先队列贪心问题（待补充详细思路）

J 替换字符

简要题意：高效处理字符串的区间字符替换。

解题思路：

• 使用字典记录每个字符的位置索引。
• 通过二分查找快速定位需要修改的区间。
• 批量更新字符位置信息。

代码实现：

import string
import bisects = list(input())
mp = {i: [] for i in string.ascii_lowercase}
for idx in range(len(s)):mp[s[idx]].append(idx)m = int(input())
for _ in range(m):l, r, x, y = input().split()l, r = map(int, [l, r])mp[x].sort()x_l = bisect.bisect_left(mp[x], l - 1)x_r = bisect.bisect_right(mp[x], r - 1)mp[y].extend(mp[x][x_l:x_r])for idx in mp[x][x_l:x_r]:s[idx] = ydel mp[x][x_l:x_r]print("".join(s))