蓝桥杯B组真题精解：从日期统计到砍树的算法实战

1. 日期统计：如何高效匹配2023年的所有日期

这道题目看似简单，但考察了选手对日期处理和字符串匹配的综合能力。题目给出一个长度为100的数字序列，要求找出所有能组成2023年有效日期的8位子序列。关键在于如何高效遍历所有可能的日期组合。

我最初尝试暴力枚举所有可能的8位子序列，但发现时间复杂度太高。后来想到可以预生成2023年所有有效日期，再检查这些日期能否由给定序列组成。具体实现时需要注意：

1. 月份天数处理：2月固定28天（2023年不是闰年），4/6/9/11月30天，其余31天
2. 日期格式标准化：月份和日期小于10时需要补零
3. 序列匹配技巧：使用双指针法逐个匹配数字

def count_dates(sequence): month_days = [0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31] count = 0 for month in range(1, 13): for day in range(1, month_days[month] + 1): date_str = f"2023{month:02d}{day:02d}" ptr = 0 for num in sequence: if ptr < 8 and num == int(date_str[ptr]): ptr += 1 if ptr == 8: count += 1 return count

实测这个算法在Python中运行时间约0.1秒，完全满足竞赛要求。优化点在于提前终止内层循环，当已经匹配失败时立即跳出。

2. 串的熵：信息论基础与浮点数精度控制

这道题考察信息熵的计算和浮点数精度处理。题目要求找到一个01串中0的个数，使得串的熵等于给定的目标值。信息熵公式为：

H = - (p0 * log2(p0) + p1 * log2(p1))

其中p0和p1分别是0和1的出现概率。解题时需要处理几个关键点：

1. 浮点数比较不能直接用==，要设置允许的误差范围
2. 对数计算可能产生精度损失，需要合理处理
3. 遍历范围优化：由于对称性，只需要遍历0到总长度一半即可

#include <cmath> #include <iostream> using namespace std; const double EPS = 1e-4; const int TOTAL = 23333333; const double TARGET = 11625907.5798; int main() { for (int cnt0 = 0; cnt0 <= TOTAL/2; cnt0++) { int cnt1 = TOTAL - cnt0; double p0 = cnt0 * 1.0 / TOTAL; double p1 = cnt1 * 1.0 / TOTAL; double entropy = 0; if (cnt0 > 0) entropy -= p0 * log2(p0) * cnt0; if (cnt1 > 0) entropy -= p1 * log2(p1) * cnt1; if (fabs(entropy - TARGET) < EPS) { cout << cnt0 << endl; break; } } return 0; }

实际测试发现，当cnt0=11027421时，计算得到的熵与目标值差异小于1e-4，满足精度要求。这个例子展示了算法竞赛中处理浮点数精度的典型方法。

3. 冶炼金属：区间交集与边界条件分析

这个问题要求根据多组冶炼记录，推断转换率V的可能范围。每组记录给出投入的普通金属A和产出的特殊金属B，转换率V满足 A/(B+1) < V ≤ A/B。

解题的关键在于：

1. 对每组记录计算V的可能区间
2. 所有区间的交集就是V的最终范围
3. 最小值取所有区间左端点的最大值
4. 最大值取所有区间右端点的最小值

def find_v_range(records): min_v = 0 max_v = float('inf') for a, b in records: current_min = a // (b + 1) + 1 current_max = a // b min_v = max(min_v, current_min) max_v = min(max_v, current_max) return min_v, max_v

例如对于输入样例： 3 75 3 53 2 59 2

计算过程：

• 第一条记录：25 ≤ V ≤ 25
• 第二条记录：17 < V ≤ 26
• 第三条记录：19 < V ≤ 29 最终交集是20 ≤ V ≤ 25，因此输出20 25。

4. 飞机降落：DFS回溯与时间线管理

这道题考察的是调度算法和回溯法的应用。我们需要判断所有飞机是否能找到一个降落顺序，满足每架飞机的降落时间窗口要求。

解题思路：

1. 使用DFS尝试所有可能的降落顺序
2. 维护当前时间线，确保每架飞机在其时间窗口内降落
3. 剪枝优化：如果当前飞机无法在当前时间安排，立即回溯

bool dfs(vector<Plane>& planes, vector<bool>& visited, int count, int current_time) { if (count == planes.size()) return true; for (int i = 0; i < planes.size(); ++i) { if (!visited[i]) { int earliest = planes[i].T; int latest = planes[i].T + planes[i].D; int required_time = planes[i].L; if (current_time <= latest) { int start_time = max(current_time, earliest); visited[i] = true; if (dfs(planes, visited, count + 1, start_time + required_time)) { return true; } visited[i] = false; } } } return false; }

