今年蓝桥杯告一段落，检查的时候发现好多会写的题都犯了粗心的错误，还有时间安排上死磕了一些不会的题，希望能给后人一些警示。
4.25update：拿了广东省第十，挺开心的hh。这篇题解有部分错误，等我有空再重新更新一版

C题：松散子序列

问题描述

给定一个仅含小写字母的字符串 s ，假设 s 的一个子序列 t 的第 i 个字符 对应了原字符串中的第 pi 个字符。我们定义 s 的一个松散子序列为：对于 i > 1 总是有 pi − pi−1 ≥ 2 。设一个子序列的价值为其包含的每个字符的价值之和 ( a ∼ z 分别为 1 ∼ 26 ) 。 求 s 的松散子序列中的最大价值。

输入格式

输入一行包含一个字符串 s 。

输出格式

输出一行包含一个整数表示答案。

样例输入

azaazaz

样例输出

78

思路

这个题咋一看很吓人，但其实仔细琢磨就可以知道题面含义就是一个字母选了之后，下一个不能选，也就是说只能隔一个选。那么就是很经典的选不选问题，直接用线性DP解决。依次枚举每个位置的字母选还是不选，最后求所有位置的最大值即可。

代码

N = 1000010
dp = [0 for i in range(N)]
a = input()
# 第一个位置选的价值
dp[1] = ord(a[0]) - ord('a') + 1
# 第二个位置选的价值
dp[2] = ord(a[1]) - ord('a') + 1
# 从第三个位置开始枚举
for i in range(3, len(a) + 1):
    w = ord(a[i - 1]) - ord('a') + 1
    dp[i] = max(dp[i - 2] + w, dp[i - 1])

print(max(dp[:len(a) + 1]))

F题：树上选点

问题描述

给定一棵树，树根为 1，每个点的点权为 Vi 。你需要找出若干个点 Pi，使得：

1. 每两个点 Px Py 互不相邻；

2. 每两个点 Px Py 与树根的距离互不相同；

3. 找出的点的点权之和尽可能大。

请输出找到的这些点的点权和的最大值。

输入格式

输入的第一行包含一个整数 n 。

第二行包含 n − 1 个整数 Fi ，相邻整数之间使用一个空格分隔，分别表示第 2 至 n 个结点的父结点编号。

第三行包含 n 个整数 Vi，相邻整数之间使用一个空格分隔，分别表示每个结点的点权。

输出格式

输出一行包含一个整数表示答案。

样例输入

5

1 2 3 2

2 1 9 3 5

样例输出

11

思路

题面的三个条件可以转化为：

1. 一个点选了之后，父或子不能选。
2. 同一层只能选一个
3. 求选所有点的和的最大值

这样转化之后，问题就是很经典的选或不选问题。

对第一个条件，我们从上往下遍历，枚举每一层选或不选。

对于第二个条件，我们对一层选的时候求该层最大值即可。

由于一层只能选一个，那么进行层序遍历就可以了。

时间复杂度 O(n)，每个点只被遍历了一次。

代码

from collections import defaultdict

N = 2_000_10
# 存放权值
w = [0 for i in range(N)]
# 存放父节点
f = [0 for i in range(N)]
# 存放点的高度
h = [0 for i in range(N)]
# 存放每一层的点
h_g = defaultdict(list)
dp = [0 for i in range(N)]

h_g[1].append(1)

n = int(input())
f[2:n] = list(map(int, input().split()))
f[1] = -1
w[1:n] = list(map(int, input().split()))

for i in range(2, n + 1):
    # 一个点的高度是他父亲的高度加一
    h[i] = h[f[i]] + 1
    # 为了方便遍历，直接将这个点加入他所在的层
    h_g[h[i] + 1].append(i)

dp[1] = w[1]
# 从第二层遍历到最后一层
for i in range(2, max(h[1:n]) + 1):
    i_max = max([w[j] for j in h_g[i]])
    dp[i] = max(dp[i - 2] + i_max, dp[i - 1])

print(dp[max(h[1:n])])

H题: 独一无二

问题描述

有一个包含 n 个点，m 条边的无向图，第 i 条边的边权为 ci，没有重边和 自环。设 si 表示从结点 1 出发到达结点 i 的最短路的不同路径数 ( i ∈ [1, n] )， 显然可以通过删除若干条边使得 si = 1，也就是有且仅有一条从 1 到 i 的最短 路，且保持最短路的路径长度不变，对于每个 i ，求出删除边数的最小值。

输入格式

输入的第一行包含两个正整数 n, m。 接下来 m 行，每行包含三个正整数 ui , vi , ci 表示第 i 条边连接的两个点的 编号和边权。

输出格式

输出 n 行，第 i 行包含一个正整数表示对于结点 i ，删除边数的最小值， 如果 1 和 i 不连通，输出 −1 。

样例输入

4 4

1 2 1

1 3 2

2 4 2

3 4 1

样例输出

0

0

0

1

思路

单源最短路，无负权边，首选就是dijkstra。画几个图稍微总结下规律就会发现只要每次出现相同距离的时候，任意删除一条边就可以得到正确的结果，属于贪心的思想。

代码

import heapq

N = 10
g = {}
inf = 0x3f3f3f3f
st = [0 for i in range(N)]
dist = [inf for i in range(N)]

cnt = [0 for i in range(N)]


def dijkstra():
    dist[1] = 0
    q = []
    heapq.heappush(q, (0, 1))
    while q:
        dis, cur = heapq.heappop(q)
        if st[cur] == 1:
            continue
        st[cur] = 1
        if cur in g:
            for c, d in g[cur]:
                if d + dist[cur] == dist[c]:
                    cnt[c] += 1
                if d + dist[cur] < dist[c]:
                    dist[c] = d + dist[cur]
                    heapq.heappush(q, (dist[c], c))


n, m = map(int, input().split())
for _ in range(m):
    a, b, c = map(int, input().split())
    if a in g:
        g[a].append((b, c))
    else:
        g[a] = [(b, c)]

dijkstra()

for i in range(1, n + 1):
    if dist[i] == inf:
        cnt[i] = -1
    print(cnt[i])

I题: 异或和

问题描述

输入格式

输出格式

样例输入

样例输出

J题: 混乱的数组

问题描述

输入格式

输出格式

样例输入

样例输出