蓝桥杯2024【第十五届省赛】Python B （78分题解）_蓝桥杯python第十五届

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()

时间限制: 10.0s

内存限制: 512.0MB

本题总分：10 分

【问题描述】

        小蓝发现了一个神奇的闹钟，从纪元时间（1970 年 1 月 1 日 00:00:00 ）开

始，每经过 x 分钟，这个闹钟便会触发一次闹铃（纪元时间也会响铃）。这引起

了小蓝的兴趣，他想要好好研究下这个闹钟。

        对于给出的任意一个格式为 yyyy-MM-dd HH:mm:ss 的时间，小蓝想要

知道在这个时间点之前（包含这个时间点）的最近的一次闹铃时间是哪个时间？

注意，你不必考虑时区问题。

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: 蓝桥村的真相（满分）

思路：刚开始没思路，先写个暴力找规律(因为数据范围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: 魔法巡游（满分）

思路：题目太多字了，没看这题

        赛后补题 例如：

        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%分）

思路：属实是让我给押到题了，赛前特意查缺补漏了这一篇最短路径之寻找最大边的最小值（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: 纯职业小组

思路：没做这题... ... 因为不甘于并查集size，调了一个半小时未放弃... ...