第十四届蓝桥杯大赛软件组国赛 Python大学A组 个人暴力题解

Powered by:NEFU AB-IN

！！！博主个人的暴力题解，基本很少是正解，求轻喷
！！！代码是赛后凭着印象复原的，可能会有记错的

国赛 Python大学A组 个人暴力题解

• A

  • 思路

    调日期库，模拟

  • 代码

    from sys import setrecursionlimit, stdin, stdout, exit
    from collections import Counter, deque
    from heapq import heapify, heappop, heappush, nlargest, nsmallest
    from bisect import bisect_left, bisect_right
    from datetime import datetime, timedelta
    from string import ascii_lowercase, ascii_uppercase
    from math import log, ceil, gcd, sqrt, fabs
    
    
    class sa:
        def __init__(self, x , y):
            self.x = x
            self.y = y
        def __lt__(self, a):
            return self.x < a.x
            
    
    
    N = int(2e5 + 10)
    M = 20
    INF = int(2e9)
    
    setrecursionlimit(INF)
    input = lambda: stdin.readline().rstrip("\r\n")
    read = lambda: map(int, input().split())
    LTN = lambda x: ord(x.upper()) - 65
    NTL = lambda x: ascii_uppercase[x]
    AR = lambda x: [x] * N
    
    # _____________________________________________________
    
    def check(st):
        if str(st.year).count("1") or str(st.month).count("1") or str(st.day).count("1") or str(st.weekday() + 1).count("1"):
            return True
        else:
            return False
    
    
    st = datetime(year=2023, month=1, day=1)
    ans = 0
    while st.year == 2023:
        # print(st.date())
        if check(st):
            ans += 5
        else:
            ans += 1
        st = st + timedelta(days=1)
        
    
    print(ans)
    

• B

  • 思路

    模拟

  • 代码

    from sys import setrecursionlimit, stdin, stdout, exit
    from collections import Counter, deque
    from heapq import heapify, heappop, heappush, nlargest, nsmallest
    from bisect import bisect_left, bisect_right
    from datetime import datetime, timedelta
    from string import ascii_lowercase, ascii_uppercase
    from math import log, ceil, gcd, sqrt, fabs
    
    
    class sa:
        def __init__(self, x , y):
            self.x = x
            self.y = y
        def __lt__(self, a):
            return self.x < a.x
            
    
    
    N = int(2e5 + 10)
    M = 20
    INF = int(2e9)
    
    setrecursionlimit(INF)
    input = lambda: stdin.readline().rstrip("\r\n")
    read = lambda: map(int, input().split())
    LTN = lambda x: ord(x.upper()) - 65
    NTL = lambda x: ascii_uppercase[x]
    AR = lambda x: [x] * N
    
    # _____________________________________________________
    
    
    d = Counter(
        {
            0: "1111110",
            1: "0110000",
            2: "1101101",
            3: "1111001",
            4: "0110011",
            5: "1011011",
            6: "1011111",
            7: "1110000",
            8: "1111111",
            9: "1111011"
        }
    )
    
    ans = [
        "0000011",
        "1001011",
        "0000001",
        "0100001",
        "0101011",
        "0110110",
        "1111111",
        "0010110",
        "0101001",
        "0010110",
        "1011100",
        "0100110",
        "1010000",
        "0010011",
        "0001111",
        "0101101",
        "0110101",
        "1101010",
    ]
    
    res = 1
    for i in range(len(ans)):
        cnt = 0
        for j in range(10):
            s, t = ans[i], d[j]
            flag = 1
            for k in range(len(s)):
                if s[k] == '1' and t[k] == '0':
                    flag = 0
                    break
            cnt += flag
        res *= cnt
    print(res)
    
    

• C

  • 思路

    模拟

  • 代码

    from sys import setrecursionlimit, stdin, stdout, exit
    from collections import Counter, deque
    from heapq import heapify, heappop, heappush, nlargest, nsmallest
    from bisect import bisect_left, bisect_right
    from datetime import datetime, timedelta
    from string import ascii_lowercase, ascii_uppercase
    from math import log, ceil, gcd, sqrt, fabs
    
    
    class sa:
        def __init__(self, x , y):
            self.x = x
            self.y = y
        def __lt__(self, a):
            return self.x < a.x
            
    
    
    N = int(2e5 + 10)
    M = 20
    INF = int(2e9)
    
    read = lambda: map(int, input().split())
    LTN = lambda x: ord(x.upper()) - 65
    NTL = lambda x: ascii_uppercase[x]
    AR = lambda x: [x] * N
    
    # _____________________________________________________
    
    
    
    n, = read()
    
    def f(x):
        ans = 0
        x = str(x)
        for i in x:
            ans += int(i)
        return ans
    
    ans = 0
    while n:
        n -= f(n)
        ans += 1
    
    print(ans)
    
    

