第十三届蓝桥杯C++B组题解(Python版本)

Acwing上目前好像只有C++B组的题,所以就顺便做了一下。。。

刷题统计

分析

首先以$7$天为单位进行计算,余数再枚举即可

代码实现(Python)

a, b, n = map(int, input().split())
t = a * 5 + 2 * b
res = n // t * 7
n %= t
if n <= a * 5: res += (n + a - 1) // a
else: res += 5 + (n - a * 5 + b - 1) // b;
print(res)

修剪灌木

分析

能长到的最高高度就是距离左右边界的最大距离乘二

代码实现(Python)

n = int(input())
print('\n'.join([str(2 * max(i - 1, n - i)) for i in range(1, n + 1)]))

X 进制减法

分析

这题最大的难点在于读懂题目,读懂之后发现每一位尽量取较小的进制即可

代码实现(Python)

import sys
input = sys.stdin.readline

n = int(input())
ma = int(input())
a = list(map(int, input().split()))
mb = int(input())
b = [0 for i in range(ma - mb)] + list(map(int, input().split()))

x = []
for i in range(ma):
    x.append(max(2, max(a[i], b[i]) + 1))
res = 0
for i in range(ma):
    res = (res * x[i] + a[i] - b[i]) % 1000000007
print(res)

统计子矩阵

分析

可以枚举矩阵的左右边界是从哪一列到哪一列,然后用枚举矩形的下边界用双指针统计答案即可,复杂度为$O(n^3)$

代码实现(Python)

import sys
input = sys.stdin.readline

n, m, k = map(int, input().split())
s = [[0 for i in range(m + 1)]]
for _ in range(n):
    s.append([0] + list(map(int, input().split())))
    for i in range(1, m + 1):
        s[-1][i] += s[-1][i - 1]
res = 0
for i in range(1, m + 1):
    for j in range(i, m + 1):
        ss, l, r = 0, 1, 1
        while r <= n and l <= n:
            ss += s[r][j] - s[r][i - 1]
            while ss > k:
                ss -= s[l][j] - s[l][i - 1]
                l += 1
            res += r - l + 1
            r += 1
print(res)

积木画

分析

用f[i][j]表示第放积木放到$i$列时第$i$列的状态为$j$时的方案数,其中$0\le j < 4$,$j$的两个bit分别代表上下两个格子是否已经有了积木,然后想明白转移就是个很简单的线性dp,数组的第一维可以滚动掉,当然也可以上快速幂,但是本题没有必要

代码实现(Python)

mod = 1000000007
f = [0, 0, 0, 1]
for i in range(0, int(input()) + 1):
    g = [(f[0] + f[3]) % mod, (f[0] + f[2]) % mod, (f[0] + f[1]) % mod, (f[0] + f[1] + f[2]) % mod]
    f, g = g, f
print(f[0])

扫雷

分析

一个典型的多源bfs问题,主要的难点在于对于队头结点如何扩展.注意到这题的半径r很小,可以直接枚举所有与队头结点距离小于的点,判断这个点是否有地雷,如果有就继续扩展.这样每次扩展最多$400$个点,复杂度可以接受,此外还要注意这题一个点可能有多个地雷,要注意判断.

代码实现(Python)

from collections import defaultdict, deque

n, m = map(int, input().split())
ids = defaultdict(list)
v = set()
q = deque()
delta = 2000000000
a = [[]]

for i in range(1, n + 1):
    a.append(list(map(int, input().split())))
    ids[a[-1][0] * delta + a[-1][1]].append(i);
for i in range(m):
    q.append(list(map(int, input().split())))
res = 0
while q:
    x, y, r = q[0]
    q.popleft()
    for i in range(-r, r + 1):
        for j in range(-r, r + 1):
            if i * i + j * j <= r * r:
                tid = (x + i) * delta + y + j
                if tid in ids and ids[tid][0] not in v:
                    for k in ids[tid]:
                        res += 1
                        q.append(a[k])
                        v.add(k)
print(res)

李白打酒加强版

分析

状态$f[i][j][k]$表示走到第$i$步时,李白还剩下$j$斗酒,已经打过$k$次酒的方案数目,状态转移很简单,可以参照代码.初始边界条件是$f[0][2][0] = 1$(初始有两斗酒),答案是$f[n + m - 1][1][n]$,(因为要求最后一次操作必须是喝酒)

代码实现(Python)

n, m = map(int, input().split())
f = [[[0 for k in range(n + 1)] for j in range(m + 1)] for i in range(n + m + 1)]
mod = 1000000007

f[0][2][0] = 1
for i in range(n + m - 1):
    for j in range(m + 1):
        for k in range(min(i + 1, n + 1)):
            if k + 1 <= n and j * 2 <= m:
                f[i + 1][j * 2][k + 1] = (f[i + 1][j * 2][k + 1] + f[i][j][k]) % mod
            if j >= 1 and i - k + 1 <= m:
                f[i + 1][j - 1][k] = (f[i + 1][j - 1][k] + f[i][j][k]) % mod
print(f[n + m - 1][1][n])

砍竹子

分析

对于第$i$棵竹子来说,如果当前高度他前面竹子的高度相同,那么这棵竹子可以和前面的竹子一起砍,否则的话必须花费一个单位的单价砍这棵竹子,所以统计该竹子前一棵竹子被砍到$1$会经历的高度,和当前竹子重叠的部分不需要花费,不重叠的部分才需要花费.

代码实现(Python)

from math import sqrt
import sys
input = sys.stdin.readline

def get(x) -> int: return int(sqrt(x // 2 + 1))

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

dic1, dic2 = set(), set()
res = 0
for t in a:
    while t > 1:
        if t not in dic1: res += 1
        dic2.add(t)
        t = get(t)
    dic1, dic2 = dic2, dic1
    dic2 = set()
print(res)