写在前面
⚠️写这份题解之前我是没有看过任何版本的题解，以下代码均是我独立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]) - 96dp = [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 101 16 510 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必须开到2e9l, r = 1, 2 * 10**9while l + 1 != r: mid = (l + r) // 2 if check(mid): r = mid else: l = midprint(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 。
输出格式
输出一行包含一个整数表示答案。
样例输入
51234954321样例输出
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，相邻整数之间使用一个空格分隔，分别表示每个结点的点权。
输出格式
输出一行包含一个整数表示答案。
样例输入
51 2 3 22 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] = jprint(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 51 2 3 41 21 32 42 11 1 02 12 2样例输出
4566代码解释
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 = 0def 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] = cntdfs(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 ansfor 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