第十四届蓝桥杯国赛 Python A组 解题报告

A 跑步计划

Solution

datetime 库中 的 weekday() 可以获取某一天的星期信息。

Code

import datetime

delta = datetime.timedelta(1)
st = datetime.date(2023, 1, 1)
ed = datetime.date(2024, 1, 1)
ans = 0

while st != ed:
    y, m, d = int(st.year), int(st.month), int(st.day)
    if m // 10 == 1 or m % 10 == 1 or d % 10 == 1 or d // 10 == 1 or st.weekday() == 0:
        ans += 5
    else:
        ans += 1
    st += delta
    
print(ans)

B 残缺的数字

Solution

当前亮的灯，可能的数字一定也是亮的。

Code

str = ['1111110', '0110000', '1101101', '1111001', '0110011', '1011011', '1011111', '1110000', '1111111', '1111011']

ans = 1
for T in range(18):
    s = input()
    cnt = 0
    for x in str:
        flg = 1
        s, x = list(s), list(x)
        for i in range(7):
            if s[i] == '1' and x[i] == '0':
                flg = 0
                break
        cnt += flg
    ans *= cnt
print(ans) // 254016000

C 整数变换

Solution

暴力计算可以满足 $60\%$ 的数据，考场上可以作为对拍。

考虑正解，注意到一次操作最多只能减去 $9\times 9=81<100$，也许我们可以选择预处理一些本质相同的计算。

对于预处理，设 $a_{i,j}$ 表示一个数 \bmod 1000 之后为 $i$，除后三位外所有位数之和为 $j$，通过 $a_{i,j}$ 次操作后第四位需要退位，即导致 $j$ 会发生变化。通常情况下后三位不会直接被同时减到 $0$，因此设 $b_{i,j}$ 记录最后一次操作后后三位的情况。

对于给定的 $n$，可以快速算出对应的 $i$ 和 $j$。然后根据 $a_{i,j}$ 和 $b_{i,j}$ 分别统计答案和更新 $n$，直到 $n=0$ 为止。

预处理的循环次数约为 $1000\times 80 = 8\times 10^4$，求解 $n$ 约需要 $10^6$ 次循环，可以通过本题。

Code

n = int(input())
a = [[0 for _ in range(105)] for _ in range(10010)]
b = [[0 for _ in range(105)] for _ in range(10010)]
ans = 0

for i in range(1, 1001):
    for j in range(0, 80):
        num, cnt = i, 0
        while num:
            res, sum = num, 0
            while res:
                sum += res % 10
                res //= 10
            num -= sum + j
            cnt += 1
            if num <= 0:
                a[i][j] = cnt
                b[i][j] = num
                break
                
while n:
    if n < 1000:
        ans += a[n][0]
        break
    x = n % 1000
    if x == 0:
        res, sum = n, 0
        while res:
            sum += res % 10
            res //= 10
        n -= sum
        ans += 1
        continue
    y = n // 1000
    z = 0
    while y:
        z += y % 10
        y //= 10
    ans += a[x][z]
    n = n - x + b[x][z]
print(ans)

D 2023

对于 $40\%$ 的数据，选择 $O(nm)$ 的 dp，设 $f_{i,j}$ 表示第 $i$ 个位置，前面一共有 $j$ 个 2023 的方案。

正解卡在容斥原理那一步实在理解不了，下面给出 gpt 的做法：

下面给出一种基于排列组合（严格来说是利用“不重叠子串”的插板法与容斥思想）的数学解法，其核心结论是：

记

$A(j)=\binom{n-3j}{j}\,10^{\,n-4j} \quad (j\ge 0)$

其中证明过程如下：

如果我们“强制”在字符串中出现某一组不重叠的 “2023”（注意 “2023” 不可能自我重叠，因此任何一组出现必定分散开来），那么可证明放置 $j$ 个非重叠“2023”有

$\binom{n-3j}{j}$

种方法（这实际上就是“占用了 $4j$ 个位置，但 $j-1$ 个间隙重叠抵消了 $j-1$ 个位置”，即

$n-4j+j=n-3j$

，其余 $n-4j$ 个位置任取 10 个数字，共

$10^{n-4j}$

种填法．不过这种计数方法“过计”了那些额外出现 “2023” 的情况。

进一步利用容斥原理可证明：恰好出现 $m$ 次的数量为

$E(m)=\sum_{j=m}^{\lfloor n/4\rfloor} (-1)^{\,j-m}\binom{j}{m}A(j) =\sum_{j=m}^{\lfloor n/4\rfloor} (-1)^{\,j-m}\binom{j}{m}\binom{n-3j}{j}\,10^{\,n-4j}\,.$

MOD = 998244353

