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)
修剪灌木
【题目描述】
爱丽丝要完成一项修剪灌木的工作。有 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
但还要考虑一种情况：灌木在第一次裁剪之前就已经达到最高高度
矩形拼接 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)))
这种题容易因为小数精度的问题丢分，使用分数可以保证精度
重新排序 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 分……
青蛙过河【问题描述】
小青蛙住在一条河边，它想到河对岸的学校去学习。小青蛙打算经过河里的石头跳到对岸。
河里的石头排成了一条直线，小青蛙每次跳跃必须落在一块石头或者岸上。不过，每块石头有一个高度，每次小青蛙从一块石头起跳，这块石头的高度就会下降 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% | |
【解析及代码】
质因数个数 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)))
时间超限，刷不动了
