C语言网：2022年蓝桥杯第十三届大赛省赛真题https://www.dotcpp.com/oj/train/1035/
这个题集涵盖了第十三届省赛所有组别的编程题，但 Python B 组的题解我写在了另一篇文章中：蓝桥杯【第13届省赛】Python B组 91.75分
刷题统计 100【题目描述】
小明决定从下周一开始努力刷题准备蓝桥杯竞赛。他计划周一至周五每天做 a 道题目，周六和周日每天做 b 道题目。请你帮小明计算，按照计划他将在第几天实现做题数大于等于 n 题？
【输入格式】
输入一行包含三个整数 a, b 和 n
【输出格式】
输出一个整数代表天数。
【样例】
| 输入 | 输出 |
| 10 20 99 | 8 |
【评测用例规模与约定】
| 50% | |
| 100% |
【解析及代码】
from math import ceil
a, b, n = map(int, input().split())
# 每周做题数
num_per_week = 5 * a + 2 * b
# 花费周数
cost_week = n // num_per_week
# 经过 m 周后还差多少
undone = n - cost_week * num_per_week
# 总共花费天数
cost_day = cost_week * 7
if undone <= 5 * a:
cost_day += ceil(undone / a)
else:
undone -= 5 * a
cost_day += 5 + ceil(undone / b)
print(cost_day)
修剪灌木 100
【题目描述】
爱丽丝要完成一项修剪灌木的工作。有 N 棵灌木整齐的从左到右排成一排。爱丽丝在每天傍晚会修剪一棵灌木，让灌木的高度变为 0 厘米。爱丽丝修剪灌木的顺序是从最左侧的灌木开始，每天向右修剪一棵灌木。当修剪了最右侧的灌木后，她会调转方向，下一天开始向左修剪灌木。直到修剪了最左的灌木后再次调转方向。然后如此循环往复。灌木每天从早上到傍晚会长高 1 厘米，而其余时间不会长高。在第一天的早晨，所有灌木的高度都是 0 厘米。爱丽丝想知道每棵灌木最高长到多高。
【输入格式】
一个正整数 N ，含义如题面所述。
【输出格式】
输出 N 行，每行一个整数，第行表示从左到右第 i 棵树最高能长到多高。
【样例】
| 输入 | 输出 |
| 3 | 4 2 4 |
【评测用例规模与约定】
| 30% | |
| 100% |
【解析及代码】
分析一下样例，当输入 3 时输出是 4, 2, 4
| 早晨 | 1 1 1 | 1 2 2 | 2 1 3 | 3 1 1 | 4 1 2 |
| 傍晚 | 0 1 1 | 1 0 2 | 2 1 0 | 3 0 1 | 0 1 2 |
从表中可以看到：灌木最高高度 = 最长裁剪时间间隔 + 1
n = int(input())
for i in range(n):
# 向左裁剪 -> 向右裁剪
interval_1 = 2 * i
# 向右裁剪 -> 向左裁剪
interval_2 = 2 * (n - i - 1)
print(max([interval_1, interval_2]))
青蛙过河 77
【问题描述】
小青蛙住在一条河边，它想到河对岸的学校去学习。小青蛙打算经过河里的石头跳到对岸。
河里的石头排成了一条直线，小青蛙每次跳跃必须落在一块石头或者岸上。不过，每块石头有一个高度，每次小青蛙从一块石头起跳，这块石头的高度就会下降 1，当石头的高度下降到 0 时小青蛙不能再跳到这块石头上（某次跳跃后使石头高度下降到 0 是允许的）。
小青蛙一共需要去学校上 x 天课，所以它需要往返 2x 次。当小青蛙具有一个跳跃能力 y 时，它能跳不超过 y 的距离。
请问小青蛙的跳跃能力至少是多少才能用这些石头上完 x 次课。
【输入格式】
输入的第一行包含两个整数 n, x，分别表示河的宽度和小青蛙需要去学校的天数。请注意 2x 才是实际过河的次数。
第二行包含 n − 1 个非负整数 H1, H2, · · · , Hn-1，其中 Hi > 0 表示在河中与小青蛙的家相距 i 的地方有一块高度为 Hi 的石头，Hi = 0 表示这个位置没有石头。
【输出格式】
输出一行，包含一个整数，表示小青蛙需要的最低跳跃能力。
【样例】
| 输入 | 输出 | 说明 |
| 5 1 1 0 1 0 | 4 | 由于只有两块高度为 1 的石头，所以往返只能各用一块。 第 1 块石头和对岸的距离为 4，如果小青蛙的跳跃能力为 3 则无法满足要求。所以小青蛙最少需要 4 的跳跃能力。 |
【评测用例规模与约定】
| 30% | |
| 60% | |
| 100% | |
【解析及代码】
往返 2x 次，等价于 2x 只青蛙同时从左到右过河
width, time = map(int, input().split()) time *= 2 # 石头高度: 补上起点 (0)、终点 (2x) available = [0] + list(map(int, input().split())) + [time]
总的思路就是 贪心 + 二分答案，验证函数的思路是：
- 记录每个位置的青蛙数量，青蛙能跳多远就跳多远
- 有青蛙没法跳出某个位置时，该跳跃能力不可行
def check(pace):
# 记录对应位置剩余的青蛙
member = [time] + [0] * width
# 当前石头高度
avai = available[:]
# 枚举青蛙所在位置
for loc in range(width):
# 能跳多远跳多远
for next_ in range(
min([loc + pace, width]), loc, -1):
# 移动的青蛙数
move_num = min([
member[loc], avai[next_]
])
# 更新青蛙位置, 石头高度
member[loc] -= move_num
if next_ < width:
member[next_] += move_num
avai[next_] -= move_num
# 有青蛙没法跳出该位置
if member[loc]: return False
return True
然后就是非常简单的二分法了
if check(1):
print(1)
else:
# 二分答案
l, r = 1, width
while l + 1 < r:
mid = (l + r) // 2
# r 永远可行
if check(mid):
r = mid
# l 永远不可行
else:
l = mid
print(r)
时间超限，点到为止
X进制减法 97【题目描述】
进制规定了数字在数位上逢几进一。
X 进制是一种很神奇的进制，因为其每一数位的进制并不固定！例如说某种 X 进制数，最低数位为二进制，第二数位为十进制，第三数位为八进制，则 X 进制数 321 转换为十进制数为 65。
现在有两个 X 进制表示的整数 A 和 B，但是其具体每一数位的进制还不确定，只知道 A 和 B 是同一进制规则，且每一数位最高为 N 进制，最低为二进制。请你算出 A − B 的结果最小可能是多少。
请注意，你需要保证 A 和 B 在 X 进制下都是合法的，即每一数位上的数字要小于其进制。
【输入格式】
第一行一个正整数 N，含义如题面所述。
第二行一个正整数 Ma，表示 X 进制数 A 的位数。
第三行 Ma 个用空格分开的整数，表示 X 进制数 A 按从高位到低位顺序各个数位上的数字在十进制下的表示。
第四行一个正整数 Mb，表示 X 进制数 B 的位数。
第五行 Mb 个用空格分开的整数，表示 X 进制数 B 按从高位到低位顺序各个数位上的数字在十进制下的表示。
请注意，输入中的所有数字都是十进制的。
【输出格式】
输出一行一个整数，表示 X 进制数 A − B 的结果的最小可能值转换为十进制后再模 1000000007 的结果。
【样例】
| 输入 | 输出 | 说明 |
| 11 3 10 4 0 3 1 2 0 | 94 | 当进制为：最低位 2 进制，第二数位 5 进制， 第三数位 11 进制时，减法得到的差最小。 此时 A 在十进制下是 108， B 在十进制下是 14，差值是 94。 |
【评测用例规模与约定】
| 30% | N ≤ 10；Ma, Mb ≤ 8 |
| 100% | 2 ≤ N ≤ 1000；1 ≤ Ma, Mb ≤ 100000；A ≥ B |
【解析及代码】
以 a 为 [10, 2, 1]，b 为 [1, 4, 0] 为例
- 最小进制：与 a, b 对应位置的数字有关，依次为 [11, 5, 2]
- δ = a - b：设各数位进制依次为 [x, y, z]，则 [9, -2, 1] = ((9y - 2)z + 1)，而这时 z 取最大进制还是最小进制，就由 9y - 2（高位换算到低位）的正负决定了；最高位的进制不用管
- a >= b：因为这个条件的存在，所以 δ 的前 n 位换算后总是大于等于 0，所以一直取最小进制就行了
mod = 10 ** 9 + 7
max_base = int(input())
number = []
for _ in range(2):
_ = input()
number.append(list(map(int, input().split())))
a, b = number
# a >= b, 可能需要补齐
b = (len(a) - len(b)) * [0] + b
# 最小进制
min_base = [max([max(ij) + 1, 2]) for ij in zip(a, b)]
# a - b
delta = [i - j for i, j in zip(a, b)]
# 记录每一时刻的 最小、最大
result = delta[0]
# 枚举低位
for i in range(1, len(min_base)):
# 高位换算到低位
result = result * min_base[i] + delta[i]
result %= mod
print(result)
还是时间超限了，没有刷满
矩形拼接 100【题目描述】
已知 3 个矩形的大小依次是 a1 × b1, a2 × b2 和 a3 × b3。用这 3 个矩形能拼出的所有多边形中，边数最少可以是多少？例如用 3 × 2 的矩形（用 A 表示）、4 × 1 的矩形（用 B 表示）和 2 × 4 的矩形（用 C 表示）可以拼出如下 4 边形
例如用 3 × 2 的矩形（用 A 表示）、3 × 1 的矩形（用 B 表示）和 1 × 1 的矩形（用 C 表示）可以拼出如下 6 边形。
【输入格式】
输入包含多组数据。
第一行包含一个整数 T，代表数据组数。
以下 T 行，每行包含 6 个整数 a1, b1, a2, b2, a3, b3，其中 a1, b1 是第一个矩形的边长，a2, b2 是第二个矩形的边长，a3, b3 是第三个矩形的边长。
【输出格式】
对于每组数据，输出一个整数代表答案。
【样例】
| 输入 | 输出 |
| 2 2 3 4 1 2 4 1 2 3 4 5 6 | 4 6 |
【评测用例规模与约定】
| 10% | |
| 30% | |
| 60% | |
| 100% | |
【解析及代码】
小的不才，没有什么比较好的解法，解法接近暴力，基本的思路是：
- 将三个矩形分成 2 + 1 的形式，对前两个矩形进行拼接，以 int 表示凸边，以自定义类 Corner 表示凹角
- 使用列表存储凸边、凹角，以表示多边形，该多边形的边数为：
class Corner:
''' 凹角'''
def __init__(self, edge: list, third: list):
# 该凹角相邻的两条边
self.edge = edge
# 该凹角在拼接上第三个矩形后, 对边数的贡献
self.contri = self.stack(third) + 2
def stack(self, rect):
# 刚好可以嵌入转角
for r in rect, rect[::-1]:
if r == self.edge:
return -2
# 有一条边与转角吻合
for a in rect:
for b in self.edge:
if a == b:
return 0
# 无最佳拼接方法
return 2
- 当第三个矩形拼接在凹角处时，使用 stack 方法计算该凹角对边数的贡献
- 当第三个矩形未拼接在凹角处时，则凹角对边数的贡献是 2
groups = int(input())
for _ in range(groups):
# 整理出矩形的边长
rects = list(map(int, input().split()))
rects = [rects[i * 2: (i + 1) * 2] for i in range(3)] * 2
# 对每个二元组进行拼接: 凸边, 凹角
result = []
for i in range(3):
temp1, temp2, temp3 = rects[i: i + 3]
for a in range(2):
for b in range(2):
# 新多边形
new = [temp1[a], temp2[b], temp1[1 - a] + temp2[1 - b]]
have_corner = temp1[a] != temp2[b]
# 两拼接边长不相等: 产生转角
if have_corner:
# 拼接残差
res = abs(temp1[a] - temp2[b])
if temp1[a] > temp2[b]:
corner = Corner([res, temp2[1 - b]], temp3)
new += [temp1[1 - a], corner]
else:
corner = Corner([res, temp1[1 - a]], temp3)
new += [temp2[1 - b], corner]
# 两拼接边长相等
else:
new += [temp1[1 - a] + temp2[1 - b]]
# 拼接第三个矩形
basic_num = len(new) + have_corner
for ele in set(new):
# 在转角处拼接: 访问 Corner 的 contri 属性
if isinstance(ele, Corner):
result += [len(new) - 1 + ele.contri]
# 非转角处拼接: Corner 对边数的贡献是 2
else:
for c in set(temp3):
if c == ele:
result += [basic_num]
break
result += [basic_num + 2]
print(min(result))
GCD 100
【题目描述】
给定两个不同的正整数 a, b，求一个正整数 k 使得 gcd(a + k, b + k) 尽可能大，其中 gcd(a, b) 表示 a 和 b 的最大公约数，如果存在多个 k，请输出所有满足条件的 k 中最小的那个。
【输入格式】
输入一行包含两个正整数 a, b，用一个空格分隔。
【输出格式】
输出一行包含一个正整数 k。
【样例】
| 输入 | 输出 |
| 5 7 | 1 |
【评测用例规模与约定】
| 20% | |
| 40% | |
| 100% |
【解析及代码】
两个数的最大公约数只可能是两者之差的因数，即 gcd(a + k, b + k) 最大为 |a - b|，记为 gain：
求 k 使 m, n 均为整数，有
为使 k 尽可能小，令
from fractions import Fraction from math import ceil a, b = map(int, input().split()) max_gcd = abs(a - b) gain = Fraction(a, max_gcd) k = ceil(gain) * max_gcd - a print(int(round(k)))
这种题容易因为小数精度的问题丢分，使用分数可以保证精度
因数平方和【问题描述】
记 f(x) 为 x 的所有因数的平方的和。例如：。
定义。给定 n, 求 g(n) 除以 的余数。
【输入格式】
输入一行包含一个正整数 n
【输出格式】
输出一个整数表示答案 g(n) 除以 的余数
【样例】
| 输入 | 输出 |
| 100000 | 680584257 |
【评测用例规模与约定】
| 20% | |
| 30% | |
| 100% |
【解析及代码】
重新排序 5【问题描述】
给定一个数组 A 和一些查询 Li , Ri，求数组中第 Li 至第 Ri 个元素之和。
小蓝觉得这个问题很无聊，于是他想重新排列一下数组，使得最终每个查询结果的和尽可能地大。小蓝想知道相比原数组，所有查询结果的总和最多可以增加多少?
【输入格式】
输入第一行包含一个整数 n。
第二行包含 n 个整数 A1, A2, · · · , An，相邻两个整数之间用一个空格分隔。
第三行包含一个整数 m 表示查询的数目。
接下来 m 行，每行包含两个整数 Li、Ri ，相邻两个整数之间用一个空格分隔。
【输出格式】
输出一行包含一个整数表示答案。
【样例】
| 输入 | 输出 | 说明 |
| 5 1 2 3 4 5 2 1 3 2 5 | 4 | 原来的和为 6 + 14 = 20， 重新排列为 (1, 4, 5, 2, 3) 后和为 10 + 14 = 24，增加了 4。 |
【评测用例规模与约定】
| 30% | |
| 50% | |
| 70% | |
| 100% | |
【解析及代码】
使用权重向量来记录数列对应位置的数被取的次数
为了降低时间复杂度，使用差分数列进行表示
对权重向量、原数列进行排序，按序相乘即为最优结果
length = int(input())
seq = list(map(int, input().split()))
# 权重向量的差分数列
weight = [0] * length
for _ in range(int(input())):
left, right = map(lambda i: int(i) - 1, input().split())
# 更新差分数列
weight[left] += 1
if right + 1 < length:
weight[right + 1] -= 1
# 还原得到权重向量
for i in range(1, length):
weight[i] += weight[i - 1]
origin = [e * w for e, w in zip(seq, weight)]
current = [e * w for e, w in zip(*map(sorted, [seq, weight]))]
print(sum(current) - sum(origin))
我觉得思路应该没错，但是在 C 语言网的得分只有 5 分……
质因数个数 71【题目描述】
给定正整数 n，请问有多少个质数是 n 的约数。
【输入格式】
输入的第一行包含一个整数 n。
【输出格式】
输出一个整数，表示 n 的质数约数个数。
【样例】
| 输入 | 输出 |
| 396 | 3 |
【评测用例规模与约定】
| 30% | |
| 60% | |
| 100% |
【解析及代码】
def factorization(n):
''' 质因数分解'''
factor = []
i = 2
while i ** 2 <= n:
if n % i == 0:
factor.append(i)
n //= i
while n % i == 0:
n //= i
i += 1
if i > 1:
factor.append(i)
return factor
n = int(input())
print(len(factorization(n)))
时间超限，刷不动了
