第十五届蓝桥杯国赛 Python B组 解题报告

A

Solution

dfs 枚举所有题目的选择情况。状态数一共为 $2^{10}$。答案为 $31$。

B

Solution

对 $2024!$ 进行质因数分解，并求出每个质因数在 $2024!$ 中的指数。对于质因数 $p_i$，在 $2024!$ 中的指数为 $x_i$，它作为 $n$ 中的因数时，指数可以为 $0\sim \lfloor \frac{x_i}{61} \rfloor$ 中的整数。根据乘法原理，本题答案为

$\prod\limits_{i} (\lfloor \frac{x_i}{61} \rfloor+1).$

Code

if __name__ == '__main__':
    tot = [0] * 3030
    ans = 1
    for i in range(2, 2025):
        num = i
        for j in range(2, i + 1):
            while num % j == 0:
                tot[j] += 1
                num //= j
    for i in range(2, 2025):
        ans *= (tot[i] // 61 + 1)
    print(ans)

C

Solution

球员的球衣号码为他到队长的距离。故他拥有过的最大球衣号码为与他距离最远的队长的距离。对所有队长的位置排序，考虑最左和最右的两个队长即可。

Code

if __name__ == '__main__':
    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    minn, maxn = min(a), max(a)
    for i in range(1, n + 1):
        print(max(maxn - i, i - minn), end=' ')

D

Solution

二分答案裸题。

Code

def check(k):
    res = 0
    for i in range(n):
        res += a[i] // k
        if a[i] % k == 0:
            res -= 1
    return (res <= m)

if __name__ == '__main__':
    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    l, r, ans = 1, 10 ** 9, 0
    while l <= r:
        mid = l + r >> 1
        if check(mid):
            ans = mid
            r = mid - 1
        else:
            l = mid + 1
    print(ans)

E

Solution

根据两点坐标之差的奇偶性，容易 $O(1)$ 判断两点是否可以通过走田相互到达并算出所需步数。一个显然的结论是：能走田的情况下一定比走日更快到达目标。

考虑 bfs，若不能只走田到达终点，则由日的八个方向继续搜索。

否则，直接计算出多少步田可以到达终点，并终止搜索。

Code

ans = 1e9

def bfs1():
    global ans
    q = [(0, 0)] * 100010
    vis = [[-1] * 55 for _ in range(105)]
    head = tail = 1
    q[head] = (x1, y1)
    vis[x1][y1] = 0
    while head <= tail:
        (x, y) = q[head]
        head += 1
        if (vis[x][y] > ans):
            return
        d1, d2 = abs(x - x2), abs(y - y2)
        if not (d1 & 1) and not (d2 & 1) and (d1 // 2 & 1) == (d2 // 2 & 1):
            ans = min(ans, max(d1, d2) // 2 + vis[x][y])
        if x == x2 and y == y2:
            ans = vis[x][y]
            return
        for i in range(8):
            nx, ny = x + dx[i], y + dy[i]
            if nx < 0 or nx > n or ny < 0 or ny > n or vis[nx][ny] != -1:
                continue
            tail += 1
            q[tail] = (nx, ny)
            vis[nx][ny] = vis[x][y] + 1
    

if __name__ == '__main__':
    n, x1, y1, x2, y2 = map(int, input().split())
    dx = [1, 1, -1, -1, 2, 2, -2, -2]
    dy = [2, -2, 2, -2, 1, -1, 1, -1]
    bfs1()
    print(ans if ans != 1e9 else -1)

F

Solution

开两个大小为 $26n$ 的数组 $A,B$，分别记录每种字母的数量的前缀和，与包含某数量的某字母的括号数量。

先计算 $A$ 数组。

用栈模拟括号匹配的过程，当括号匹配成功时，利用 $A$ 数组和括号的左右坐标更新 $B$ 数组。

最后对 $B$ 数组作后缀和处理，即可 $O(1)$ 回答询问。

时间复杂度 $O(26|S|)$。

Code

if __name__ == '__main__':
    s = input()
    alpha_tot = [0] * 30
    n = len(s)

    for i in range(n):
        if ord('a') <= ord(s[i]) <= ord('z'):
            alpha_tot[ord(s[i]) - ord('a')] += 1
    maxn = max(alpha_tot)

    tot = [[0] * (n + 1) for _ in range(26)]
    ans = [[0] * (maxn + 1) for _ in range(26)]
    st = []

    for i in range(n):
        if ord('a') <= ord(s[i]) <= ord('z'):
            tot[ord(s[i]) - ord('a')][i] += 1

    for i in range(26):
        for j in range(1, n):
            tot[i][j] += tot[i][j - 1]

    for i in range(n):
        if s[i] == '(':
            st.append(i)
        elif s[i] == ')':
            for j in range(26):
                ans[j][tot[j][i] - tot[j][st[-1]]] += 1
            st.pop()
    
    for i in range(26):
        for j in range(maxn - 1, -1, -1):
            ans[i][j] += ans[i][j + 1]
    
    q = int(input())
    for i in range(q):
        x, y = input().split()
        y = int(y)
        if y > maxn:
            print(0)
        else:
            print(ans[ord(x) - ord('a')][y])

G

Solution

题目转化为求使得 d\frac{10^k-1}{9}\equiv0\pmod{n} 的最小 $k,d$。其中 $k$ 为正整数，$d$ 为整数 $1\sim 9$。

经过移项得 10^k\equiv1\pmod{m}，其中 $m=\frac{9n}{(n,d)}$

由欧拉定理，10^{\phi(m)}\equiv1\pmod{m}。$\phi$ 为欧拉函数。故答案对应的 $k$ 为 $\phi(m)$ 的因数。通过试除法可找出所求 $k$。

算法实现为从枚举 $d$ 入手，找出固定 $d$ 情况下的最小 $k$，并更新答案。

关于 $\phi(m)$ 的算法，设 $m=\prod\limits_ip_i^{e_i}$ 为 $m$ 的质因数分解，则

$\phi(m)=\prod\limits_i(p_i-1)p_i^{e_i-1}$

Code

import math

def factor(n):
    fac = {}
    while n % 2 == 0:
        fac[2] = fac.get(2, 0) + 1
        n //= 2
    i = 3
    while i * i <= n:
        while n % i == 0:
            fac[i] = fac.get(i, 0) + 1
            n //= i
        i += 2
    if n > 1:
        fac[n] = fac.get(n, 0) + 1
    return fac

def phi(fac):
    res = 1
    for p, exp in fac.items():
        res *= (p - 1) * (p ** (exp - 1))
    return res

if __name__ == '__main__':
    MOD = 998244353
    n = int(input())
    ans_k = ans_d = None
    for d in range(1, 10):
        m = 9 * n // math.gcd(d, n)
        if m % 2 == 0 or m % 5 == 0:
            continue
        m_fac = factor(m)
        m_phi = phi(m_fac)
        phi_fac = factor(m_phi)
        
        for p in phi_fac:
            while m_phi % p == 0:
                if pow(10, m_phi // p, m) == 1:
                    m_phi //= p
                else:
                    break
        
        if pow(10, m_phi, m) != 1:
            continue
        
        if ans_k == None or ans_k > m_phi or (ans_k == m_phi and ans_d > d):
            ans_k, ans_d = m_phi, d
    
    if ans_k == None:
        print(-1)
    else:
        ans = ((pow(10, ans_k, MOD) - 1 + MOD) % MOD * pow(9, MOD - 2, MOD) + MOD) % MOD * ans_d % MOD
        print(ans)

H

Solution

设 $A_i$ 为原始数组，$B^k_i$ 为经过 $k$ 次变换后的第 $i$ 位。

观察得出，所有 $B_i^k$ 均可表示为 $S$ 和 $A_i$ 的线性组合。其中 $S=\sum\limits^n\limits_{i=1}A_i$。故设

$B_i^k=\alpha_kS+\beta_kA_i$

又

$\begin{aligned} B_i^{k+1} &= \sum_{j=i}^{n} B_j^k - B_j^k \\ &= \sum_{j=1}^{n} (\alpha_k S + \beta_k A_j) - \alpha_k S - \beta_k A_i \\ &= ((n-1) \alpha_k + \beta_k) S - \beta_k A_i \end{aligned}$

故

$\begin{cases} \alpha_{k+1} = (n-1) \alpha_k + \beta_k, \\ \beta_{k+1} = -\beta_k. \end{cases}$

化为矩阵形式即为

$\begin{pmatrix} \alpha_{k+1} \\ \beta_{k+1} \end{pmatrix} = \begin{pmatrix} n-1 & 1 \\ 0 & -1 \end{pmatrix} \begin{pmatrix} \alpha_k \\ \beta_k \end{pmatrix}.$

边界条件为 $\alpha_0=0,\beta_0=-1$。

采用矩阵快速幂计算递推式子，求出 $\alpha_k,\beta_k$，并代入 $S,A_i$ 即可。

也可以根据上述递推公式，手动求出 $\alpha_k,\beta_k$ 的通项公式，从而 $O(1)$ 得到答案。

Code

mod = 998244353

def mtx_mul(a, b):
    res = [[0] * 2 for _ in range(2)]
    for i in range(2):
        for j in range(2):
            res[i][j] = (a[i][0] * b[0][j] % mod + a[i][1] * b[1][j] % mod + mod) % mod
    return res

def mtx_pow(m, k):
    res = [[1, 0], [0, 1]]
    while k:
        if k & 1:
            res = mtx_mul(res, m)
        m = mtx_mul(m, m)
        k >>= 1
    return res

if __name__ == '__main__':
    a0, b0 = 0, 1
    n = int(input())
    a = list(map(int, input().split()))
    S = sum(a)
    M = [[n - 1, 1], [0, -1]]
    q = int(input())
    for i in range(q):
        x, y = map(int, input().split())
        m = mtx_pow(M, x)
        ak = ((m[0][0] * a0) % mod + m[0][1] * b0 % mod) % mod
        bk = ((m[1][0] * a0) % mod + m[1][1] * b0 % mod) % mod
        print((ak * S % mod + bk * a[y - 1] % mod) % mod)

I

Solution

贪心题。

由于产品之间需求的拓扑关系与编号顺序有关，因此很方便的就可以求出：生产某种产品一个，需要多少人（包括所需原料的人力）。人数可以为小数。

显然若生产某材料的利润高，则应该只生产该产品。

将产品的价值除以生产一个产品的需要的人数，就是人均利润。

注意特判产品的原料无法生产的情况。

Code

if __name__ == '__main__':
    n, m = map(int, input().split())
    v = list(map(float, input().split()))
    w = [10 ** 9] * (n + 1)
    for i in range(m):
        a, b, c, d = map(int, input().split())
        if w[a] == 10 ** 9 and c:
            continue
        if b == 0:
            w[b] = min(w[b], 1 / d)
        else:
            c /= d
            w[b] = min(w[b], 1 / d + c * w[a])
    for i in range(n):
        if w[i + 1]:
            v[i] /= w[i + 1]
        else:
            v[i] = 0
    print("{:.2f}".format(max(v)))