C语言网：2022年第十三届蓝桥杯大赛软件类省赛Python大学B组真题https://www.dotcpp.com/oj/train/1034/

只能说这波有点混，我估计 48.5 分左右 (满分 150)。广东总共 78 个省一，我只排到了第 33 (42.3%)

考前主要在力扣上面练，考试时发现并无卵用，打蓝桥杯还是要以真题为主

考完没有第一时间写题解也是因为考试时有很多不懂的，现在已经是个要打国赛的人了，重新做一下

A：排列字母  100🏆

【问题描述】

        小蓝要把一个字符串中的字母按其在字母表中的顺序排列。

        例如，LANQIAO 排列后为 AAILNOQ。

        又如，GOODGOODSTUDYDAYDAYUP 排列后为 AADDDDDGGOOOOPSTUUYYY

        请问对于以下字符串，排列之后字符串是什么?

        WHERETHEREISAWILLTHEREISAWAY

【解析及代码】

string = 'WHERETHEREISAWILLTHEREISAWAY'
print(''.join(sorted(string)))

You can do it if you have hands.

B：寻找整数  100🏆

【问题描述】

        有一个不超过  的正整数 n，知道这个数除以2至49后的余数如下表所示，求这个正整数最小是多少。

【解析及代码】

首先按照余数进行分类，求出余数相同的除数的最小公倍数

例如，余数为 1 的除数有 2, 4, 8, 41，这四个数的最小公倍数为 328，则当除数为 328 时余数也为 1

data = [0, 0, 1, 2, 1, 4, 5, 4, 1, 2, 9, 0, 5, 10,
        11, 14, 9, 0, 11, 18, 9, 11, 11, 15, 17, 9,
        23, 20, 25, 16, 29, 27, 25, 11, 17, 4, 29, 22,
        37, 23, 9, 1, 11, 11, 33, 29, 15, 5, 41, 46]

# Python 3.9.0 版本特有
from math import lcm

mod_list = list(enumerate(data))[2:]
# 关于余数的字典
res_dict = {res: [] for res in data}
for mod, res in mod_list:
    res_dict[res].append(mod)

# 按余数查询的最小公倍数字典
for res in res_dict:
    res_dict[res] = lcm(*res_dict[res])
print(res_dict)

得到关于余数的字典如下 

{0: 187, 1: 328, 2: 9, 4: 35, 5: 564, 9: 400, 10: 13, 11: 59598, 14: 15, 18: 19, 15: 46, 17: 408, 23: 78, 20: 27, 25: 224, 16: 29, 29: 180, 27: 31, 22: 37, 37: 38, 33: 44, 41: 48, 46: 49}

因为最大的除数是 59598，所以作为搜索步长，其对应的余数 11 作为初始值

# 当前的结果
result = 11
# 当前的最小公倍数
pace = res_dict.pop(11)

如果用 for 循环进行搜索的话，那么

假如对某一 a 存在：，此时又满足 

为了保持在更新的过程中仍然保持这两个条件，搜索步长应该更新为 (lcm 为求最小公倍数的函数)：

即此时的 p 既可被原本的 59598 整除，也可以被 328 整除，不影响原来的余数

for res in res_dict:
    mod = res_dict[res]
    while result % mod != res:
        # 当前结果求余结果不满足条件时
        result += pace
    else:
        # 更新搜索步长
        pace = lcm(pace, mod)

print(result)

答案：2022040920220409

C：纸张尺寸  100🏆

【问题描述】

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

【解析及代码】 

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：蜂巢  100🏆

【问题描述】

【评测用例规模与约定】

【解析及代码】

基本的思路是，把 (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：消除游戏  87🏆

【问题描述】

【评测用例规模与约定】

【解析及代码】 

import itertools as it

string = input()

for _ in range(pow(2, 63)):
    # 保存相邻字符的比较结果
    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

print(string if string else 'EMPTY')

时间超限，刷不上去了

G：全排列的价值  100🏆

【问题描述】

【评测用例规模与约定】

以 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 = value * i % mod

print(round(value))

在阶乘的时候一定要用 for 循环边乘边求余数，不要用 math 库的 factorial

H：技能升级  52🏆

【问题描述】

【评测用例规模与约定】

【解析及代码】 

这份代码的瓶颈主要在于 M 太大了，下面是比较简单的思路

读取输入之后，对  进行排序，然后每次都取出列表末端的技能 (即最大值)

将技能取出并使用后，修改技能点数，利用 bisect 库的二分法放回技能列表

import bisect

n, m = map(int, input().split())
skill = [list(map(int, input().split())) for _ in range(n)]
skill.sort()

answer = 0
for i in range(m):
    if skill[-1][0] <= 0: break
    answer += skill[-1][0]
    # 修改技能点数, 并用二分法插入
    skill[-1][0] -= skill[-1][1]
    bisect.insort(skill, skill.pop(-1))

print(answer)

I：最长不下降子序列

【问题描述】

【评测用例规模与约定】

【解析及代码】

我有个可以找到最优解的思路，不过要写的话代码太多，懒得做。从左到右做个递增序列的搜索，从右到左做个递增序列的搜索，变换成两个递增序列的拼接问题

挂个 C++ 大佬的满分做法：Link ~

J：最优清零方案  24🏆

【问题描述】

【评测用例规模与约定】

【解析及代码】

从测试结果来看，只对了一部分样例，这个并不是最优的做法，接下来讲讲怎么一本正经的骗分

对于 3 1 2 4 5，操作长度为 3 时，最优的操作应当是：

1. 操作二 1 次：2 0 1 4 5
2. 操作一 2 次：0 0 1 4 5
3. 操作二 1 次：0 0 0 3 4
4. 操作二 3 次：0 0 0 0 1
5. 操作一 1 次：0 0 0 0 0

如果将两种操作合并成“链式减 1”，则上述操作等价于：

1. 操作 3 次：[0, 1, 2] 位置减去 [3, 1, 1] -> 0 0 1 4 5
2. 操作 1 次：[2, 3, 4] 位置减去 [1, 1, 1] -> 0 0 0 3 4
3. 操作 3 次：[3, 4] 位置减去 [3, 3] -> 0 0 0 0 1
4. 操作 1 次：[4] 位置减去 [1] -> 0 0 0 0 0

在某一轮链式减 1 中，该区间首元素的数值即为操作数 (直接将首元素置 0)，其它元素的减少量不高于上一位的减少量、不高于本身数值

n, k = map(int, input().split())
seq = list(map(int, input().split()))

# 记录操作次数
time, pin = 0, 0
while pin < n:
    if seq[pin]:
        # 操作次数 = 当前 pin 指向的值
        time += seq[pin]
        # 链式操作量: 必是降序
        sub_list = [seq[pin]]
        seq[pin] = 0
        # 操作不超过限制个数的数
        for next_ in range(pin + 1, min([pin + k, n])):
            # 计算可减少的量
            sub = min([sub_list[-1], seq[next_]])
            if sub == 0: break
            # 存储减少量, 并减少
            sub_list.append(sub)
            seq[next_] -= sub
    pin += 1

print(time)