蓝桥杯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 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 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