浅念づ昔夜's Blog

Like author, like book.

0%

2023 蓝桥杯省赛 Python A组 解题报告

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

A 特殊日期

Solution

利用 Python 系统库 datetime 可以省去日期枚举中的细节处理。

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
import datetime

delta = datetime.timedelta(1) // 每次日期 + 1

st = datetime.date(1900,1,1)
ed = datetime.date(9999,12,31)
ans = 0

while st < ed:
    year, month, day = int(st.year), int(st.month), int(st.day)
    y = m = d = 0
    while year:
        y += year % 10
        year //= 10
    while month:
        m += month % 10
        month //= 10
    while day:
        d += day % 10
        day //= 10
    if y == m + d:
        ans += 1
    st += delta

print(ans)

B 分糖果

Solution

贪心。

分两种情况讨论：

  1. 字符串 SS 的所有字母相同，此时应该尽可能将糖果平均分配。

  2. 字符串 SS 由两种或以上字母组成，此时先把前 xx 小的糖果每人分一个，然后将余下所有糖果给一个手上糖果最小的人。

正确性显然。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
import math

n, x = map(int, input().split())
a = list(input())
a.sort()

if a[0] == a[n - 1]:
    print(a[0] * math.ceil(n / x))
elif a[0] == a[x - 1]:
    for i in range(x - 1, n):
        print(a[i], end='')
else:
    print(a[x - 1])

C 三国游戏

Solution

设

xi=Ai−Bi−Cix_i = A_i-B_i-C_i

对 xix_i 降序排序，sumisum_i 为 xix_i 的前缀和，使得 sumi>0sum_i>0 的最大 ii 即为 AA 国获胜下最多发生的事件数。

同理，另外两个国家也能如法炮制。