• D

  • 思路

    排列组合 + 逆元

  • 代码

    from sys import setrecursionlimit, stdin, stdout, exit
    from collections import Counter, deque
    from heapq import heapify, heappop, heappush, nlargest, nsmallest
    from bisect import bisect_left, bisect_right
    from datetime import datetime, timedelta
    from string import ascii_lowercase, ascii_uppercase
    from math import log, ceil, gcd, sqrt, fabs
    
    
    class sa:
        def __init__(self, x , y):
            self.x = x
            self.y = y
        def __lt__(self, a):
            return self.x < a.x
            
    
    
    N = int(1e5 + 10)
    M = 20
    INF = int(2e9)
    
    read = lambda: map(int, input().split())
    LTN = lambda x: ord(x.upper()) - 65
    NTL = lambda x: ascii_uppercase[x]
    AR = lambda x: [x] * N
    
    # _____________________________________________________
    
    MOD = 998244353
    fact = AR(0)
    
    def init():
        fact[0] = 1
        for i in range(1, N):
            fact[i] = fact[i - 1] * i % MOD
        
    init()
    n, m = read()
    
    a = n - 3 * m
    b = m
    
    fz = fact[a]
    fm = pow(fact[a - b] * fact[b] % MOD, MOD - 2, MOD)
    
    print(fz * fm * 10 % MOD)
    
    
    

• E

  • 思路

    01背包
    我写的不是正解，会有贪心的感觉

  • 代码

    from sys import setrecursionlimit, stdin, stdout, exit
    from collections import Counter, deque
    from heapq import heapify, heappop, heappush, nlargest, nsmallest
    from bisect import bisect_left, bisect_right
    from datetime import datetime, timedelta
    from string import ascii_lowercase, ascii_uppercase
    from math import log, ceil, gcd, sqrt, fabs
    
    
    class sa:
        def __init__(self, x , y):
            self.x = x
            self.y = y
        def __lt__(self, a):
            return self.x < a.x
            
    
    
    N = int(5e3 + 10)
    M = 20
    INF = int(2e9)
    
    read = lambda: map(int, input().split())
    LTN = lambda x: ord(x.upper()) - 65
    NTL = lambda x: ascii_uppercase[x]
    AR = lambda x: [x] * N
    
    # _____________________________________________________
    
    w = AR(0)
    n, a, b = read()
    w[1:] = read()
    
    def init(a, b):
        w1, dpa, dpb, st = AR(0), AR(0), AR(0), AR(0)
        dp = [[] for _ in range(N)] 
    
        for i in range(1, n + 1):
            for j in range(a, w[i] - 1, -1):
                if dpa[j - w[i]] + w[i] > dpa[j]:
                    dpa[j] = dpa[j - w[i]] + w[i]
                    dp[j] = dp[j - w[i]][:]
                    dp[j].append(i)
    
        for i in dp[a]:
            st[i] = 1
    
    
        for i in range(1, n + 1):
            if st[i] == 0:
                w1[i] = w[i]
    
        for i in range(1, n + 1):
            for j in range(b, w1[i] - 1, -1):
                if dpb[j - w1[i]] + w1[i] > dpb[j]:
                    dpb[j] = dpb[j - w1[i]] + w1[i]
    
        return dpa[a] + dpb[b]
    
    
    # ____先a后b
    # ____先b后a
    print(max(init(a, b), init(b, a)))
    
    

