C语言网：2022年第十三届蓝桥杯大赛软件类省赛Python大学B组真题https://www.dotcpp.com/oj/train/1034/
只能说这波有点混，我估计 48.5 分左右。广东总共 78 个省一，我只排到了第 33 (42.3%)
考前主要在力扣上面练，考试时发现并无卵用，打蓝桥杯还是要以真题为主
考完没有第一时间写题解也是因为考试时有很多不懂的，现在已经是个要打国赛的人了，重新做一下 (目前得分：91.75)
| 填空题 | 编程题 | |||
| 5 分 | 10 分 | 15 分 | 20 分 | 25 分 |
| A、B | C、D | E、F | G、H | I、J |
C：纸张尺寸
【问题描述】
在 ISO 国际标准中定义了
A0
纸张的大小为
1189
mm
×
841
mm
，将
A0
纸沿长边对折后为 A1
纸，大小为
841
mm
×
594
mm
，在对折的过程中长度直接取下整（实际裁剪时可能有损耗）。将 A1
纸沿长边对折后为
A2
纸，依此类推。
输入纸张的名称，请输出纸张的大小。
【输入格式】
输入一行包含一个字符串表示纸张的名称，该名称一定是 A0
、
A1
、
A2
、A3、
A4
、
A5
、
A6
、
A7
、
A8
、
A9
之一。
【输出格式】
输出两行，每行包含一个整数，依次表示长边和短边的长度。
【样例】
【输入格式】
输入一行包含一个字符串表示纸张的名称，该名称一定是 A0
、
A1
、
A2
、A3、
A4
、
A5
、
A6
、
A7
、
A8
、
A9
之一。
【输出格式】
输出两行，每行包含一个整数，依次表示长边和短边的长度。
【样例】
【样例】
| 输入 | 输出 |
| A0 | 1189 841 |
| A1 | 841 594 |
require = int(input()[1])
size = [(1189, 841)]
# 当不是 A0
if require:
for time in range(require):
# 原长边、原短边
last_a, last_b = size[time]
# 原短边 -> 现长边
now_a = last_b
# 长边对折
now_b = last_a // 2
# 记录当前尺寸
size.append((now_a, now_b))
print(*size[require], sep='n')
很简单，满分结束
D：数位排序 【问题描述】 小蓝对一个数的数位之和很感兴趣，今天他要按照数位之和给数排序。当两个数各个数位之和不同时，将数位和较小的排在前面，当数位之和相等时，将数值小的排在前面。 例如，2022 排在 409 前面，因为 2022 的数位之和是 6 ，小于 409 的数位之和 13 。 又如，6 排在 2022 前面，因为它们的数位之和相同，而 6 小于 2022 。 给定正整数 n， m ，请问对 1 到 n 采用这种方法排序时，排在第 m 个的元素是多少？ 【输入格式】 输入第一行包含一个正整数 n 。 第二行包含一个正整数 m 。 【输出格式】 输出一行包含一个整数，表示答案。 【样例】
| 输入 | 输出 | 说明 |
| 13 5 | 3 | 1 到 13 的排序为： 1, 10, 2, 11, 3, 12, 4, 13, 5, 6, 7, 8, 9。 第 5 个数为 3。 |
【评测用例规模与约定】
| 30% | 1 ≤ m ≤ n ≤ 300 |
| 50% | 1 ≤ m ≤ n ≤ 1000 |
| 100% | 1 ≤ m ≤ n ≤ |
from heapq import nsmallest n, index = map(int, [input() for _ in range(2)]) # 求值函数: 所有数位之和 key_fun = lambda num: sum(map(int, str(num))) # 使用堆排, 取前 n 小 print(nsmallest(index, range(1, n + 1), key=key_fun)[-1])
很简单，满分结束
E：蜂巢 【问题描述】 蜂巢由大量的六边形拼接而成，定义蜂巢中的方向为：0 表示正西方向， 1 表示西偏北 60° ， 2 表示东偏北 60° ， 3 表示正东， 4 表示东偏南 60° ， 5 表示西偏南 60° 。 对于给定的一点 O，我们以 O 为原点定义坐标系，如果一个点 A 由 O 点 先向 d 方向走 p 步再向 ( d + 2) mod 6 方向（ d 的顺时针 120° 方向）走 q 步到达，则这个点的坐标定义为 ( d , p , q ) 。在蜂窝中，一个点的坐标可能有多种。 下图给出了点 B(0 , 5 , 3) 和点 C (2 , 3 , 2) 的示意。 给定点 (d 1 , p 1 , q 1 ) 和点 ( d 2 , p 2 , q 2 ) ，请问他们之间最少走多少步可以到达？ 【输入格式】 输入一行包含 6 个整数 d 1 , p 1 , q 1 , d 2 , p 2 , q 2 表示两个点的坐标，相邻两个整 数之间使用一个空格分隔。 【输出格式】 输出一行包含一个整数表示两点之间最少走多少步可以到达。 【样例】| 输入 | 输出 |
| 0 5 3 2 3 2 | 7 |
| 25% | p1, p2 ≤ |
| 50% | p1, p2 ≤ |
| 75% | p1, p2 ≤ |
| 100% | 0 ≤ d1, d2 ≤ 5，0 ≤ q1 < p1 ≤ ，0 ≤ q2 < p2 ≤ |
基本的思路是，把 (d, p, q) 坐标转换成 xy 坐标，因为 xy 坐标可叠加
SQRT_3 = 3 ** 0.5
def dir_tran(direct):
''' direct: 方向
return: 单位步长的分量'''
if direct == 0:
x, y = -1, 0
elif direct == 1:
x, y = -1 / 2, SQRT_3 / 2
elif direct == 2:
x, y = 1 / 2, SQRT_3 / 2
else:
x, y = dir_tran(direct % 3)
x, y = -x, -y
return x, y
def loc_tran(d, p, q):
''' 将 (d, p, q) 坐标转换为 (x, y) 坐标'''
# 沿 d 方向走 p 步
x1, y1 = dir_tran(d)
x1, y1 = x1 * p, y1 * p
# 沿 (d+2)%6 方向走 q 步
x2, y2 = dir_tran((d + 2) % 6)
x2, y2 = x2 * q, y2 * q
return x1 + x2, y1 + y2
d1, p1, q1, d2, p2, q2 = map(int, input().split())
x1, y1 = loc_tran(d1, p1, q1)
x2, y2 = loc_tran(d2, p2, q2)
# 求出等价的距离向量
x, y = abs(x1 - x2), abs(y1 - y2)
转换成 xy 坐标后，可求出距离向量 (就是坐标差值)，记为 (x, y)。因为研究多少步可以走完 (3, -4) 这段距离和研究多少步可以走完 (3, 4) 这段距离是等价的，故对该距离向量取绝对值
如果 ，则从某一点回到 x 轴需要走 n 步，同时会在 x 方向上产生最多 步的移动。当然，因为在回到 x 轴的过程中，可以向左下、右下移动，所以这个 是最多，而不是一定
蓝色的线走了 6 步，绿色的线走了 5 步，差别就是绿色的线在回到 x 轴的过程中调整过方向
总步数 = 回到 x 轴的步数 + 在 x 轴上移动的步数
# 回到 x 轴所需的步数 total_pace = y / SQRT_3 * 2 # 回到 x 轴时, 在 x 方向上产生的最大偏移量 x_move = y / SQRT_3 # 在 x 方向上还需移动的步数 total_pace += max([0, x - x_move]) print(int(round(total_pace)))
满分结束
F：消除游戏 【问题描述】 在一个字符串 S 中，如果 且 ，则称 和 为边缘字符。如果 且 ，则 和 也称为边缘字符。其它的字符都不是边缘字符。 对于一个给定的串 S ，一次操作可以一次性删除该串中的所有边缘字符（操作后可能产生新的边缘字符）。 请问经过 次操作后，字符串 S 变成了怎样的字符串，如果结果为空则输出 EMPTY 。 【输入格式】 输入一行包含一个字符串 S 。 【输出格式】 输出一行包含一个字符串表示答案，如果结果为空则输出 EMPTY 。 【样例】| 输入 | 输出 |
| edda | EMPTY |
| sdfhhhhcvhhxcxnnnnshh | s |
| 25% | |S | ≤ ，其中 |S | 表示 S 的长度 |
| 50% | |S | ≤ |
| 75% | |S | ≤ |
| 100% | |S | ≤ ，S 中仅含小写字母 |
import itertools as it
string = input()
for _ in range(2 << 64):
# 保存相邻字符的比较结果
eq_flag = [string[i] == string[i + 1]
for i in range(len(string) - 1)]
# 是否保留该位置的字符
keep_flag = [True] * len(string)
# 是否不再出现边缘字符?
all_done_flag = True
# 标记边缘字符
for i in range(len(string) - 2):
# S[i] == S[i+1], S[i+1] != S[i+2], 除去 S[i+1] S[i+2]
if eq_flag[i]:
if not eq_flag[i + 1]:
keep_flag[i + 1] = keep_flag[i + 2] = False
all_done_flag = False
# S[i] != S[i+1], S[i+1] == S[i+2], 除去 S[i] S[i+1]
else:
if eq_flag[i + 1]:
keep_flag[i] = keep_flag[i + 1] = False
all_done_flag = False
# 根据 keep_flag 进行保留
string = ''.join(it.compress(string, keep_flag))
# 退出: keep_flag 全部为 True / 字符串长度 < 3
if all_done_flag or len(string) < 3:
break
if string:
print(string)
else:
print('EMPTY')
时间超限 75 分，刷不上去了
G：全排列的价值 【问题描述】 对于一个排列 ，定义价值 为 至 中小于 的数 的个数，即 A 的价值为 。 给定 n ，求 1 至 n 的全排列中所有排列的价值之和。 【输入格式】 输入一行包含一个整数 n 。 【输出格式】 输出一行包含一个整数表示答案，由于所有排列的价值之和可能很大，请 输出这个数除以 998244353 的余数。 【样例】| 输入 | 输出 | 说明 |
| 3 | 9 | (1 , 2 , 3) : 0 + 1 + 2 = 3 ； (1 , 3 , 2) : 0 + 1 + 1 = 2 ； (2 , 1 , 3) : 0 + 0 + 2 = 2 ； (2 , 3 , 1) : 0 + 1 + 0 = 1 ； (3 , 1 , 2) : 0 + 0 + 1 = 1 ； (3 , 2 , 1) : 0 + 0 + 0 = 0 ； 故总和为 3 + 2 + 2 + 1 + 1 = 9 |
| 2022 | 593300958 |
| 40% | n ≤ 20 |
| 70% | n ≤ 5000 |
| 100% | 2 ≤ n ≤ |
以 4 的全排列为例，当第一位是 2 时，总共有 种排列方式。而且每一种排列方式下必有“3 4”大于 2，贡献了 2 × 6 = 12 的价值，同理可得：
- 第一位是 1：3 × 6 = 18
- 第一位是 2：2 × 6 = 12
- 第一位是 3：1 × 6 = 6
- 第一位是 4：0 × 6 = 0
总共是
计算完第一位产生的贡献后，剔除第一位，剩下“1 3 4”全排列产生的贡献，等价为“1 2 3”全排列产生的贡献
当现在的第一位为 1 时，总共有 种排列方式：
- 现第一位是 1：2 × 2 = 4
- 现第一位是 2：1 × 2 = 2
- 现第一位是 3：0 × 2 = 0
总共是
剔除第二位，剩下 3 4，正反两种排列总共贡献 1。全排列所有末两位的总贡献即为
答案为 36 + 24 + 12 = 72
对于 4，全排列的价值为：
对于 n，全排列的价值为：
n = int(input())
mod = 998244353
value = n * (n - 1) / 4 % mod
for i in range(1, n + 1):
value *= i
value %= mod
print(int(round(value)))
满分结束，在阶乘的时候一定要用 for 循环边乘边求余数，不要用 math 库的 factorial
H：技能升级 【问题描述】 小蓝最近正在玩一款 RPG 游戏。他的角色一共有 N 个可以加攻击力的技能。其中第 i 个技能首次升级可以提升 点攻击力，以后每次升级增加的点数都会减少 。 ( 上取整 ) 次之后，再升级该技能将不会改变攻击力。 现在小蓝可以总计升级 M 次技能，他可以任意选择升级的技能和次数。请你计算小蓝最多可以提高多少点攻击力？ 【输入格式】 输入第一行包含两个整数 N 和 M 。 以下 N 行每行包含两个整数 和 。 【输出格式】 输出一行包含一个整数表示答案。 【样例】| 输入 | 输出 |
| 3 6 10 5 9 2 8 1 | 47 |
| 40% | 1 ≤ N, M ≤ 1000 |
| 60% | 1 ≤ N ≤ , 1 ≤ M ≤ |
| 100% | 1 ≤ N ≤ ，1 ≤ M ≤ 2 × ，1 ≤ Ai, Bi ≤ |
class Jineng:
def __init__(self, num, delta):
# 技能当前的增益
self.value = num
# 每使用一次技能产生的衰减值
self.delta = delta
def use(self):
# 使用之后, 出现衰减
self.value -= self.delta
# 边界处理
if self.value < 0:
self.value = 0
先写一个对象来存储技能的信息，并用 use 函数实现技能增益衰减
将技能依照 value 属性降序排列，并在每次使用技能之后 (value 发生改变)，重新存放技能
num, oper_time = map(int, input().split())
# 技能列表
ability = [Jineng(*map(int, input().split())) for _ in range(num)]
benefit = 0
for _ in range(oper_time):
# 贪心地选取最佳的
best_choose = max(ability, key=lambda j: j.value)
# 当增益不为 0
if best_choose.value:
# 使用并更新技能
benefit += best_choose.value
best_choose.use()
else:
break
print(benefit)
时间超限 35 分，点到为止
I：最长不下降子序列 【问题描述】 给定一个长度为 N 的整数序列：。现在你有一次机会，将其中连续的 K 个数修改成任意一个相同值。请你计算如何修改可以使修改后的数列的最长不下降子序列最长，请输出这个最长的长度。 最长不下降子序列是指序列中的一个子序列，子序列中的每个数不小于在它之前的数。 【输入格式】 输入第一行包含两个整数 N 和 K 。 第二行包含 N 个整数 。 【输出格式】 输出一行包含一个整数表示答案。 【样例】| 输入 | 输出 |
| 5 1 1 4 2 8 5 | 4 |
| 20% | 1 ≤ K ≤ N ≤ 100 |
| 30% | 1 ≤ K ≤ N ≤ 1000 |
| 50% | 1 ≤ K ≤ N ≤ 10000 |
| 100% | 1 ≤ K ≤ N ≤ ，1 ≤ Ai ≤ |
我有个可以找到最优解的思路，不过要写的话代码太多，懒得做。从左到右做个递增序列的搜索，从右到左做个递增序列的搜索，变换成两个递增序列的拼接问题
以下是我 10 分的解法，只能应付简单情况
from copy import copy
length, oper_num = map(int, input().split())
dp = list(map(int, input().split()))
class State:
def __init__(self, num, idx):
self.last_value = num
self.last_idx = idx
# 上一个数字的索引、值
self.max_empty = min([idx, oper_num])
self.len = 1
# 跳跃长度、已有长度
def is_legal(self, other):
''' 合法连接'''
return self.last_value <= other
def update(self, num, idx):
''' 根据新添加的数字, 更新自身参数'''
self.max_empty = max([self.max_empty, idx - self.last_idx - 1])
# 原跳跃长度 / 新连接间隔
self.max_empty = min([self.max_empty, oper_num])
# 最优跳跃长度 / 修改限制
self.last_value = num
self.last_idx = idx
self.len += 1
dp[0] = State(dp[0], 0)
for cur in range(1, len(dp)):
cur_num = dp[cur]
cur_state = State(cur_num, cur)
cur_length = cur_state.len
# 生成当前状态, 比较时使用 原长度
for last in range(cur):
last_state = copy(dp[last])
# 获取上一个状态
if last_state.is_legal(cur_num):
# 判断是否递增
last_state.update(cur_num, cur)
# 连接并传递状态
last_length = last_state.len
# 现状态的 原长度
if last_length > cur_length or (
last_length == cur_length and last_state.max_empty > cur_state.max_empty):
# 原长度更长 | 原长度等长时 跳跃长度更长
cur_state = last_state
# 状态替换
dp[cur] = cur_state
state = dp[-1]
result = state.len + state.max_empty
print(result)
J：最优清零方案
【问题描述】
给定一个长度为 N
的数列 。现在小蓝想通过若干次操作将这个数列中每个数字清零。
每次操作小蓝可以选择以下两种之一：
1. 选择一个大于
0
的整数，将它减去
1
；
2. 选择连续
K
个大于
0
的整数，将它们各减去
1
。
小蓝最少经过几次操作可以将整个数列清零？
【输入格式】
输入第一行包含两个整数 N
和
K
。
第二行包含 N
个整数 。
【输出格式】
输出一个整数表示答案。
【样例】
| 输入 | 输出 |
| 4 2 1 2 3 4 | 6 |
| 20% | 1 ≤ K ≤ N ≤ 10 |
| 40% | 1 ≤ K ≤ N ≤ 100 |
| 50% | 1 ≤ K ≤ N ≤ 1000 |
| 60% | 1 ≤ K ≤ N ≤ 10000 |
| 70% | 1 ≤ K ≤ N ≤ 100000 |
| 100% | 1 ≤ K ≤ N ≤ 1000000, 0 ≤ Ai ≤ 1000000 |
对于 3 1 2 4 5，操作长度为 3 时，最优的操作应当是：
- 操作二 1 次：2 0 1 4 5
- 操作一 2 次：0 0 1 4 5
- 操作二 1 次：0 0 0 3 4
- 操作二 3 次：0 0 0 0 1
- 操作一 1 次：0 0 0 0 0
如果将两种操作合并成“链式减 1”，则上述操作等价于：
- 操作 3 次：[0, 1, 2] 位置减去 [3, 1, 1] -> 0 0 1 4 5
- 操作 1 次：[2, 3, 4] 位置减去 [1, 1, 1] -> 0 0 0 3 4
- 操作 3 次：[3, 4] 位置减去 [3, 3] -> 0 0 0 0 1
- 操作 1 次：[4] 位置减去 [1] -> 0 0 0 0 0
在某一轮链式减 1 中，该区间首元素的数值即为操作数 (直接将首元素置 0)，其它元素的减少量不高于上一位的减少量、不高于本身数值
length, oper_num = map(int, input().split())
seq = list(map(int, input().split()))
# 记录操作次数
time = 0
pin = 0
while pin < length:
if seq[pin]:
# 操作次数 = 当前 pin 指向的值
time += seq[pin]
# 链式操作量: 必是降序
sub_list = [seq[pin]]
seq[pin] = 0
# 操作不超过限制个数的数
for next_ in range(pin + 1, min([pin + oper_num, length])):
# 计算可减少的量
sub = min([sub_list[-1], seq[next_]])
if sub:
# 存储减少量, 并减少
sub_list.append(sub)
seq[next_] -= sub
else:
break
# 步进
pin += 1
print(time)
时间超限 24 分，跪了跪了