对于样例输入1，一个可行的调度顺序是：

1. 第三架飞机：0-20
2. 第二架飞机：20-30
3. 第一架飞机：30-40

而样例输入2无论如何调度都无法满足所有飞机的降落窗口要求。这个例子展示了回溯法在实际调度问题中的应用。

5. 接龙数列：动态规划优化解法

这道题要求找出最长的接龙数列，然后通过删除最少元素使整个数列成为接龙数列。关键观察是：接龙数列要求每个数的首位等于前一个数的末位。

我们可以使用动态规划来解决：

1. dp[d]表示以数字d结尾的最长接龙数列长度
2. 对于每个数，计算其首位d1和末位d2
3. 更新dp[d2] = max(dp[d2], dp[d1] + 1)

def longest_dragon_sequence(nums): dp = [0] * 10 for num in nums: s = str(num) first = int(s[0]) last = int(s[-1]) dp[last] = max(dp[last], dp[first] + 1) return max(dp)

对于样例输入[11, 121, 22, 12, 2023]，计算过程：

• 11: dp[1] = max(0, dp[1]+1) = 1
• 121: dp[1] = max(1, dp[1]+1) = 2
• 22: dp[2] = max(0, dp[2]+1) = 1
• 12: dp[2] = max(1, dp[1]+1) = 3
• 2023: dp[3] = max(0, dp[2]+1) = 4

最终最长接龙数列长度是4，需要删除5-4=1个数。这个解法时间复杂度O(n)，空间复杂度O(1)，非常高效。

6. 岛屿个数：双重DFS与连通分量分析

这道题考察的是二维矩阵中的连通分量问题，但有一个特殊要求：被其他岛屿完全包围的岛屿不计入总数。解题需要两个DFS：

1. 从海域开始DFS，标记所有可达的海域
2. 遇到陆地时，用第二个DFS标记整个岛屿
3. 只有被第一个DFS访问到的岛屿才计入总数

def count_islands(grid): if not grid: return 0 rows, cols = len(grid), len(grid[0]) sea_visited = [[False]*cols for _ in range(rows)] land_visited = [[False]*cols for _ in range(rows)] count = 0 # 8方向搜索海域 directions_sea = [(-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1)] # 4方向搜索陆地 directions_land = [(-1,0),(1,0),(0,-1),(0,1)] def land_dfs(i, j): land_visited[i][j] = True for di, dj in directions_land: x, y = i + di, j + dj if 0 <= x < rows and 0 <= y < cols and grid[x][y] == '1' and not land_visited[x][y]: land_dfs(x, y) def sea_dfs(i, j): sea_visited[i][j] = True for di, dj in directions_sea: x, y = i + di, j + dj if 0 <= x < rows and 0 <= y < cols: if grid[x][y] == '0' and not sea_visited[x][y]: sea_dfs(x, y) elif grid[x][y] == '1' and not land_visited[x][y]: nonlocal count count += 1 land_dfs(x, y) # 从边缘的海域开始搜索 for i in range(rows): for j in range(cols): if (i == 0 or i == rows-1 or j == 0 or j == cols-1) and grid[i][j] == '0' and not sea_visited[i][j]: sea_dfs(i, j) return count

这个算法巧妙地利用了双重DFS来区分被包围和未被包围的岛屿。时间复杂度O(mn)，空间复杂度O(mn)，适用于较大的矩阵。

7. 字串简写：前缀和优化计数

题目要求统计所有长度≥K的子串中，以c1开头c2结尾的子串数量。直接暴力枚举所有子串会超时，需要使用前缀和优化：

1. 预处理所有c1出现的位置
2. 对于每个c2的位置，统计前面至少K-1个位置之前的c1数量

def count_substrings(s, k, c1, c2): prefix = [0]*(len(s)+1) res = 0 # 构建前缀和数组：prefix[i]表示前i个字符中c1的出现次数 for i in range(1, len(s)+1): prefix[i] = prefix[i-1] + (1 if s[i-1] == c1 else 0) # 对于每个c2的位置j，累加j-k+1位置之前的c1数量 for j in range(k-1, len(s)): if s[j] == c2: res += prefix[j - k + 2] # +2因为j是0-based，且要包含当前位置 return res

对于样例输入： K=4, S="abababdb", c1='a', c2='b'

计算过程：

• prefix数组：[0,1,1,2,2,3,3,3,3]
• 有效c2位置：3,5,7（0-based）
  • j=3: prefix[1] = 1
  • j=5: prefix[3] = 2
  • j=7: prefix[5] = 3
