大矩学习资料 - 比赛题解第4页

2023年GESP六级工作沟通（洛谷P10109）：LCA问题实战解析

3周前 (07-03)72

一、问题理解与建模这道题目将公司层级关系抽象为树结构，每个员工是树中的一个节点，直接领导关系构成父子关系。我们需要解决的问题是：给定一组员工，找到能够管理所有这些员工的最低层级领导（即编号最大的最近公共祖先）。二、算法核心：LCA的二进制提升法二进制提升法是一种高效的LCA查询算法，主要分为两个阶段...

2025年蓝桥杯省赛A组地雷阵（洛谷P12144）题解：数学建模与算法实现详解

3周前 (07-02)84

本文针对2025年蓝桥杯省赛A组的地雷阵问题（洛谷P12144）进行了详细解析。通过数学建模将圆形地雷区域转换为角度区间，提出基于区间合并的高效算法解决方案。文章包含完整的C++代码实现，详细讲解了如何计算地雷危险角度范围、合并重叠区间以及最终概率计算的方法。特别适合准备蓝桥杯竞赛的选手学习，内容涵...

NOIP2017逛公园问题终极指南：从Dijkstra到记忆化搜索的完整解析 | 算法竞赛必备技巧

3周前 (07-02)78

本文深入解析2017年NOIP提高组逛公园问题（洛谷P3953），通过Dijkstra算法预处理最短路，结合记忆化搜索实现高效路径计数。文章包含完整C++代码实现，详细注释了算法关键步骤，包括反向图构建、状态转移方程和环路检测机制。特别适合算法竞赛新手学习图论与动态规划的综合应用，不仅解释了核心算法...

2013年蓝桥杯国赛C组危险系数（洛谷P8604）：图论算法解密

3周前 (07-01)77

本文基于2013年蓝桥杯国赛C组"危险系数"真题，深入解析了图论中关键节点识别问题的解决方案。文章首先介绍了问题背景：地下网络站点间的连通性及关键站点对整体网络的影响。通过构建邻接表存储图结构，采用BFS算法进行连通性检查，详细讲解了如何计算两个站点间的危险系数DF(x,y)。实...

2023年GESP四级真题解析：幸运数的判定算法详解

3周前 (07-01)82

本文深入解析2023年GESP四级幸运数判定问题，重点讲解数字变换与字符串处理的编程技巧。通过拆解问题为三个关键步骤：1）将数字转为字符串逆向处理；2）对奇数位数字实施"乘7后求数字根"的变换；3）验证各位和是否为8的倍数。代码实现部分展示了to_string转换、字符数字处理（...

蓝桥杯2022省赛B组扫雷问题：BFS算法实战解析

3周前 (06-29)78

本文详细解析了2022年蓝桥杯省赛B组炸雷问题的解决方案。通过BFS（广度优先搜索）算法模拟排雷火箭引发的连锁爆炸过程，展示了如何高效处理二维空间中的爆炸范围计算和状态标记。文章包含完整C++实现代码并添加详细注释，重点讲解了unordered_map存储优化、距离平方计算技巧等关键算法优化点。特别...

树形DP经典：1997年CTSC选课问题深度解析

3周前 (06-29)66

本文深入解析1997年CTSC竞赛经典题目"选课"的树形动态规划解法，通过构建课程树结构和引入虚拟根节点技巧，将复杂依赖关系转化为标准的树形DP问题。文章提供完整代码实现并添加详细注释，重点讲解分组背包在树形结构中的应用方式，包括状态转移方程设计、后序遍历处理顺序以及学分累加规则...

带权并查集实战：2001年NOI食物链问题详解

3周前 (06-29)74

本文详细解析2001年NOI竞赛经典题目"食物链"的带权并查集解法，通过构建关系维护机制和路径压缩优化，将复杂的生物关系转化为带权并查集问题。文章提供完整代码实现并添加详细注释，重点讲解模3运算在关系维护中的应用、路径压缩时的关系更新策略以及按秩合并的实现细节。针对算法竞赛新手，...

蓝桥杯2024省赛B组拔河问题：前缀和与双指针解法详解

3周前 (06-28)80

本文详细解析了2024年蓝桥杯省赛B组拔河问题的创新解法。通过构建前缀和数组实现O(1)时间复杂度的区间和查询，采用双重循环枚举所有连续区间并记录边界信息。算法核心在于将区间和排序后，使用双指针技巧高效寻找不相交区间的最小差值。文章深入讲解了时间复杂度为O(n² log n)的完整实现过程，并分析了...