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

A 特殊日期

Solution

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

Code

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. 字符串 $S$ 的所有字母相同，此时应该尽可能将糖果平均分配。

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

正确性显然。

Code

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

设

$x_i = A_i-B_i-C_i$

对 $x_i$ 降序排序，$sum_i$ 为 $x_i$ 的前缀和，使得 $sum_i>0$ 的最大 $i$ 即为 $A$ 国获胜下最多发生的事件数。

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

时间复杂度 $O(n)$。

Code

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

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

Code

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)$

Code

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

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

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

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

Code

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

本场最难的题。

设 $F_{i,a,b,c,d}$ 为第 $i$ 位为 $d$，后五位形如 $xabcd$ 的方案数。设 $m$ 为一位上的选择数量，朴素 dp 的时间复杂度是 $O(nm^5)$ 的。

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

Code

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+1$ 个 $n!$ 可以合成一个 $(n+1)!$。我们把所有能合成的 $n!$ 都给处理了，剩下最小的 $m!$，答案即为 $m$。

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

Code

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. 点 $x$ 下一层最右端的儿子编号为 $mx+1$

2. 点 $x$ 的父亲编号为

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}

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

Code

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^' 长度为奇数时，中间一位一定为 $0$。

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

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

时间复杂度 $O(n)$。

Code

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))