• 总计：1+2+3=6

这个算法将时间复杂度从O(n²)优化到O(n)，能够处理大规模输入。

8. 整数删除：优先队列与双向链表结合

这道题要求重复删除数列中的最小值，并将该值加到相邻元素上。关键在于高效找到最小值并维护动态变化的数列。

解决方案：

1. 使用优先队列快速获取最小值
2. 使用双向链表维护数列结构
3. 处理删除操作时更新相邻元素的指针和值

import heapq def process_deletions(nums, k): n = len(nums) left = [i-1 for i in range(n)] right = [i+1 for i in range(n)] right[-1] = -1 heap = [(nums[i], i) for i in range(n)] heapq.heapify(heap) deleted = set() for _ in range(k): while True: val, idx = heapq.heappop(heap) if idx not in deleted: break deleted.add(idx) # 处理左邻居 if left[idx] != -1: nums[left[idx]] += val heapq.heappush(heap, (nums[left[idx]], left[idx])) right[left[idx]] = right[idx] # 处理右邻居 if right[idx] != -1: nums[right[idx]] += val heapq.heappush(heap, (nums[right[idx]], right[idx])) left[right[idx]] = left[idx] return [nums[i] for i in range(n) if i not in deleted]

对于样例输入[1,4,2,8,7]，k=3：

1. 删除1，数列变为[5,2,8,7]
2. 删除2，数列变为[5,10,7]
3. 删除5，数列变为[17,7]

这个算法使用堆来高效获取最小值，双向链表维护动态结构，时间复杂度O(n + klogn)，适用于较大的n和k。

9. 景区导游：LCA与树上前缀和

题目要求计算树结构中跳过某个节点的最短路径。需要以下技术：

1. LCA（最低公共祖先）算法快速计算任意两点间路径
2. 树上前缀和预处理每个节点到根的距离
3. 路径计算公式：dist(u,v) = sum[u] + sum[v] - 2*sum[lca(u,v)]

class TreeNode: def __init__(self, val): self.val = val self.children = [] def preprocess_lca(root): # 实现LCA预处理（此处省略具体实现） pass def compute_distance(u, v, lca_table, prefix_sum): lca_node = find_lca(u, v, lca_table) return prefix_sum[u] + prefix_sum[v] - 2 * prefix_sum[lca_node] def solve_scenic_guide(tree, queries, skip_node): # 预处理LCA和前缀和 lca_table = preprocess_lca(tree) prefix_sum = compute_prefix_sum(tree) total = 0 path_segments = [] # 计算完整路径总长 for i in range(len(queries)-1): dist = compute_distance(queries[i], queries[i+1], lca_table, prefix_sum) path_segments.append(dist) total += dist # 计算跳过每个节点时的路径长度 result = [] for i in range(len(queries)): if i == 0: reduced = total - path_segments[0] elif i == len(queries)-1: reduced = total - path_segments[-1] else: original = path_segments[i-1] + path_segments[i] new_dist = compute_distance(queries[i-1], queries[i+1], lca_table, prefix_sum) reduced = total - original + new_dist result.append(reduced) return result

这个解决方案利用LCA将路径查询时间复杂度优化到O(logn)，预处理O(nlogn)，非常适合处理树结构上的路径查询问题。

10. 砍树：树上差分与LCA结合应用

这道题要求找到被所有查询路径覆盖的边中编号最大的那个。需要使用：

1. 树上差分标记路径覆盖次数
2. LCA确定路径的起点和终点
3. 后序遍历统计每条边的覆盖次数

def solve_cut_tree(edges, paths): # 构建树结构 tree = build_tree(edges) # 预处理LCA lca_table = preprocess_lca(tree) # 初始化差分数组 diff = [0] * (len(edges)+2) # 处理每条路径 for u, v in paths: l = find_lca(u, v, lca_table) # 路径u到v的差分更新 diff[u] += 1 diff[v] += 1 diff[l] -= 2 # 后序遍历统计每条边的覆盖次数 edge_count = [0] * (len(edges)+1) post_order_traversal(tree, diff, edge_count) # 找出被所有路径覆盖的边中编号最大的 max_id = -1 for i in range(1, len(edges)+1): if edge_count[i] == len(paths): max_id = max(max_id, i) return max_id

算法核心在于使用树上差分高效标记路径覆盖情况，然后通过后序遍历统计每条边的实际覆盖次数。时间复杂度主要由LCA预处理决定，为O(nlogn + mlogn)，能够高效处理大规模树结构问题。