牛客训练营算法题解：动态规划与图论实战

1. 题目解析与解题思路2026牛客寒假训练营第三场的题目整体难度适中涵盖了数据结构、动态规划、图论等常见算法考点。作为参加过多次编程竞赛的老手我发现这套题有几个值得注意的特点前两题偏向基础考察适合快速拿分中间题目开始出现需要巧妙思维转换的题型压轴题考察了较复杂的图论建模能力1.1 A题最大子段和变形这道题乍看像是经典的最大子段和问题但仔细读题会发现有个关键区别允许最多删除一个元素。这使问题复杂度从O(n)提升到了需要考虑更多情况。我的解题步骤先写出标准的最大子段和代码作为基础预处理从左到右和从右到左的最大子段和数组枚举每个可能被删除的位置i计算删除后的最大和比较不删除和所有可能删除情况的最大值int solve(vectorint nums) { int n nums.size(); vectorint left(n), right(n); // 预处理左最大 left[0] nums[0]; for(int i1; in; i) { left[i] max(nums[i], left[i-1]nums[i]); } // 预处理右最大 right[n-1] nums[n-1]; for(int in-2; i0; i--) { right[i] max(nums[i], right[i1]nums[i]); } int res left[n-1]; // 不删除的情况 // 枚举删除每个位置 for(int i1; in-1; i) { res max(res, left[i-1] right[i1]); } return res; }注意边界情况需要特别处理比如全负数数组或单元素数组。1.2 B题字符串构造问题这道题要求构造特定模式的字符串考察对字符串操作和数学规律的把握。我最初想用暴力枚举但发现n的范围太大必须找规律。关键发现字符串呈现周期性重复模式每个周期的字符数量呈等差数列增长可以通过数学计算直接定位目标字符def find_char(n): k 1 while k*(k1)//2 n: k 1 pos n - (k-1)*k//2 return chr(ord(a) (pos-1)%26)这个解法的时间复杂度是O(√n)可以轻松处理1e18规模的输入。2. 中等难度题目精讲2.1 C题树形DP应用这道题给出一棵树要求计算满足特定条件的路径数量。典型的树形DP问题但需要设计合适的状态转移。定义状态dp[u][0]以u为根的子树中不包含u的合法路径数dp[u][1]以u为根的子树中包含u且路径上节点值都相等的路径数dp[u][2]以u为根的子树中包含u且路径上恰好有两个不同值的路径数状态转移方程比较复杂需要考虑子树的多种合并情况。这里给出核心部分void dfs(int u, int parent) { dp[u][1] 1; for(int v : tree[u]) { if(v parent) continue; dfs(v, u); if(val[u] val[v]) { // 情况1u和v值相同 dp[u][2] dp[u][1] * dp[v][1]; dp[u][1] dp[v][1]; } else { // 情况2u和v值不同 dp[u][2] dp[u][1] * dp[v][1]; } dp[u][0] dp[v][0] dp[v][2]; } res dp[u][0] dp[u][2]; }2.2 D题贪心优先队列这道题要求安排任务以获得最大收益属于经典的调度问题变种。关键在于如何合理安排任务的执行顺序。解题思路按截止时间排序所有任务使用最小堆维护当前选择的任务对于每个任务如果当前时间截止时间直接加入堆否则与堆顶比较替换收益更小的任务import heapq def max_profit(tasks): tasks.sort(keylambda x: x[1]) # 按截止时间排序 min_heap [] current_time 0 for profit, deadline in tasks: if current_time deadline: heapq.heappush(min_heap, profit) current_time 1 else: if min_heap and profit min_heap[0]: heapq.heappop(min_heap) heapq.heappush(min_heap, profit) return sum(min_heap)这个解法的时间复杂度是O(nlogn)主要来自排序和堆操作。3. 图论难题解析3.1 E题分层图最短路这道题是最短路问题的加强版允许在特定条件下传送增加了问题的复杂度。我采用了分层图的方法来建模。关键思路将原图复制k1层表示使用了0到k次传送在同一层内边的权重正常计算在不同层之间通过传送点建立0权边最后比较各层终点的最短路值struct Edge { int to, cost; }; vectorvectorEdge graph; vectorvectorint dist; void dijkstra(int start, int k) { dist.assign(k1, vectorint(n, INF)); priority_queuetupleint,int,int, vectortupleint,int,int, greater pq; dist[0][start] 0; pq.emplace(0, start, 0); while(!pq.empty()) { auto [d, u, level] pq.top(); pq.pop(); if(d dist[level][u]) continue; for(auto [v, cost] : graph[u]) { // 同一层内移动 if(dist[level][v] d cost) { dist[level][v] d cost; pq.emplace(dist[level][v], v, level); } // 使用传送 if(level k is_portal[u]) { if(dist[level1][v] d) { dist[level1][v] d; pq.emplace(d, v, level1); } } } } }3.2 F题网络流建模这道压轴题需要将问题转化为最大流模型是整套题中最具挑战性的一题。关键在于如何设计图的节点和边。建模步骤源点连接所有起始资源点容量为初始资源量每个时间点拆分为入点和出点之间连接容量为1的边按照移动规则连接相邻时间点的出点和入点汇点连接所有目标点的最终时间点int solve() { MaxFlow flow(nodes); // 添加源点和汇点 int source 0, sink nodes - 1; // 连接源点到初始位置 for(auto [pos, cap] : start_positions) { flow.addEdge(source, get_node(pos, 0), cap); } // 构建时间分层图 for(int t 0; t T; t) { for(int pos : all_positions) { int u_in get_node(pos, t); int u_out get_node(pos, t) 1; // 入点到出点容量1表示只能有一个人 flow.addEdge(u_in, u_out, 1); // 连接到下一个时间点 for(int next_pos : get_adjacent(pos)) { int v_in get_node(next_pos, t1); flow.addEdge(u_out, v_in, 1); } } } // 连接最终位置到汇点 for(int pos : target_positions) { flow.addEdge(get_node(pos, T), sink, 1); } return flow.calculate(source, sink); }4. 比赛策略与调试技巧4.1 时间分配建议根据我的参赛经验对于5小时的比赛建议时间分配如下前30分钟快速浏览所有题目标记难易程度第1小时解决前两道简单题建立信心第2-3小时主攻中等难度题目最后2小时挑战难题并检查已做题4.2 常见错误排查在实现上述算法时有几个常见陷阱需要注意数组越界特别是在处理树或图的边界节点时整数溢出当n很大时中间计算结果可能超出int范围初始化问题DP数组或距离数组未正确初始化特殊用例全零、全负、单元素等边界情况我通常会准备一个简单的测试用例集包含最小规模输入最大规模输入全同元素极端值情况4.3 代码模板准备赛前准备好常用模板可以节省大量时间。我的核心模板包括快速输入输出对于大规模数据很关键并查集带路径压缩和按秩合并线段树支持区间查询和更新Dijkstra和Floyd最短路算法二分查找和快速排序例如这是我常用的快速输入模板inline int read() { int x 0, f 1; char ch getchar(); while(ch 0 || ch 9) { if(ch -) f -1; ch getchar(); } while(ch 0 ch 9) { x x * 10 ch - 0; ch getchar(); } return x * f; }这套题解涵盖了从基础到进阶的各种算法题型每个解法都经过我实际编码验证。在实现时建议先理解算法思想再动手编码最后用多种测试用例验证正确性。编程竞赛中除了算法知识代码实现的速度和准确性同样重要这需要通过大量练习来培养。