def solve():
    import sys
    n, m = map(int, input().split())

    # 最大可能用到的数不超过 n（注意：组合数 binom(n-3j, j) 中 n-3j 最大为 n）
    maxN = n
    fact = [1] * (maxN + 1)
    invfact = [1] * (maxN + 1)
    for i in range(2, maxN + 1):
        fact[i] = fact[i - 1] * i % MOD
    invfact[maxN] = pow(fact[maxN], MOD - 2, MOD)
    for i in range(maxN, 0, -1):
        invfact[i - 1] = invfact[i] * i % MOD

    def binom(a, b):
        if b < 0 or b > a:
            return 0
        return fact[a] * invfact[b] % MOD * invfact[a - b] % MOD

    # 根据题意，j 的取值为 m <= j <= floor(n/4)
    J_max = n // 4
    ans = 0
    for j in range(m, J_max + 1):
        # 此处 binom(j, m) 来自容斥展开
        term = binom(j, m) * binom(n - 3 * j, j) % MOD
        # 剩余 n-4j 个位置任取数字
        term = term * pow(10, n - 4 * j, MOD) % MOD
        # 符号 (-1)^(j-m)
        if (j - m) & 1:
            term = -term
        ans = (ans + term) % MOD
    sys.stdout.write(str(ans % MOD))

if __name__ == '__main__':
    solve()

E 火车运输

Solution

状压 + 背包

朴素的想法是，设 $F_{i,j}=1$ 表示存在车 $1$ 的重量为 $i$，车 $2$ 的重量为 $j$ 的情况，然后进行背包。时间复杂度为 $O(nm^2)$，是不可接受的。

更优的做法是，设 $F_s$ 表示两车总重为 $s$ 时，车 $1$ 可能装了多少重量的货物。当 $F_s$ 二进制下的第 $i$ 位为 $1$ 时，代表存在两车总重为 $s$，车 $1$ 重量为 $i$ 的情况。易见 $F_s$ 最大可以为 $2^{1001}$。如果是 C++ 的话，建议使用 vector<bitset<1001>> 定义 $F$。默认 $F_s$ 最末端为第 $0$ 位。故初始化 $F_0=1$。

根据 $F$ 的定义，我们容易得到转移方程如代码所示。答案即为使 $F_i$ 不为零的最大的 $i$。

要注意的细节是，记得判断条件 $S-i\le B$ 和 $i\le A$，其中 $i$ 为车 $1$ 的重量。

时间复杂度 $O(\frac{nm^2}{w})$，参考了 bitset 的复杂度。

Code

n, A, B = map(int, input().split())
a = list(map(int, input().split()))
f = [0 for _ in range(2010)]
f[0] = 1
tot = (1 << (A + 1)) - 1

for i in range(n):
    for j in range(A + B, a[i] - 1, -1):
        f[j] |= (f[j - a[i]] << a[i]) & tot // tot 负责除掉 i>A 的部分
        low = max(j - B, 0) // 移项得到 i >= j-B
        f[j] |= (f[j - a[i]] >> low) << low // 去掉 i<low 的部分

for i in range(A + B, -1, -1):
    if f[i]:
        print(i)
        break

F 走方格

Solution

Bfs 即可。第二种做法是 $O(n*3)$ 的 dp。

Code

from queue import Queue

n = int(input())
a = [[0 for _ in range(1010)] for _ in range(1010)]
for i in range(n):
    a[i] = list(map(int, input().split()))
vis = [[0 for _ in range(1010)] for _ in range(1010)]

def bfs():
    q = Queue()
    q.put((0, 0, 0))
    vis[0][0] = 1
    while not q.empty():
        (x, y, z) = q.get()

        if (x, y) == (n - 1, n - 1):
            print(z)
            return

        if x < n - 1 and not vis[x + 1][y]:
            q.put((x + 1, y, z + 1))
            vis[x + 1][y] = 1

        if y < n - 1 and not vis[x][y + 1]:
            q.put((x, y + 1, z + 1))
            vis[x][y + 1] = 1

        for i in range(y + 1, n):
            if a[x][i - 1] <= a[x][i]:
                break
            if not vis[x][i]:
                q.put((x, i, z + 1))
                vis[x][i] = 1

        for i in range(y - 1, -1, -1):
            if a[x][i] >= a[x][i + 1]:
                break
            if not vis[x][i]:
                q.put((x, i, z + 1))
                vis[x][i] = 1

bfs()

H 彩色二叉树

Solution

对于某个询问，先从新到旧枚举修改信息，暴力计算修改点和询问点的距离。

由于是完全二叉树，树的深度是 $\log n$，故可以通过本题。

Code

n, q = map(int, input().split())
a = []

def dis(x, y):
    res = 0
    while x != y:
        if x > y:
            x >>= 1
        else:
            y >>= 1
        res += 1
    return res

def query(x):
    m = len(a)
    for i in range(m - 1, -1, -1):
        if dis(a[i][0], x) <= a[i][1]:
            return a[i][2]
    return 0

for i in range(q):
    cur = list(map(int, input().split()))
    if cur[0] == 1:
        a.append((cur[1], cur[2], cur[3]))
    else:
        print(query(cur[1]))