代码收藏家 2023年蓝桥杯Python大学B组真题解析
写在前面
⚠️写这份题解之前我是没有看过任何版本的题解，以下代码均是我独立AC后把代码记录到该题解内。
🚀代码提交后是能保证100%通关的，并且配有注释，可以放心食用。
C题 松散子序列🌟🌟🌟（10分）
题目描述
给定一个仅含小写字母的字符串 s ，假设 s 的一个子序列 t 的第 i 个字符 对应了原字符串中的第 pi 个字符。我们定义 s 的一个松散子序列为：对于 i > 1 总是有 pi − pi−1 ≥ 2 。设一个子序列的价值为其包含的每个字符的价值之和 ( a ∼ z 分别为 1 ∼ 26 ) 。
求 s 的松散子序列中的最大价值。
输入格式
输入一行包含一个字符串 s 。
输出格式
输出一行包含一个整数表示答案。
样例输入
azaazaz
样例输出
78
代码解析
s = [0] + list(input())
for i in range(1, len(s)): s[i] = ord(s[i]) - 96
dp = [0] * (len(s) + 1) # dp[i]表示前i个数的最大价值
dp[1] = s[1]
for i in range(2, len(s)):
# 第i个数不选的话从dp[i-1]直接递推过来，不选的话从dp[i-2]递推过来，满足选的数都至少间隔1个。
dp[i] = max(dp[i - 1], dp[i - 2] + s[i])
print(dp[len(s) - 1])
D题 管道🌟🌟🌟（10分）
题目描述
有一根长度为 len 的横向的管道，该管道按照单位长度分为 len 段，每一段的中央有一个可开关的阀门和一个检测水流的传感器。
一开始管道是空的，位于 Li 的阀门会在 Si 时刻打开，并不断让水流入管道。
对于位于 Li 的阀门，它流入的水在 Ti (Ti ≥ Si) 时刻会使得从第 Li−(Ti−Si) 段到第 Li + (Ti − Si) 段的传感器检测到水流。 求管道中每一段中间的传感器都检测到有水流的最早时间。
输入格式
输入的第一行包含两个整数 n, len，用一个空格分隔，分别表示会打开的阀门数和管道长度。
接下来 n 行每行包含两个整数 Li , Si，用一个空格分隔，表示位于第 Li 段 管道中央的阀门会在 Si 时刻打开。
输出格式
输出一行包含一个整数表示答案。
样例输入
3 10
1 1
6 5
10 2
样例输出
5
代码解析
这道题满足答案的二段性，也是最大值最小化问题，可以用二分法求解。
n, ll = map(int, input().split())
a = []
for _ in range(n):
a.append(list(map(int, input().split())))
def check(ans):
res = [] # res存储管道的灌溉区间
for i in range(n):
if ans < a[i][1]: continue
l = max(1, a[i][0] - (ans - a[i][1]))
r = min(ll, a[i][0] + (ans - a[i][1]))
res.append([l, r])
res.sort()
# 如果最左起点不能灌溉到1管道则False
if res[0][0] > 1: return False
rr = res[0][1] # 初始化最右灌溉区域
# 合并区间
for i in range(1, len(res)):
# 如果该区间和上一区间没有交集且不连续则False
if res[i][0] > rr and res[i][0] != rr + 1: return False
else: rr = max(res[i][1], rr) # 更新最右灌溉区域
if rr < ll: return False # 如果最右灌溉区域达不到Len则False
return True
# r必须开到2e9
l, r = 1, 2 * 10**9
while l + 1 != r:
mid = (l + r) // 2
if check(mid):
r = mid
else: l = mid
print(r)
E题 保险箱🌟🌟🌟✨（15分）
题目描述
小蓝有一个保险箱，保险箱上共有 n 位数字。
小蓝可以任意调整保险箱上的每个数字，每一次操作可以将其中一位增加 1 或减少 1 。
当某位原本为 9 或 0 时可能会向前（左边）进位/退位，当最高位（左边第 一位）上的数字变化时向前的进位或退位忽略。
例如：
00000 的第 5 位减 1 变为 99999 ；
99999 的第 5 位减 1 变为 99998 ；
00000 的第 4 位减 1 变为 99990 ；
97993 的第 4 位加 1 变为 98003 ；
99909 的第 3 位加 1 变为 00009 。
保险箱上一开始有一个数字 x，小蓝希望把它变成 y，这样才能打开它，问 小蓝最少需要操作的次数。
输入格式
输入的第一行包含一个整数 n 。
第二行包含一个 n 位整数 x 。
第三行包含一个 n 位整数 y 。
输出格式
输出一行包含一个整数表示答案。
样例输入
5
12349
54321
样例输出
11
代码解析
从低位到高位依此变换，变换数字有三种情况：进位（高位+1）、退位（高位-1）、不进位也不退位。
n = int(input())
x = [0] + list(map(int, list(input())))[::-1]
y = [0] + list(map(int, list(input())))[::-1]
# dp[i][j]表示i～n个数已经相等，j存第i个数相等的方式
dp = [[0] * 3 for i in range(n + 1)]
dp[1][0] = abs(x[1] - y[1]) # 不进退位
dp[1][1] = 10 - x[1] + y[1] # 进位
dp[1][2] = 10 - y[1] + x[1] # 退位
for i in range(2, n + 1):
dp[i][0] = min(dp[i - 1][0] + abs(x[i] - y[i]), dp[i - 1][1] + abs(x[i] - y[i] + 1), dp[i - 1][2] + abs(x[i] - y[i] - 1))
dp[i][1] = min(dp[i - 1][0] + 10 - x[i] + y[i], dp[i - 1][1] + 10 - (x[i] + 1) + y[i], dp[i - 1][2] + 10 - (x[i] - 1) + y[i])
dp[i][2] = min(dp[i - 1][0] + 10 - y[i] + x[i], dp[i - 1][1] + 10 - y[i] + (x[i] + 1), dp[i - 1][2] + 10 - y[i] + (x[i] - 1))
print(min(dp[n][0], dp[n][1], dp[n][2]))
F题 树上选点🌟🌟🌟🌟（15分）
题目描述
给定一棵树，树根为 1，每个点的点权为 Vi 。
你需要找出若干个点 Pi，使得：
-
每两个点 Px Py 互不相邻；
-
每两个点 Px Py 与树根的距离互不相同；
-
找出的点的点权之和尽可能大。
请输出找到的这些点的点权和的最大值。
输入格式
输入的第一行包含一个整数 n 。
第二行包含 n − 1 个整数 Fi ，相邻整数之间使用一个空格分隔，分别表示 第 2 至 n 个结点的父结点编号。
第三行包含 n 个整数 Vi，相邻整数之间使用一个空格分隔，分别表示每个结点的点权。
输出格式
输出一行包含一个整数表示答案。
样例输入
5
1 2 3 2
2 1 9 3 5
样例输出
11
代码解析
⚠️pypy3提交通过可以达到100%。
这题很难，需要用到树形dp，用state数组记录每一层的选了结点最大值a、不选结点的最大值b、选了结点和a非同父结点的最大值。参考代码理解，解法应该是全网最优解了。
n = int(input())
fa = [0, 0] + list(map(int, input().split()))
v = [0] + list(map(int, input().split())) # 存1~n个结点的值
dep = [0] * (n + 1) # 每个结点的深度
dep_node = [[] for i in range(n + 1)] # 存每个深度中的结点编号
deep_max = 0 # 深度的最大值
for i in range(1, n + 1): # 求每个深度有哪些结点
dep[i] = dep[fa[i]] + 1
deep_max = max(deep_max, dep[i])
dep_node[dep[i]].append(i)
dp = [[0] * 2 for i in range(n + 1)] # 表示i结点选或不选的情况dp[i][0/1]
state = [0, 0, 0] # [不选该层结点的最大值结点,选该层结点的最大值结点,选该层结点非最大值同父最大值结点]
for i in range(deep_max, 0, -1): # 从deep_max~1深度,自下向上
for j in dep_node[i]: # j表示i深度的结点
dp[j][0] = max(dp[state[0]][0], dp[state[1]][1])
if fa[state[1]] == j: # 如果下一层的最大值结点是j的子结点, 则选择max(非j子结点的最大值, 不选的最大值结点)
dp[j][1] = v[j] + max(dp[state[0]][0], dp[state[2]][1])
else: # max(下一层的最大值结点, 不选的最大值结点)
dp[j][1] = v[j] + max(dp[state[0]][0], dp[state[1]][1])
state = [0, 0, 0]
for j in dep_node[i]: # 求深度为i的dp[j][0]和dp[j][1]的最大值
if dp[state[0]][0] < dp[j][0]:
state[0] = j
if dp[state[1]][1] < dp[j][1]:
state[1] = j
for j in dep_node[i]: # 求i深度下和选最大值结点非共同父结点的次最大值结点
if fa[state[1]] != fa[j] and dp[state[2]][1] < dp[j][1]:
state[2] = j
print(max(dp[1][0], dp[1][1]))
I题 异或和🌟🌟🌟🌟（25分）
题目描述
给一棵含有 n 个结点的有根树，根结点为 1 ，编号为 i 的点有点权 ai（i ∈ [1, n]）。现在有两种操作，格式如下：
• 1 x y 该操作表示将点 x 的点权改为 y 。
• 2 x 该操作表示查询以结点 x 为根的子树内的所有点的点权和。
现有长度为 m 的操作序列，请对于每个第二类操作给出正确的结果。
输入格式
输入的第一行包含两个正整数 n, m ，用一个空格分隔。
第二行包含 n 个整数 a1, a2, …, an ，相邻整数之间使用一个空格分隔。
接下来 n − 1 行，每行包含两个正整数 ui , vi ，表示结点 ui 和 vi 之间有一条边。
接下来 m 行，每行包含一个操作。
输出格式
输出若干行，每行对应一个查询操作的答案。
样例输入
4 5
1 2 3 4
1 2
1 3
2 4
2 1
1 1 0
2 1
2 2
样例输出
4
5
6
6
代码解释
n, m = map(int, input().split())
v = [0] + list(map(int, input().split()))
g = [[] for _ in range(n + 1)]
for _ in range(n - 1):
u, va = map(int, input().split())
g[u].append(va)
g[va].append(u)
tree = [0] * (n + 1) # 用树状数组求异或和
a = [[0, 0] for _ in range(n + 1)] # 存dfs序
cnt = 0
def dfs(node, fa): # 求dfs序
global cnt
cnt += 1
a[node][0] = cnt
for i in g[node]:
if i != fa:
dfs(i, node)
a[node][1] = cnt
dfs(1, 0)
def lowbit(x):
return x & (-x)
def update(x, d):
while x <= n:
tree[x] ^= d
x += lowbit(x)
def query(x):
ans = 0
while x:
ans ^= tree[x]
x -= lowbit(x)
return ans
for i in range(1, n + 1):
# 子结点的入序和出序一定是在根结点入序和出序之间
update(a[i][0], v[i])
for _ in range(m):
o = list(map(int, input().split()))
if o[0] == 2:
# 从根结点的入序到出序之间的异或和
print(query(a[o[1]][1]) ^ query(a[o[1]][0] - 1))
else:
x, y = o[1], o[2]
update(a[x][0], v[x] ^ y)
v[x] = y
