代码收藏家 2024蓝桥杯Python B省赛第十五届78分题解
第三年蓝球杯，感觉题目比往年简单多了。题量合适够我这种菜鸟解答… …
大概可能有45分，希望进省一大三最后i一次机会了55555
进省一了耶耶耶
试题 A: 穿越时空之门（满分）
本题总分：5 分
【问题描述】
随着 2024
年的钟声回荡，传说中的时空之门再次敞开。这扇门是一条神秘
的通道，它连接着二进制和四进制两个不同的数码领域，等待着勇者们的探索。
在二进制的领域里，勇者的力量被转换成了力量数值的二进制表示中各数
位之和。
在四进制的领域里，力量的转换规则相似，变成了力量数值的四进制表示
中各数位之和。
穿越这扇时空之门的条件是严苛的：当且仅当勇者在二进制领域的力量等
同于四进制领域的力量时，他才能够成功地穿越。
国王选定了小蓝作为领路人，带领着力量值从
1
到
2024
的勇者们踏上了这
段探索未知的旅程。作为小蓝的助手，你的任务是帮助小蓝计算出，在这
2024
位勇者中，有多少人符合穿越时空之门的条件。
思路：进制转换… …
答案：63
多此一举的输出纯粹怕粗心。
def check(a):
jin_2, x2 = jin_s(a, 2)
jin_4, x4 = jin_s(a, 4)
print(a, x2, x4)
if jin_2 == jin_4:
return True
return False
def jin_s(x, m):
res = []
while x:
res.append(x%m)
x //= m
return sum(res), res
def main():
res = 0
for i in range(1, 2025):
if check(i):
res += 1
print(res, '**************')
# 63
if __name__ == '__main__':
main()试题 B: 数字串个数（满分）
本题总分：5 分
【问题描述】
小蓝想要构造出一个长度为
10000
的数字字符串，有以下要求：
1) 小蓝不喜欢数字
0
，所以数字字符串中不可以出现
0
；
2) 小蓝喜欢数字
3
和
7
，所以数字字符串中必须要有
3
和
7
这两个数字。
请问满足题意的数字字符串有多少个？这个数字会很大，你只需要输出其
对
10
9
+ 7
取余后的结果。
思路：第一反应先构造长度2-4，模拟找规律。发现DP即可
答案：157509472
def main():
n = 10000
p = int(1e9 +7)
dp = [[[0] * 2 for i in range(2)] for j in range(n+1)]
# 前缀指的是不包括当前字符串的前子串
# 状态为[当前str长度][前缀是否有3][前缀是否有7]
# 边界
dp[1][0][0] = 7 # 没有3和7,只能是除37的其它七种方案
dp[1][0][1] = 1 # 有3,一种方案
dp[1][1][0] = 1 # 有7,一种方案
dp[1][1][1] = 0 # 有3和7,不可能(长度为1不可能同时出现37)
# 枚举阶段,决策为当前i位置填什么字符
for i in range(2, n+1):
# 状态转移
dp[i][0][0] = (dp[i-1][0][0] * 7) % p # 前缀无37(当前可填7种1、2、4、5、6、8、9)
dp[i][0][1] = (dp[i-1][0][1] * 8 + dp[i-1][0][0]) % p # 从有7(可填8种)、和均没有(可填1种)
dp[i][1][0] = (dp[i-1][1][0] * 8 + dp[i-1][0][0]) % p # 从有3(可填8种)、和均没有(可填1种)
dp[i][1][1] = (dp[i-1][1][1] * 9 + dp[i-1][0][1] + dp[i-1][1][0]) % p # 从有37(可填9种)、只有3(1种)、只有7(1种)三种情况
# 答案
print(dp[n][1][1]) # 157509472
if __name__ == '__main__':
main()
试题 C: 连连看（满分）
时间限制: 10.0s
内存限制: 512.0MB
本题总分：10 分
【问题描述】
小蓝正在和朋友们玩一种新的连连看游戏。在一个 n
×
m
的矩形网格中，
每个格子中都有一个整数，第
i
行第
j
列上的整数为
A
i
,
j
。玩家需要在这个网
格中寻找一对格子
(
a
,
b
)
−
(
c
,
d
)
使得这两个格子中的整数
A
a
,
b
和
A
c
,
d
相等，且
它们的位置满足
|
a
−
c
|
=
|
b
−
d
|
>
0
。请问在这个
n
×
m
的矩形网格中有多少对
这样的格子满足条件。
对于所有评测用例，1 ≤ n, m ≤ 1000 ，1 ≤ Ai, j ≤ 1000 。
目标算法O(n^2)
思路：对于每个元素,判断对‘X’型方向上有无相同元素。
因为矩阵斜行的下标满足 (i+j)%2000和(i-j)%2000是相等的，参考八皇后问题。
所以可用二维哈希 [斜行][元素值]。
import sys
def main():
input = lambda: sys.stdin.readline().strip() # 快读
n, m = map(int, input().split())
maps = []
hax0 = [[0]*1001 for i in range(2001)] # 斜行=> '\'
hax1 = [[0]*1001 for i in range(2001)] # 斜行=> '/'
for i in range(n):
maps.append(list(map(int, input().split())))
# 记录这一斜行每个元素出现次数
for j, x in enumerate(maps[-1]):
hax0[(i-j) % 2000][x] += 1
hax1[(i+j) % 2000][x] += 1
res = 0
for i in range(n):
for j in range(m):
ai = maps[i][j]
# 因为要排除自己,所以需要大于1才行,还需要-1。
# 例如当前斜行有2个相等元素,有一个是自己,所以只能配成一对
if hax0[(i-j) % 2000][ai] > 1:
res += hax0[(i-j) % 2000][ai] - 1
if hax1[(i+j) % 2000][ai] > 1:
res += hax1[(i+j) % 2000][ai] - 1
print(res)
if __name__ == '__main__':
main()
试题 D: 神奇闹钟（满分）
时间限制: 10.0s
内存限制: 512.0MB
本题总分：10 分
【问题描述】
小蓝发现了一个神奇的闹钟，从纪元时间（1970
年
1
月
1
日
00:00:00
）开
始，每经过
x
分钟，这个闹钟便会触发一次闹铃（纪元时间也会响铃）。这引起
了小蓝的兴趣，他想要好好研究下这个闹钟。
对于给出的任意一个格式为 yyyy-MM-dd HH:mm:ss
的时间，小蓝想要
知道在这个时间点之前（包含这个时间点）的最近的一次闹铃时间是哪个时间？
注意，你不必考虑时区问题。
对于所有评测用例，1 ≤ T ≤ 10，1 ≤ x ≤ 1000，保证所有的时间格式都是
合法的。
目标复杂度应该要(9999年-1970年，以间隔迭代肯定超时，所以不能迭代)
思路：datetime库，就用了两个最简单的类函数进行拼凑。
import sys
from datetime import datetime, timedelta # 时间类、时间差值类
def main():
input = lambda: sys.stdin.readline().strip()
start = datetime(1970, 1, 1, 0, 0, 0)
for i in range(int(input())):
aa, bb, mmm = input().split()
n, y, r = map(int, aa.split('-'))
s, f, m = map(int, bb.split(':'))
# 和秒没有关系,因为从0:0:0开始,又是整数间隔分钟
# 实例化当前时间
now = datetime(n, y, r, s, f, 0)
# 到目前的差值时间
diff = now - start
# 计算差值时间的 (mod 间隔)的余数
totmins = int(diff.total_seconds())//60%int(mmm)
# 把当前时间前移 差值对间隔余多少分钟
print(str(now-timedelta(minutes=totmins)))
if __name__ == '__main__':
main()
试题 E: 蓝桥村的真相（满分）
时间限制: 10.0s
内存限制: 512.0MB
本题总分：15 分
【问题描述】
在风景如画的蓝桥村，n
名村民围坐在一张古老的圆桌旁，参与一场思想
的较量。这些村民，每一位都有着鲜明的身份：要么是誉满乡野的诚实者，要
么是无可救药的说谎者。
当会议的钟声敲响，一场关于真理与谬误的辩论随之展开。每位村民轮流
发言，编号为
i
的村民提出了这样的断言：坐在他之后的两位村民——也就是
编号
i
+ 1
和
i
+ 2
（注意，编号是环形的，所以如果
i
是最后一个，则
i
+ 1
是
第一个，以此类推）之中，一个说的是真话，而另一个说的是假话。
在所有摇曳不定的陈述中，有多少真言隐藏在谎言的面纱之后？
请你探索每一种可能的真假排列组合，并计算在所有可能的真假组合中，
说谎者的总数。
对于所有评测用例，1 ≤ T ≤ 105，3 ≤ n ≤ 1018。
目标算法需要O(T)或者O(Tlogn)
思路：刚开始没思路，先写个暴力找规律(因为数据范围2<=n<=10e18)，必须公式或者log。
然后发现，n是3的倍数答案就是n*2，不是3的倍数答案就是n本身
import sys
def check(n, xxxxx):
"""
检查该排列是否符合要求
:param n:
:param xxxxx: 用来拆分的数
:return:
"""
# 拆分二进制,枚举集合状态
lis = []
while xxxxx:
lis.append(xxxxx%2)
xxxxx //= 2
res = [0] *(n-len(lis)) + lis # 不够长的补0
# 扩大一倍,解决环的问题
lis = res * 2
for i in range(n):
if lis[i] == 1:
if lis[i+1] ^ lis[i+2] == 0:
return False, res
else:
if lis[i+1] ^ lis[i+2] == 1:
return False, res
return True, res
def sol(n):
"""
这是用来暴力找规律的
"""
ans = 0
for i in range((2**n)):
flag, lis = check(n, i)
if flag:
print(lis)
ans += lis.count(0)
print(n%3, n, ans, "***************"*5)
def main():
input = lambda: sys.stdin.readline().strip()
t = int(input())
# 用来暴力的
# for n in range(3, 22):
# sol(n)
for i in range(t):
n = int(input())
if n%3 == 0:
print(n*2)
else:
print(n)
if __name__ == '__main__':
main()
试题 F: 魔法巡游（满分）
时间限制: 10.0s
内存限制: 512.0MB
本题总分：15 分
【问题描述】
在蓝桥王国中，两位魔法使者，小蓝与小桥，肩负着维护时空秩序的使命。
他们每人分别持有
N
个符文石，这些石头被赋予了强大的力量，每一块上都刻
有一个介于
1
到
10
9
之间的数字符号。小蓝的符文石集合标记为
s
1
,
s
2
, . . . ,
s
N
，
小桥的则为
t
1
,
t
2
, . . . ,
t
N
。
两位魔法使者的任务是通过使用符文石，在各个时空结点间巡游。每次巡
游遵循这样一条法则：当小蓝使用了符文石
s
i
到达新的结点后，小桥必须选用
一个序号更大的符文石（即某个
t
j
满足
j
>
i
）前往下一个结点。同理，小桥抵
达之后，小蓝需要选择一个序号
k
>
j
的符文石
s
k
继续他们的巡游。
为了成功地穿梭时空，两个连续使用的符文石上的数字符号必须有共鸣，
这种共鸣只有当数字符号中
至少包含一个
特定的元素——星火（数字
0
）、水波
（数字
2
）或者风语（数字
4
）时，才会发生。例如，符号序列
126
,
552
,
24
,
4
中
的每对连续符文都包含了至少一个共鸣元素，则它们是一系列成功的巡游；而
如果是
15
,
51
,
5
，则不成立，因为它们之间的共鸣元素不包含星火、水波或风语
中的任意一个。
小蓝总是先启程，使用他的符文石开启巡游。
你的任务是计算这对魔法使者能够执行的最长时空巡游序列的长度。这样
的序列形式为
s
i
1
,
t
i
2
,
s
i
3
,
t
i
4
, . . .
，其中序列索引满足
i
1
<
i
2
<
i
3
<
i
4
< . . .
，并且序
列中每一对相邻的符文石都至少包含一个共鸣元素。
对于所有评测用例，1 ≤ N ≤ 105，1 ≤ si , ti ≤ 109。
目标复杂度 O(N) 或者 O(N logN)
思路：题目太多字了，没看这题
赛后补题 例如：
126 393 581 42 44
204 990 240 46 52
贪心的话直接选择第一个满足的就行了，所以难点就是快速找满足条件的第一个
两组满足条件的下标入数组
1 4 5
1 2 3 4 5
直接二分查找,交替找第一个大于上一块石头下标就行了… …
真简单，大无语事件因为字多不想看… …
import re
import bisect
def solution(A, B):
if not A: # 小蓝一个都拿不了
return 0
left = A[0] # 小蓝开始贪心拿第一个
cnt = 1 # 答案
cur_lis = B # 交替的数组，小蓝选了一个，接下来小乔选
while True:
try:
left = cur_lis[bisect.bisect(cur_lis, left)] # 不断用二分交替找第一个大于的数
cnt += 1
cur_lis = A if cur_lis is B else B
except: # 直接用异常来判断结束
return cnt
if __name__ == '__main__':
n = int(input())
# 使用re筛选含有024的符文数字
pat = re.compile('[024]')
# 把符合调节的符文下标存入待选数组
# A 为小蓝待选, B为小乔
A = [i for i, x in enumerate(input().split(), 1) if pat.search(x)]
B = [i for i, x in enumerate(input().split(), 1) if pat.search(x)]
print(solution(A, B))
试题 G: 缴纳过路费（91%分）
时间限制: 10.0s
内存限制: 512.0MB
本题总分：20 分
【问题描述】
在繁华的商业王国中，N
座城市被
M
条商路巧妙地连接在一起，形成了一
个错综复杂的无向图网络。每条商路是双向通行的，并且任意两座城市之间最
多只有一条直接的商路。每条商路都有它的规则，其中最引人注目的就是穿过
商路，需要缴纳过路费。因此，商人们在选择商路时必须格外认真。
有一位名叫小蓝的商人，他对于商路的花费有着自己独到的见解。在小蓝
眼中，一条路线包含一条或多条商路，但路线的成本并不是沿途累积的过路费
总和，而是这条路线上
最贵
的那一次收费。这个标准简单而直接，让他能迅速
评估出一条路线是否划算。
于是，他设立了一个目标，即找出所有城市对，这些城市之间的最低路线
成本介于他心中预设的两个数
L
和
R
之间。他相信，这样的路线既不会太廉
价，以至于路况糟糕；也不会过于昂贵，伤害他精打细算的荷包。
作为小蓝的助手，请你帮助小蓝统计出所有满足条件的城市对数量。
对于所有评测用例，1 ≤ N ≤ 105，1 ≤ M ≤ min(2 × 105 , N×( 2 N−1) )，1 ≤ L ≤
R ≤ 109 ,1 ≤ u, v ≤ N, u , v，1 ≤ w ≤ 109。
还是最高nlogn复杂度
思路：属实是让我给押到题了，赛前特意查缺补漏了这一篇最短路径之寻找最大边的最小值（Floyd、Dijkstra、Kruskal）_路径最大值最小-CSDN博客
所以直接kruskal，然后并查集维护连通块大小，从大到小遍历，(并查集维护不小于某边权的最大连通)。
如果通过一条边能连接两个连通块，说明这条边是两个连通块，全连接（相互到达）的最大边权，也就是最贵的一条路。所以连接前的两个连通块，都能组成一对符合条件的点对故size[u]*size[v]。
但是:
虽然我熟练掌握了各种树状数组、线段树、LCA、SCC缩点、割点和割边的求法
就是忘记了并查集如何维护size，忘记了合并的时候这个 size += size该写在哪里… …
痛失20分，我还调试了一个半小时。
以下代码只能得到91%分，原因不详
import sys
def main():
input = lambda: sys.stdin.readline().strip()
def find(x):
nonlocal fa, size
if x != fa[x]:
fa[x] = find(fa[x])
return fa[x]
def merge(x, y):
nonlocal fa, size
xx, yy = find(x), find(y)
if xx == yy:
return False
fa[xx] = yy
size[yy] += size[xx]
return True
n, m, LL, RR = map(int, input().split())
size = {i: 1 for i in range(1, n + 1)}
fa = {i: i for i in range(1, n + 1)}
edges = []
for i in range(m):
u, v, w = map(int, input().split())
# 不满足的边直接筛掉
if w > RR or w < LL:
continue
edges.append((w, u, v))
ans = 0
# 并查集维护不小于某边权的集合
# 从大到小枚举,并且去除不符合条件的边
for w, u, v in sorted(edges, reverse=True):
aa, bb = find(u), find(v)
# 记录连通前两个连通块的全连接大小
temp = size[aa] * size[bb]
# 如果是第一次连接两个集合,说明该边是两个连通块的最大连接边(最贵的路)
if merge(u, v):
ans += temp
print(ans)
if __name__ == '__main__':
main()
试题 H: 纯职业小组
时间限制
: 10.0s
内存限制
: 512.0MB
本题总分：
20
分
【问题描述】
在蓝桥王国，国王统治着一支由 n
个小队组成的强大军队。每个小队都由
相同职业的士兵组成。具体地，第
i
个小队包含了
b
i
名职业为
a
i
的士兵。
近日，国王计划在王宫广场举行一场盛大的士兵检阅仪式，以庆祝王国的
繁荣昌盛。然而，在士兵们入场的过程中，一场突如其来的风暴打乱了他们的
行列，使得不同小队的士兵混杂在一起，次序乱成一团，
尽管国王无法知道每个士兵的具体职业，但为了确保仪式能顺利进行，国
王打算从这些混乱的士兵中选出一部分，组成
k
个“纯职业小组”进行检阅。
一个“纯职业小组”定义为由
3
名同职业的士兵组成的队伍。
请问，国王至少需要选择多少名士兵，才能确保这些士兵可以组成 k
个
“纯职业小组”。
思路：没做这题… … 因为不甘于并查集size，调了一个半小时未放弃… …
读一遍题目可能是鸽巢原理，然后复杂度应该要O(n)，贪心考虑如何选能产生最多的无效人员。
写题此文章时，看了10分钟没思路。
