浅念づ昔夜's Blog

Like author, like book.

0%

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

发表于 更新于 分类于
本文字数： 1.8k 阅读时长 ≈ 6 分钟

A 跑步计划

Solution

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

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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%60\% 的数据，考场上可以作为对拍。

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

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

对于给定的 nn，可以快速算出对应的 ii 和 jj。然后根据 ai,ja_{i,j} 和 bi,jb_{i,j} 分别统计答案和更新 nn，直到 n=0n=0 为止。

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

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
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%40\% 的数据，选择 O(nm)O(nm) 的 dp，设 fi,jf_{i,j} 表示第 ii 个位置，前面一共有 jj 个 2023 的方案。

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

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

记

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

其中证明过程如下：

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

(n−3jj)\binom{n-3j}{j}

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

n−4j+j=n−3jn-4j+j=n-3j

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

10n−4j10^{n-4j}

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

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

E(m)=∑j=m⌊n/4⌋(−1) j−m(jm)A(j)=∑j=m⌊n/4⌋(−1) j−m(jm)(n−3jj) 10 n−4j .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}\,. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
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

状压 + 背包

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

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

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

要注意的细节是，记得判断条件 S−i≤BS-i\le B 和 i≤Ai\le A，其中 ii 为车 11 的重量。

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

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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)O(n*3) 的 dp。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
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\log n，故可以通过本题。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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]))