• F

  • 思路

    DP + BFS

  • 代码

    from sys import setrecursionlimit, stdin, stdout, exit
    from collections import Counter, deque
    from heapq import heapify, heappop, heappush, nlargest, nsmallest
    from bisect import bisect_left, bisect_right
    from datetime import datetime, timedelta
    from string import ascii_lowercase, ascii_uppercase
    from math import log, ceil, gcd, sqrt, fabs
    
    
    class sa:
        def __init__(self, x , y):
            self.x = x
            self.y = y
            
    
    
    N = int(1010)
    M = 20
    INF = int(2e9)
    
    read = lambda: map(int, input().split())
    LTN = lambda x: ord(x.upper()) - 65
    NTL = lambda x: ascii_uppercase[x]
    AR = lambda x: [x] * N
    
    # _____________________________________________________
    
    g = [AR(0) for _ in range(N)]
    n, = read()
    
    for i in range(1, n + 1):
        g[i][1:] = read()
    
    
    # 首先求每一行的每个点的可递增最长序列的长度，0代表走不动，1代表可走一格
    # 首先求往右的
    
    dpr, dpl = [AR(0) for _ in range(N)], [AR(0) for _ in range(N)]
    for i in range(1, n + 1):
        for j in range(n - 1, 0, -1):
            if g[i][j] < g[i][j + 1]:
                dpr[i][j] = dpr[i][j + 1] + 1
            else:
                dpr[i][j] = 0
    
        for j in range(1, n + 1):
            if g[i][j] < g[i][j - 1]:
                dpl[i][j] = dpl[i][j - 1] + 1
            else:
                dpl[i][j] = 0
    
    dist = [AR(INF) for _ in range(N)]
    q = deque()
    
    dx = [1, 0]
    dy = [0, 1]
    
    def bfs():
        dist[1][1] = 0
        q.appendleft(sa(1, 1))
        while len(q):
            point = q.pop()
            x, y = point.x, point.y
    
            for i in range(2):
                x1 = x + dx[i]
                y1 = y + dy[i]
                if x1 < 1 or x1 > n or y1 < 1 or y1 > n:
                    continue
                if dist[x1][y1] > dist[x][y] + 1:
                    dist[x1][y1] = dist[x][y] + 1
                    if x1 == n and y1 == n:
                        return dist[x1][y1]
                    q.appendleft(sa(x1, y1))
            
            l, r = dpl[x][y], dpr[x][y]
            if l != 0: 
                for i in range(1, l + 1):
                    x1, y1 = x, y - i
                    if x1 < 1 or x1 > n or y1 < 1 or y1 > n:
                        continue
                    if dist[x1][y1] > dist[x][y] + 1:
                        dist[x1][y1] = dist[x][y] + 1
                        if x1 == n and y1 == n:
                            return dist[x1][y1]
                        q.appendleft(sa(x1, y1))
            if r != 0:
                for i in range(1, r + 1):
                    x1, y1 = x, y + i
                    if x1 < 1 or x1 > n or y1 < 1 or y1 > n:
                        continue
                    if dist[x1][y1] > dist[x][y] + 1:
                        dist[x1][y1] = dist[x][y] + 1
                        if x1 == n and y1 == n:
                            return dist[x1][y1]
                        q.appendleft(sa(x1, y1))
        return dist[n][n]
    
    print(bfs())
    

• G

  • 思路

    至今没搞懂题意，是一个数只能取一次，还是一个数能取三次，如果能取三次，那么样例就不对，如果只能取一次，n给的范围能取到1，索性直接暴力了

  • 代码

    from sys import setrecursionlimit, stdin, stdout, exit
    from collections import Counter, deque
    from heapq import heapify, heappop, heappush, nlargest, nsmallest
    from bisect import bisect_left, bisect_right
    from datetime import datetime, timedelta
    from string import ascii_lowercase, ascii_uppercase
    from math import log, ceil, gcd, sqrt, fabs
    
    
    class sa:
        def __init__(self, x , y):
            self.x = x
            self.y = y
        def __lt__(self, a):
            return self.x < a.x
            
    
    
    N = int(2e5 + 10)
    M = 20
    INF = int(2e9)
    
    read = lambda: map(int, input().split())
    LTN = lambda x: ord(x.upper()) - 65
    NTL = lambda x: ascii_uppercase[x]
    AR = lambda x: [x] * N
    
    # _____________________________________________________
    
    
    # 得出结论 这个数列只有两种数字 只有aab abb两种组合 
    # aab 满足 2 * a > b
    # abb 满足 2 * b > a
    
    # 问题转化为 将数组中的数字转换为a, b 代价最小 
    # 思路 二分a 找b
    
    # 暴力版本
    
    a = AR(0)
    n, = read()
    a[1:] = read()
    
    ans = INF
    
    def check(p, q):
        # p为双边
        cnt = 0
        for i in range(1, n + 1):
            cnt += min(abs(a[i] - p), abs(a[i] - q))
        return cnt
    
    
    l, r = min(a[1:]), max(a[1:])
    
    for i in range(l, r + 1): # i双边
        for j in range(l, r + 1):
            if 2 * i > j and 2 * j > i:
                ans = min(ans, check(i, j))
    
    
    print(ans)
    

