蓝桥杯2024【第十五届省赛】Python B组竞赛信息

第三年蓝球杯，感觉题目比往年简单多了。题量合适够我这种菜鸟解答… …

大概可能有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)%n 和(i-j)%n是相等的，参考八皇后问题。

        所以可用二维哈希 [斜行][元素值]。

import sys
def main():
    input = lambda: sys.stdin.readline().strip()    # 快读
    n, m = map(int, input().split())
    maps = []
    hax0 = [[0]*1001 for i in range(1001)]  # 斜行=> '\'
    hax1 = [[0]*1001 for i in range(1001)]  # 斜行=> '/'
    for i in range(n):
        maps.append(list(map(int, input().split())))
        
        # 记录这一斜行每个元素出现次数
        for j, x in enumerate(maps[-1]):
            hax0[(i-j) % 1000][x] += 1
            hax1[(i+j) % 1000][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) % 1000][ai] > 1:
                res += hax0[(i-j) % 1000][ai] - 1
            if hax1[(i+j) % 1000][ai] > 1:
                res += hax1[(i+j) % 1000][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库，就用了两个最简单的类函数进行拼凑。然后都知道超过%1000(间隔)的时间是无效的，所以把间隔减小 （差值day-1天）

import sys
from datetime import datetime, timedelta    # 时间类、时间差值类
def main():
    input = lambda: sys.stdin.readline().strip()
    start = datetime(1970, 1, 1, 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
        
        # 超过一天的差值是无效的因为只有: 间隔*k次 + 余数,故超过1天的k是无效的
        # 所以直接把差值缩小到 第一个大于1天的间隔,满足差值时间超过1000(最大间隔时间)分钟
        diff = diff - timedelta(days=diff.days-1)
        
        # 计算差值时间的 (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

        直接二分查找,交替找第一个大于上一块石头下标就行了… …

        真简单，大无语事件因为字多不想看… …

试题 G: 缴纳过路费

时间限制: 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的乘积。

但是:

虽然我熟练掌握了各种树状数组、线段树、LCA、SCC缩点、割点和割边的求法

就是忘记了并查集如何维护size，忘记了合并的时候这个 size += size该写在哪里… …

痛失20分，我还调试了一个半小时。

以下代码是错的… … 需要自行解决并查集size的问题

import sys


def main():
    """
    注意这个代码是错的，比赛时写的，因为忘记了并查集维护size怎么写，调了一个半小时没写出...
    """
    def find(x):
        nonlocal fa, size
        if x == fa[x]:
            return x
        fa[x] = find(fa[x])
        size[fa[x]] += size[x]
        return fa[x]

    def merge(x, y):
        nonlocal fa, size
        xx, yy = find(x), find(y)
        if xx==yy:
            return False
        fa[x] = y
        size[y] += size[x]
        return True

    input = lambda: sys.stdin.readline().strip()
    n, m, l, r = map(int, input().split())
    size = [1 for i in range(n +1)]
    fa = [i for i in range(n+1)]
    edges = []
    for i in range(m):
        u, v, w = map(int, input().split())
        edges.append((w, u, v))
    ans = 0
    for w, u, v in sorted(edges):
        aa, bb = find(u), find(v)
        if l <= w <= r:
            print(size[aa], size[bb], '*****')
        temp = size[aa] * size[bb]

        if merge(u, v) and l <= w <= r:
            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分钟没思路。