时间复杂度 O(n)O(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
27
28
29
30
31
32
33
34
35
36
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
x = [0 for _ in range(n)]
y = [0 for _ in range(n)]
z = [0 for _ in range(n)]
for i in range(n):
    x[i] = a[i] - b[i] - c[i]
    y[i] = b[i] - a[i] - c[i]
    z[i] = c[i] - a[i] - b[i]
x.sort(reverse=True)
y.sort(reverse=True)
z.sort(reverse=True)
ans = res = 0
for i in range(n):
    res += x[i]
    if res <= 0:
        break
    ans = max(ans, i + 1)
res = 0
for i in range(n):
    res += y[i]
    if res <= 0:
        break
    ans = max(ans, i + 1)
res = 0
for i in range(n):
    res += z[i]
    if res <= 0:
        break
    ans = max(ans, i + 1)
if ans == 0:
    print(-1)
else:
    print(ans)

D 平均

Solution

判断哪些数字数量超过 n10\dfrac{n}{10}，并更改它们之中代价最小的几个即可。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
n = int(input())
k = n // 10
a = []
t = [0 for _ in range(10)]
for i in range(n):
    x, y = map(int, input().split())
    a.append((x, y))
a.sort()
for i in range(n):
    t[a[i][0]] += 1
cnt = ans = 0
for i in range(n):
    if i == 0 or a[i][0] != a[i - 1][0]:
        cnt = 0
    cnt += 1
    if cnt <= t[a[i][0]] - k:
        ans += a[i][1]
print(ans)

E 翻转

Solution

手玩手造数据可以发现，只需要从左到右判断哪些位置需要修改，能不能修改即可。

时间复杂度 O(Tn)O(Tn)

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
T = int(input())
while T:
    T -= 1
    a, b = list(input()), list(input())
    flg = ans = 0
    n = len(a)
    for i in range(n):
        if a[i] == b[i]:
            continue
        if i == 0 or b[i - 1] == b[i] or b[i + 1] == b[i]:
            flg = 1
            break
        if b[i] == '0':
            b[i] = '1'
        else:
            b[i] = '0'
        ans += 1
    if flg:
        print(-1)
    else:
        print(ans)

F 子矩阵

Solution

先用一遍单调队列求出每行中每个长度为 bb 的子序列的最大最小值。

再基于上一步计算的结果，对列进行单调队列，计算出所有 a×ba\times b 的子矩阵的最大最小值。

时间复杂度 O(nm)O(nm)。

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
n, m, a, b = map(int, input().split())
Min_1 = [[0 for _ in range(1005)] for _ in range(1005)]
Min_2 = [[0 for _ in range(1005)] for _ in range(1005)]
Max_2 = [[0 for _ in range(1005)] for _ in range(1005)]
Max_1 = [[0 for _ in range(1005)] for _ in range(1005)]
q = [0 for _ in range(1005)]
ans = 0

g = [list(map(int, input().split())) for _ in range(n)]

for i in range(n):
    head, tail = 1, 0
    for j in range(m):
        while head <= tail and q[head] <= j - b:
            head += 1
        while head <= tail and g[i][q[tail]] >= g[i][j]:
            tail -= 1
        tail += 1
        q[tail] = j
        Min_1[i][j] = g[i][q[head]]


for j in range(m):
    head, tail = 1, 0
    for i in range(n):
        while head <= tail and q[head] <= i - a:
            head += 1
        while head <= tail and Min_1[q[tail]][j] >= Min_1[i][j]:
            tail -= 1
        tail += 1
        q[tail] = i
        Min_2[i][j] = Min_1[q[head]][j]

for i in range(n):
    head, tail = 1, 0
    for j in range(m):
        while head <= tail and q[head] <= j - b:
            head += 1
        while head <= tail and g[i][q[tail]] <= g[i][j]:
            tail -= 1
        tail += 1
        q[tail] = j
        Max_1[i][j] = g[i][q[head]]

for j in range(m):
    head, tail = 1, 0
    for i in range(n):
        while head <= tail and q[head] <= i - a:
            head += 1
        while head <= tail and Max_1[q[tail]][j] <= Max_1[i][j]:
            tail -= 1
        tail += 1
        q[tail] = i
        Max_2[i][j] = Max_1[q[head]][j]
    
for i in range(a - 1, n):
    for j in range(b - 1, m):
        ans += Min_2[i][j] * Max_2[i][j]

print(ans)

G 奇怪的数

Solution

本场最难的题。

设 Fi,a,b,c,dF_{i,a,b,c,d} 为第 ii 位为 dd，后五位形如 xabcdxabcd 的方案数。设 mm 为一位上的选择数量，朴素 dp 的时间复杂度是 O(nm5)O(nm^5) 的。

若将 aa 一维改成前缀和的形式，则复杂度可优化为 O(nm4)O(nm^4)。

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
n, m = map(int, input().split())
p, q, ans = 1, 0, 0
mod = 998244353
f = [[[[[0 for _ in range(15)] for _ in range(15)] for _ in range(15)] for _ in range(15)] for _ in range(2)]

for a in range(p, 10, 2):
    for b in range(q, 10, 2):
        for c in range(p, 10, 2):
            for d in range(q, 10, 2):
                f[0][a + 2][b][c][d] = f[0][a][b][c][d] + (a + b + c + d <= m);

for i in range(5, n + 1):
    p, q = p ^ 1, q ^ 1
    for a in range(p, 10, 2):
        for b in range(q, 10, 2):
            for c in range(p, 10, 2):
                for d in range(q, 10, 2):
                    e = m - a - b - c - d
                    if q != (e & 1):
                        e -= 1
                    if e > 8 + q:
                        e = 8 + q
                    f[i & 1][a + 2][b][c][d] = (f[i & 1][a][b][c][d] + f[~i & 1][e + 2][a][b][c] if e >= q else 0) % mod
            
for b in range(q, 10, 2):
    for c in range(p, 10, 2):
        for d in range(q, 10, 2):
            e = m - b - c - d
            if e < p:
                continue
            if p != (e & 1):
                e -= 1
            if e > 8 + p:
                e = 8 + p
            ans = (ans + f[n & 1][e + 2][b][c][d]) % mod
print(ans)

H 阶乘的和

Solution

已知 n+1n+1 个 n!n! 可以合成一个 (n+1)!(n+1)!。我们把所有能合成的 n!n! 都给处理了，剩下最小的 m!m!，答案即为 mm。

defaultdict 是所有元素初始化为 0 的字典。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from collections import defaultdict
n = int(input())
a = list(map(int, input().split()))
a.sort()
mp = defaultdict(int)

for x in a:
    mp[x] += 1

t = a[0]
while 1:
    if mp[t] % (t + 1) == 0:
        mp[t + 1] += mp[t] // (t + 1)
        mp[t] = 0
        t += 1
    else:
        print(t)
        break

I 子树的大小

Solution

通过观察得到两个公式：

  1. 点 xx 下一层最右端的儿子编号为 mx+1mx+1

  2. 点 xx 的父亲编号为

f(x)={⌊xm⌋,if x mod m=1,⌈xm⌉,if x mod m≠1. f(x) = \begin{cases} \lfloor \frac{x}{m} \rfloor, & \text{if } x \bmod m = 1, \\ \lceil \frac{x}{m} \rceil, & \text{if } x \bmod m \neq 1. \end{cases}

由这两个公式，可以轻松判断某点在树中的第几层。让 nn 顺着树一直往上走，直到和 kk 在同一层。根据 n=kn=k 或 nn 在 kk 的左边和右边，容易分类讨论出答案。

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
43
44
45
46
47
48
49
import math

T = int(input())

def layer(u):
    res, num = 1, 1
    while num < u:
        num = num * m + 1
        res += 1
    return res

def solve():
    global n, m, k
    n, m, k = map(int, input().split())
    lyk, lyn = layer(k), layer(n)
    p = n
    
    while layer(p) > lyk:
        if p % m == 1:
            p = math.floor(p / m)
        else:
            p = math.ceil(p / m)
            
    if p == k:
        ans, cnt = 1, 1
        while layer(p) < layer(n):
            p = p * m + 1
            cnt *= m
            ans += cnt
        print(ans - p + n)
    elif p < k:
        p, ans, cnt = k, 1, 1
        while layer(p) < layer(n) - 1:
            cnt *= m
            ans += cnt
            p = p * m + 1
        print(ans)
    else:
        p, ans, cnt = k, 1, 1
        while layer(p) < layer(n):
            cnt *= m
            ans += cnt
            p = p * m + 1
        print(ans)


while T:
    T -= 1
    solve()

K 反异或 01 串

Solution

注意到 s^' 一定是回文串。特别地，s^' 长度为奇数时，中间一位一定为 00。

因此我们寻找 TT 中含 11 最多的回文子串作为 s^'。设 ss 长度为 nn，当 s^'_i=1 时，只需构造 si=0s_i=0，sn−i+1=1s_{n-i+1}=1 即可。已知 TT 有 xx 个 11，s′s' 有 yy 个 11，答案即为 x−y2x - \frac{y}{2}。

剩下就是如何寻找 s′s' 的问题。采用 manacher 找出 TT 中所有的回文子串，并利用前后缀和 O(1)O(1) 求出回文子串含 11 的个数即可。

时间复杂度 O(n)O(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
s = list(input())
s = '#' + '#'.join(s) + '#'
d = [0 for _ in range(2 * 10 ** 6 + 10)]
fsum = [0 for _ in range(2 * 10 ** 6 + 10)]
bsum = [0 for _ in range(2 * 10 ** 6 + 10)]
l, r, n = 0, -1, len(s)
for i in range(n):
    k = 1 if i > r else min(d[l + r - i], r - i + 1)
    while i - k >= 0 and i + k < n and s[i - k] == s[i + k]:
        k += 1
    d[i] = k
    k -= 1
    if i + k > r:
        l, r = i - k, i + k
tot = ans = 0
for i in range(1, n):
    fsum[i] = fsum[i - 1] + (s[i] == '1')
    tot += (s[i] == '1')
for i in range(n - 1, -1, -1):
    bsum[i] = bsum[i + 1] + (s[i] == '1')
for i in range(n):
    if s[i] == '1':
        continue
    ans = max(ans, fsum[i] - fsum[i - d[i]] + bsum[i] - bsum[i + d[i]])
print(tot - (ans >> 1))