• H

  • 思路

    不是特别会
    BFS + dijkstra

  • 代码

    from sys import setrecursionlimit, stdin, stdout, exit
    from collections import Counter, deque
    from heapq import heapify, heappop, heappush, nlargest, nsmallest
    from bisect import bisect_left, bisect_right
    from datetime import datetime, timedelta
    from string import ascii_lowercase, ascii_uppercase
    from math import log, ceil, gcd, sqrt, fabs
    
    
    class sa:
        def __init__(self, x, y):
            self.x = x
            self.y = y
    
        def __lt__(self, a):
            return self.x < a.x
    
    
    N = int(1e6 + 10)
    M = 20
    INF = int(2e9)
    
    read = lambda: map(int, input().split())
    LTN = lambda x: ord(x.upper()) - 65
    NTL = lambda x: ascii_uppercase[x]
    AR = lambda x: [x] * N
    
    # _____________________________________________________
    
    g = [[] for _ in range(N)]
    gg = [[] for _ in range(N)]
    
    n, q = read()
    color = AR(0)
    
    
    def f(x, y, z):
        dist = AR(INF)
        dist[x] = 0
        st = AR(0)
        q = []
        heappush(q, [0, x])
        while q:
            t = heappop(q)
            v, dst = t[0], t[1]
            if st[x]:
                continue
            st[x] = 1
            for [v, w] in gg[x]:
                if dist[v] > dist[x] + w:
                    dist[v] = dist[x] + w
                    heappush(q, [v, dist[v]])
    
        for i in range(1, n + 1):
            if dist[i] <= y:
                color[i] = z
    
    
    for i in range(1, n // 2 + 1):
        g[i].append([i * 2, 1])
        g[i].append([i * 2 + 1, 1])
        g[i * 2].append([i, 1])
        g[i * 2 + 1].append([i, 1])
    
    
    def bfs(i, j):
        st = AR(0)
        st[i] = 1
        q = deque()
        q.appendleft([i, 0])
        while len(q):
            t = q.pop()
            u, dst = t[0], t[1]
            for [v, w] in g[u]:
                if st[v] == 0:
                    q.appendleft([v, dst + w])
                    st[v] = 1
                    if v == j:
                        return dst + w
    
    
    for i in range(1, n + 1):
        for j in range(i + 1, n + 1):
            if i == j:
                gg[i].append([i, 0])
                continue
            ans = bfs(i, j)
            gg[i].append([j, ans])
            gg[j].append([i, ans])
    
    lst = AR(0)
    for i in range(q):
        lst = list(read())
        if len(lst) == 4:
            x, y, z = lst[1], lst[2], lst[3]
            f(x, y, z)
        else:
            print(color[lst[1]])
    '''
    6 6
    1 1 1 1
    2 3
    1 5 2 2
    2 4
    2 1
    2 3
    '''
    
    

• I

  • 思路

    不会
    直接暴力

  • 代码

    from sys import setrecursionlimit, stdin, stdout, exit
    from collections import Counter, deque
    from heapq import heapify, heappop, heappush, nlargest, nsmallest
    from bisect import bisect_left, bisect_right
    from datetime import datetime, timedelta
    from string import ascii_lowercase, ascii_uppercase
    from math import log, ceil, gcd, sqrt, fabs
    
    
    class sa:
        def __init__(self, x , y):
            self.x = x
            self.y = y
        def __lt__(self, a):
            return self.x < a.x
            
    
    
    N = int(2e5 + 10)
    M = 20
    INF = int(2e9)
    
    read = lambda: map(int, input().split())
    LTN = lambda x: ord(x.upper()) - 65
    NTL = lambda x: ascii_uppercase[x]
    AR = lambda x: [x] * N
    
    # _____________________________________________________
    
    a = AR(0)
    n, p, q = read()
    a[1:] = read()
    
    ans = abs(a[p] - a[q])
    
    for i in range(1, n + 1):
        for j in range(i + 1, n + 1):
            if i > p and j < q:
                continue
    
            b = sorted(a[i : j + 1])
            an = a[:i] + b + a[j+1 :]
            ans = max(ans, abs(an[p] - an[q]))
    print(ans)