1. 项目概述一场典型Codeforces Div.2竞赛的实战复盘Codeforces简称CF是全球最负盛名的算法竞赛平台之一。对于每一位有志于提升算法与编程能力的开发者而言参与其定期举办的比赛是检验学习成果、锻炼临场思维和保持竞技状态的绝佳方式。今天我想和大家复盘一场颇具代表性的比赛——Codeforces Round #774 (Div. 2)并聚焦于其前四道题目的解题过程。这不仅仅是一次简单的题解分享更是一次关于如何在高压、限时的比赛环境中快速理解题意、设计算法、调试代码并规避常见陷阱的深度剖析。无论你是刚刚踏入算法竞赛大门的新手还是希望提升比赛稳定性的进阶选手相信这次从“参赛者视角”出发的复盘都能为你带来一些实战层面的启发。我们将逐一拆解每道题的核心模型、解题思路、代码实现细节并穿插我在解题过程中踩过的“坑”和总结出的“偷懒”技巧。2. 赛题整体分析与策略制定Codeforces Div.2 的比赛通常包含6到7道题目难度从A题到F/G题递增。前四题A, B, C, D一般覆盖了基础思维、简单数据结构、基础算法和中等难度的组合/数论问题。解决这四题是稳定上分Rating增长的关键。Round #774 (Div. 2) 的前四题也遵循了这一模式但各有其独特的思维拐点。2.1 环境与心态准备在深入题目之前我们必须明确比赛环境。CF比赛时长通常是2小时到2.15小时前四题理想情况下需要在1小时到1.5小时内解决为后面的难题留出时间。这意味着平均每道题只有15-25分钟的思考与编码时间。因此策略至关重要通常按照A-B-C-D的顺序开题但如果某题卡壳超过10分钟应立即跳转下一题。我的个人习惯是在阅读A题时同步打开代码编辑器准备模板理解B题意后大脑可以后台思考A题解法并行处理以节省时间。2.2 题目难度预判与时间分配根据过往经验和对题目标题/题面的快速浏览可以对难度有个初步预判A题往往是纯粹的思维题或模拟题考验基本编程能力和逻辑清晰度。目标5分钟内理解10分钟内AC通过。B题难度稍升可能涉及简单的贪心策略、基础数学或枚举。目标10-15分钟。C题通常需要一些经典算法或数据结构的应用如排序、二分查找、前缀和或者较为复杂的构造。目标15-25分钟。D题Div.2的D题是一个分水岭可能涉及动态规划、图论基础、中等难度的数论或需要巧妙观察的贪心。目标20-30分钟甚至更多。 对于本次复盘的前四题我们将验证这个预判并看实际解题中与预判的差异在哪这些差异点正是需要学习和积累的经验。3. A题实战详解从理解到AC的极限速度A题的标题和题面通常很短但陷阱往往就藏在简短的描述中。3.1 题意解析与模型抽象我们以Round 774 Div.2的A题为例注为通用性此处不粘贴原题以思路分析为主。假设A题是一个关于数组操作的问题给定一个数组每次操作可以合并两个相邻且奇偶性相同的数两数之和替换它们问最终数组可能的最小长度。第一步彻底理解约束。我们必须立刻抓住几个关键操作对象是“相邻”元素条件是“奇偶性相同”操作结果是“替换为和”。目标是“最小长度”。第二步思维实验。在脑中用小规模例子模拟比如[2,4,6]全偶可以合并成[12]长度1。[1,3,2]前两个奇数可合并为[4,2]但4和2奇偶性不同无法再合并长度2。[1,2,3]没有可合并的相邻对长度3。第三步寻找规律与证明。通过几个例子我们发现奇数或偶数的连续段可以被合并成一个数。因为只要相邻两个同奇偶就可以合并合并后的和必然保持同样的奇偶性偶数偶数偶数奇数奇数偶数。等等这里有个关键点奇数奇数偶数这意味着两个奇数合并后变成了一个偶数。这个偶数可能和旁边的偶数继续合并也可能和旁边的奇数无法合并。所以一个连续的奇数段经过内部合并最终会变成一个数如果奇数个数是偶数则最终为偶数如果是奇数则最终为奇数。而偶数和偶数合并永远为偶数。因此问题的核心变成了统计数组中奇数的个数。因为偶数总是可以和偶数合并不影响奇数段的状态。而奇数会“阻塞”合并过程吗让我们推理假设有k个奇数。每两个奇数可以合并成一个偶数这个偶数可以融入偶数群体。如果k是偶数那么所有奇数可以两两配对最终全部转化为偶数的一部分整个数组可能被合并成长度1如果初始有偶数或长度1如果初始全奇数则变成若干个偶数再合并。如果k是奇数那么最后会剩下一个奇数它无法与任何偶数合并因此最小长度至少为2一个奇数一堆合并后的偶数并且可以通过构造达到2。结论最小长度只取决于初始数组中奇数的个数odd_cnt。若odd_cnt为偶数答案为1除非数组长度为1且该数为奇数但此时odd_cnt1为奇数属于下一种情况。若odd_cnt为奇数答案为2等等需要检查odd_cnt1且数组长度1的情况例如[1,2]确实无法合并成长度1答案是2。odd_cnt3例如[1,1,1,2]可以先将两个1合并成偶数2数组变为[2,1,2]然后两个2合并成4变为[4,1]长度2。所以答案是min(2, n)不当odd_cnt为奇数且大于0时答案就是2。因为我们可以通过操作将所有偶数合并为一堆将所有奇数两两合并剩下一个最终得到两个数一个由所有偶数合并而来一个由剩余的那个奇数而来。如果整个数组全是奇数且个数为奇数例如[1,1,1]可以合并两个1得到[2,1]长度2。最终算法读入数组统计奇数个数odd。如果odd是偶数输出1否则输出2。需要特判吗考虑n1的情况如果这唯一的数是奇数odd1为奇数输出1因为只有一个数无法操作长度就是1。所以我们的公式需要修正如果odd是偶数输出1如果odd是奇数则检查n是否等于1且该数为奇数如果是输出1否则输出2。但更简单的做法是如果odd是偶数或者n1输出1否则输出2。因为n1时无论奇偶答案都是1。而odd为偶数时我们已经论证可以合并到1。3.2 代码实现与常见坑点#include using namespace std; int main() { int t; cin t; while (t--) { int n; cin n; vector a(n); int odd_cnt 0; for (int i 0; i n; i) { cin a[i]; if (a[i] % 2 ! 0) odd_cnt; } // 核心判断逻辑 if (odd_cnt % 2 0) { cout 1 endl; } else { if (n 1) { cout 1 endl; } else { cout 2 endl; } } } return 0; }注意事项多组测试数据CF比赛题几乎都是多组测试输入务必使用while(t--)循环。忘记处理多组数据是新手最常见的错误之一。整数溢出本题数据范围小无需考虑。但对于涉及加法和乘法的题要时刻警惕int溢出必要时使用long long。特判边界情况就像我们刚才对n1的讨论。在得出一般性结论后一定要用n0,1数组全同、全奇、全偶等边界情况去验证逻辑。在脑中模拟比盲目提交更重要。输出格式每个答案后要换行cout ans endl;。注意在紧张的比赛中对于A题有时可以通过“猜结论”快速通过。例如本题观察样例输入输出可能直接发现奇数个数为奇时输出2为偶时输出1n1时输出1。但稳妥起见花1分钟进行简单推理验证是值得的可以避免因样例巧合而WA错误答案。4. B题进阶贪心策略的识别与证明B题通常需要比A题更进一步的抽象和策略选择。我们假设本题是一个关于分配或选择的问题。4.1 问题建模与贪心直觉假设B题描述如下有n个任务每个任务有一个奖励值a_i和一个所需时间t_i。你总共有T单位时间。每个任务完成可以获得奖励但一旦超时总时间T则无法获得任何奖励。你可以任意顺序完成任务。问如何安排任务顺序使得在不超过总时间T的前提下获得的总奖励最大。 这显然是一个经典的“日程安排”或“背包”类问题的变种。由于每个任务只有做或不做的选择这里假设不能部分完成且顺序影响是否超时我们首先想到的是按某种顺序排序后贪心地选取。贪心策略的候选按奖励从大到小选不行可能一个奖励高但耗时极长的任务挤占了多个奖励稍低但耗时短的任务。按时间从小到大选优先做快的任务。这听起来合理因为它能最大化任务数量。但可能存在一个耗时稍长但奖励极高的任务替换掉几个耗时短的任务后更优。按“单位时间奖励”即a_i / t_i从大到小选这类似于背包问题的性价比贪心。对于分数背包可拆分是最优的但对于01背包不可拆分问题性价比贪心并非总是最优。 我们需要更精确的建模。由于总时间限制是T这像一个容量为T的背包每个物品重量为t_i价值为a_i。这是经典的01背包问题但n和T如果很大DP复杂度O(n*T)会超时。题目通常会有特殊性质让我们能用贪心。重新审题可能题目有一个关键限制比如“每个任务完成后可以获得一次额外的时间奖励”或者“任务时间都是1”或者“奖励是递增的”。这改变了模型。假设原题有一个性质任务一旦开始必须连续完成且完成任务i后下一个任务的时间消耗会减少或增加一个与顺序相关的值。这时排序的贪心就至关重要。 一个常见的模型是设完成顺序是p1, p2, ..., pk则总耗时是 t_{p1} t_{p2} ...但奖励不是简单的加和可能和完成时间点有关。这时需要推导出一个排序不等式。经验性技巧对于需要排序的贪心题一个万金油的方法是尝试写出交换两个相邻任务后答案的变化公式。如果对于任意相邻对在某种顺序下答案更优那么这种顺序就是全局最优的。这就是“邻项交换法”证明贪心。4.2 实现细节与调试假设我们通过分析确定贪心策略是按a_i / t_i降序排序然后依次选取直到时间超过T。那么实现步骤如下#include #include #include using namespace std; struct Task { int time; int reward; double ratio; // 单位时间奖励 }; bool cmp(const Task x, const Task y) { return x.ratio y.ratio; // 按性价比降序 } int main() { int n, T; cin n T; vector tasks(n); for (int i 0; i n; i) { cin tasks[i].time tasks[i].reward; tasks[i].ratio (double)tasks[i].reward / tasks[i].time; } sort(tasks.begin(), tasks.end(), cmp); long long total_reward 0; int used_time 0; for (int i 0; i n; i) { if (used_time tasks[i].time T) { used_time tasks[i].time; total_reward tasks[i].reward; } else { // 如果题目允许部分完成分数背包这里可以加代码。 // 对于01背包直接break。 break; } } cout total_reward endl; return 0; }注意事项浮点数比较使用double存储比例并进行排序在极端情况下可能存在精度误差。更稳健的做法是使用交叉相乘比较避免浮点数比较a_i / t_i a_j / t_j等价于比较a_i * t_j a_j * t_i。在cmp函数中这样写return x.reward * y.time y.reward * x.time;。数据范围与类型总奖励和总时间可能超过int范围使用long long。贪心策略的证明在比赛中如果时间紧迫对于B题有时可以依赖直觉和样例验证先提交。但如果提交后WA就必须回头严谨证明或寻找反例。准备一个本子快速画几个反例测试你的贪心策略。排序稳定性如果比较函数对相等元素返回true可能导致未定义行为。确保你的比较是严格的。例如当a_i * t_j a_j * t_i时可以按时间小的优先即return x.reward * y.time y.reward * x.time ? x.time y.time : x.reward * y.time y.reward * x.time;。5. C题攻坚算法与数据结构的结合C题开始通常需要明确应用一种经典算法。我们假设本题是一个关于区间查询或二分答案的问题。5.1 识别算法模型假设题目描述给定一个长度为n的数组a和一个整数k你可以进行最多k次操作每次操作可以将数组中任意一个元素加1。问操作后数组的“中位数”最大能是多少中位数定义为排序后第ceil(n/2)个元素模型转换首先要使中位数最大我们肯定只关心排序后位于后半部分的元素特别是位置在mid n/20-indexed及之后的元素。因为无论我们怎么给前半部分的元素加1它们都不会成为中位数排序后位置不变。所以最优策略是集中所有k次操作提升从mid开始到末尾的某些元素使得a[mid]这个位置的值尽可能大。 但并不是单纯地只给a[mid]加。因为数组是排序后的我们需要保证在提升a[mid]的同时a[mid]不能超过a[mid1],a[mid2]...否则中位数就变成了后面的元素。更准确地说我们希望提升a[mid]同时让a[mid]到a[n-1]这一段尽可能“平整”即差值不要太大。问题转化为有m n - mid个元素后半部分初始为a[mid], a[mid1], ..., a[n-1]。我们有k次1操作可以分配给这些元素。目标是让第一个元素即原a[mid]尽可能大同时满足分配后序列非递减因为原始已排序加1后可能破坏顺序我们需要保证结果序列仍然非递减否则中位数位置可能变化。贪心分配一个直观且正确的贪心是从a[mid]开始看它和下一个元素a[mid1]的差距。设diff a[mid1] - a[mid]。如果我们有至少diff次操作我们可以把a[mid]提升到和a[mid1]一样高此时“平等”的元素有2个。然后我们试图将这两个元素一起提升到a[mid2]的高度以此类推。这就像一个“填平”的过程。算法设计排序数组后设定当前中位数索引mid n/2。设i从mid开始向后遍历。我们维护一个变量target表示当前我们试图将a[mid]到a[i]这些元素共同提升到的目标值。初始target a[mid]cnt 1当前考虑的元素个数。当i n-1时看下一个元素a[i1]。如果我们将当前这cnt个元素都提升到a[i1]需要增加操作数need cnt * (a[i1] - target)。如果k need则我们可以完成这次“填平”k - need,target a[i1],cnt,i。如果k need那么我们无法完全填平到a[i1]但我们可以将当前cnt个元素均匀提升add k / cnt次此时target最大可以增加到target add然后k用完结束循环。最终答案循环结束后如果k还有剩余即成功填平了直到末尾的所有台阶那么我们可以将最后这cnt个元素即整个后半部分再一起提升k / cnt次target k / cnt。答案就是target。5.2 代码实现与边界处理#include #include #include using namespace std; int main() { int n; long long k; // k可能很大 cin n k; vector a(n); for (int i 0; i n; i) cin a[i]; sort(a.begin(), a.end()); int mid n / 2; // 中位数位置0-indexed long long target a[mid]; int cnt 1; // 当前考虑的后半段元素个数 for (int i mid; i n - 1; i) { long long diff a[i 1] - target; long long need diff * cnt; if (k need) { k - need; target a[i 1]; cnt; } else { // 无法完全提升到a[i1]计算能提升多少 long long add k / cnt; // 整除每个元素平均提升add次 target add; k 0; // 剩余k不足一次平均分配可以忽略 break; } } // 如果k还有剩余说明整个后半段已经齐平可以整体提升 if (k 0) { target k / cnt; } cout target endl; return 0; }注意事项排序这是前提必须做。数据类型k、need、diff * cnt这些值可能非常大必须使用long long。整除与精度k / cnt是整数除法向下取整这正符合题意操作次数是整数。我们不需要浮点数。循环条件与更新仔细处理i和cnt的更新。cnt初始为1代表当前只考虑了a[mid]自己。每次成功填平到下一个元素cnt增加1代表考虑的元素集合扩大了一个。测试用例简单情况n1, k5, a[1]mid0,target1, 循环不进入最后target5/15输出5正确。需要填平的情况n3, k4, a[1,2,5]排序后[1,2,5],mid1,target2,cnt1。diff5-23,need3*13,k43, 所以k1,target5,cnt2, 循环结束i从1到1in-1即12成立进入下一次循环注意循环内i在更新cnt之后但for循环的i在每次迭代结束后执行。这里需要仔细走一遍初始imid1。第一次迭代diffa[2]-target5-23,need3,kneed成立更新k1,target5,cnt2。然后执行for循环的ii变为2。判断in-1即22不成立循环退出。此时cnt2,target5。剩余k1执行最后的if(k0)target1/20。最终输出5。但这是最优吗我们手动算原始中位数是2。有4次操作。如果全给第一个数2变成6数组[1,6,5]排序后[1,5,6]中位数是5。如果先花3次把2变成5数组[1,5,5]中位数5还剩1次给任意一个5变成6数组[1,5,6]或[1,6,5]中位数还是5。所以最大中位数是5算法正确。无法填平的情况n5, k3, a[1,1,1,2,5]排序后不变mid2,target1,cnt1。diffa[3]-target2-11,need1*11,k31更新k2,target2,cnt2。下一轮i3因为i后为3diffa[4]-target5-23,need3*26,k26进入elseadd2/21,target213输出3。验证原始中位数1。有3次操作。最优策略两个1位置2和3都变成2需要1次把位置2的1变成2现在数组[1,1,2,2,5]中位数2。还剩2次可以把这两个2都变成3需要2次不我们需要把位置2和3的元素现在是2和2都提升到3需要2*(3-2)2次刚好。数组变为[1,1,3,3,5]中位数3。正确。6. D题突破动态规划与状态设计D题往往需要更系统的算法设计。我们假设本题是一个动态规划问题。6.1 问题分析与状态定义假设题目给定一个n x m的网格每个格子是空地.或障碍物#。你从(1,1)出发只能向右或向下移动到达(n,m)。除了起点和终点你还需要访问恰好k个空地包括起点和终点。问有多少条不同的路径结果对某个大质数取模。初步思考如果没有“恰好访问k个空地”的限制就是经典的网格路径计数DPdp[i][j] dp[i-1][j] dp[i][j-1]。但现在有了访问格子数量的约束我们需要在状态中增加一维记录当前路径已经访问的空地数量。状态定义dp[i][j][c]表示从(1,1)走到(i,j)并且路径上包括(i,j)恰好访问了c个空地的方案数。状态转移如果当前格子(i,j)是空地那么从上方(i-1,j)走过来时那条路径的访问空地数必须是c-1从左方(i,j-1)走过来时也是c-1。所以dp[i][j][c] (dp[i-1][j][c-1] dp[i][j-1][c-1]) % MOD前提是c 1。如果当前格子是障碍物那么路径不可能停留在此格所以dp[i][j][c] 0。但题目说“访问空地”障碍物不能算在c内。实际上如果(i,j)是障碍物我们根本不能走到这个格子因为路径只能由空地组成题目通常要求路径只能走在空地上。所以对于障碍物格子所有dp[i][j][c]都应该是0并且它不应该作为转移的中继点。更准确地说在遍历时如果grid[i][j]是障碍直接跳过该格子的所有状态计算。初始化dp[1][1][1] 1如果(1,1)是空地。否则dp[1][1][1] 0且实际上无解。答案dp[n][m][k]。6.2 优化与实现细节直接三维DP复杂度是O(n*m*k)在n,m,k都是2000量级时不可行2000200020008e9。必须优化。观察路径长度是固定的从(1,1)到(n,m)只能向右向下总步数移动次数是(n-1)(m-1) nm-2。路径上经过的格子数包括起点终点是nm-1。而“访问的空地数”c不可能超过路径上的总格子数也不可能超过整个网格的空地总数。但更重要的是c必须至少是路径上的空地数。设路径上必须经过的格子集合即所有从(1,1)到(n,m)的路径都会经过的格子这个集合可能很小。但这不是优化点。关键优化维度通常这类问题中k不会很大或者n,m中的一个很小。题目可能会设置n,m 500,k 10这样的范围使得O(n*m*k)可接受。如果n,m很大k很小我们可以考虑其他方法比如组合数学。 但假设本题n,m 100, k n*m那么O(n*m*k)最大是1e6可以接受。实现注意事项索引处理为了方便我们使用1-indexed。边界条件对于i1或j1的格子只能从一个方向转移。空间优化由于dp[i][j][c]只依赖于dp[i-1][j][c-1]和dp[i][j-1][c-1]我们可以使用滚动数组优化空间将第一维i优化掉只保留dp[j][c]。但需要注意遍历顺序对于每一行ij要从1到m顺序遍历这样在计算dp[j][c]时dp[j][c-1]是当前行已经更新过的左格子dp[j][c-1]从上方来需要用上一行的数据。所以我们需要两个二维数组prev和curr分别代表上一行和当前行。取模每次加法后取模。#include #include using namespace std; const int MOD 1e97; int main() { int n, m, K; cin n m K; vector grid(n1, vector(m1)); for (int i 1; i n; i) { string s; cin s; for (int j 1; j m; j) { grid[i][j] s[j-1]; } } // 如果起点或终点是障碍直接输出0 if (grid[1][1] # || grid[n][m] #) { cout 0 endl; return 0; } // 滚动数组 dp[j][c] vector prev(m1, vector(K1, 0)); vector curr(m1, vector(K1, 0)); // 初始化第一行第一列的状态比较麻烦我们直接在循环中处理 // 但起点需要初始化 // 走到(1,1)访问空地数c1如果它是空地 curr[1][1] 1; // 假设(1,1)是空地我们在上面已经判断过 for (int i 1; i n; i) { for (int j 1; j m; j) { if (i 1 j 1) continue; // 起点已初始化 if (grid[i][j] #) { // 当前格子是障碍所有curr[j][c]应为0 fill(curr[j].begin(), curr[j].end(), 0); continue; } for (int c 1; c K; c) { long long ways 0; // 从上方来 (i-1, j) if (i 1 grid[i-1][j] .) { ways prev[j][c-1]; // 注意从上方来意味着上方的状态是prev[j][...] } // 从左方来 (i, j-1) if (j 1 grid[i][j-1] .) { ways curr[j-1][c-1]; // 左方的状态是当前行已经计算过的curr[j-1][...] } curr[j][c] ways % MOD; } } // 当前行计算完毕准备下一行 swap(prev, curr); // 需要清空curr吗实际上swap后curr变成了旧的prev我们需要清空它以便下一轮使用。 // 更清晰的做法在每行开始时将curr清零。 // 我们调整循环结构将j循环放在内层并在i循环开始时重置curr。 } // 注意由于我们最后swap了prev和curr所以最终结果在prev[m][K]中 cout prev[m][K] endl; return 0; }重新调整循环结构避免状态混乱vector dp_prev(m1, vector(K1, 0)); vector dp_curr(m1, vector(K1, 0)); // 初始化起点 if (grid[1][1] .) dp_curr[1][1] 1; for (int i 1; i n; i) { // 每行开始将dp_curr清零除了第一行第一列已经在初始化时设置 if (i 1) { // 对于i1我们需要从头计算dp_curr所以先清零 for (int j 1; j m; j) fill(dp_curr[j].begin(), dp_curr[j].end(), 0); } for (int j 1; j m; j) { if (i 1 j 1) continue; if (grid[i][j] #) continue; // dp_curr[j][c] already 0 for (int c 1; c K; c) { long long ways 0; // 从上方来 if (i 1 grid[i-1][j] .) { ways dp_prev[j][c-1]; } // 从左方来 if (j 1 grid[i][j-1] .) { ways dp_curr[j-1][c-1]; } dp_curr[j][c] ways % MOD; } } // 当前行处理完毕交换准备下一行 swap(dp_prev, dp_curr); } // 循环结束后最后一行数据在dp_prev中因为swap了 cout dp_prev[m][K] endl;注意事项起点终点判断如果起点或终点是障碍答案直接为0。状态转移的条件不仅要从合法的格子转移i1或j1而且转移过来的那个格子也必须是空地。因为如果上一个格子是障碍你不可能从那里走过来。所以条件grid[i-1][j] .和grid[i][j-1] .是必须的。空间优化细节使用滚动数组时要清楚dp_prev和dp_curr分别代表什么。dp_prev[j][c]存储的是上一行第j列、访问空地数为c的方案数。dp_curr[j-1][c-1]存储的是当前行、左边一列、访问空地数为c-1的方案数。在计算dp_curr[j][c]时dp_curr[j-1]已经计算好了因为j是顺序遍历而dp_prev[j]是上一行的数据。复杂度O(n*m*k)在合理数据范围内可以通过。模运算在加法后立即取模防止溢出。7. 常见错误与调试技巧实录在实战中无法ACAccept是常态。如何快速定位和修复错误是比赛能力的重要组成部分。7.1 典型WA错误答案原因排查清单当提交后得到WA可以按以下顺序排查重新阅读题面确保没有误解题目。特别注意“恰好”、“至少”、“至多”、“模”等关键词。检查输入输出格式、顺序。检查边界情况n0, n1, n最大值。数组全为零、全为负、全部相等。k0, k远大于n。答案可能为0的情况。验证算法逻辑用自己设计的小样例包括边界样例在本地测试。如果样例通过构造一些随机小数据用暴力算法如果可能对拍。检查数据范围和溢出这是WA的常见原因。仔细看题目数据范围计算中间结果和最终结果可能的最大值。int范围约2e9long long约9e18。对于乘法a*b即使结果用long long接收如果a和b都是int相乘时已经以int运算可能溢出再赋值给long long。应使用1LL * a * b。检查初始化DP或全局变量是否在每组测试数据前正确重置多组数据时务必清空所有容器和变量。检查索引数组是否0-indexed或1-indexed循环边界是否正确特别是for (int i0; in; i)和for (int i1; in; i)的混用容易出错。检查特判题目中是否有需要特殊处理的情况比如n1时某些公式不成立。7.2 TLE超时与MLE超内存优化策略复杂度估算在提交前估算最坏情况下的操作次数。C大约1秒可执行1e8次简单操作。如果算法是O(n^2)n5000通常安全n100000则可能超时。输入输出效率对于大量数据输入n 1e5使用scanf/printf或关闭同步的cin/cout。ios::sync_with_stdio(false); cin.tie(nullptr);减少不必要的操作避免在循环内调用memset清空大数组避免使用vector的clear()后立即resize可能不释放内存考虑复用数组。算法优化TLE的根本原因往往是算法复杂度高。思考是否有更优的算法如用二分替代线性搜索用前缀和优化重复计算用DP状态优化降维。数据结构选择频繁查找用set/mapO(log n)但常数大如果键值范围小可用数组模拟。优先使用unordered_map/unordered_setO(1)平均但注意最坏情况。MLE检查是否开了过大的全局数组。局部变量在栈上大数组应开在堆上用vector。注意vector的reserve和shrink_to_fit。7.3 调试技巧与心态管理输出中间变量在怀疑的代码段前后输出关键变量值。比赛环境支持标准错误输出cerr它不影响判题。使用静态检查对于边界条件在脑中或纸上模拟代码执行。构造极端数据自己写一个暴力程序对于小数据范围与你的优化程序对拍随机生成大量小数据比较输出。时间管理如果一道题卡住超过20分钟果断看下一题。有时后面的题反而更简单。全部题目都读一遍有助于把握整体难度分布。保持冷静WA和TLE是比赛的一部分。深呼吸从头梳理。如果一直WA on test 2可能是没理解样例如果WA on pretest 2赛后知道可能是边界情况。 
长河君 · 2026/8/18 0:30:33 · 阅读 1.2k Codeforces Div.2 竞赛实战复盘：从A到D题算法策略与代码实现详解
1. 项目概述一场典型Codeforces Div.2竞赛的实战复盘Codeforces简称CF是全球最负盛名的算法竞赛平台之一。对于每一位有志于提升算法与编程能力的开发者而言参与其定期举办的比赛是检验学习成果、锻炼临场思维和保持竞技状态的绝佳方式。今天我想和大家复盘一场颇具代表性的比赛——Codeforces Round #774 (Div. 2)并聚焦于其前四道题目的解题过程。这不仅仅是一次简单的题解分享更是一次关于如何在高压、限时的比赛环境中快速理解题意、设计算法、调试代码并规避常见陷阱的深度剖析。无论你是刚刚踏入算法竞赛大门的新手还是希望提升比赛稳定性的进阶选手相信这次从“参赛者视角”出发的复盘都能为你带来一些实战层面的启发。我们将逐一拆解每道题的核心模型、解题思路、代码实现细节并穿插我在解题过程中踩过的“坑”和总结出的“偷懒”技巧。2. 赛题整体分析与策略制定Codeforces Div.2 的比赛通常包含6到7道题目难度从A题到F/G题递增。前四题A, B, C, D一般覆盖了基础思维、简单数据结构、基础算法和中等难度的组合/数论问题。解决这四题是稳定上分Rating增长的关键。Round #774 (Div. 2) 的前四题也遵循了这一模式但各有其独特的思维拐点。2.1 环境与心态准备在深入题目之前我们必须明确比赛环境。CF比赛时长通常是2小时到2.15小时前四题理想情况下需要在1小时到1.5小时内解决为后面的难题留出时间。这意味着平均每道题只有15-25分钟的思考与编码时间。因此策略至关重要通常按照A-B-C-D的顺序开题但如果某题卡壳超过10分钟应立即跳转下一题。我的个人习惯是在阅读A题时同步打开代码编辑器准备模板理解B题意后大脑可以后台思考A题解法并行处理以节省时间。2.2 题目难度预判与时间分配根据过往经验和对题目标题/题面的快速浏览可以对难度有个初步预判A题往往是纯粹的思维题或模拟题考验基本编程能力和逻辑清晰度。目标5分钟内理解10分钟内AC通过。B题难度稍升可能涉及简单的贪心策略、基础数学或枚举。目标10-15分钟。C题通常需要一些经典算法或数据结构的应用如排序、二分查找、前缀和或者较为复杂的构造。目标15-25分钟。D题Div.2的D题是一个分水岭可能涉及动态规划、图论基础、中等难度的数论或需要巧妙观察的贪心。目标20-30分钟甚至更多。 对于本次复盘的前四题我们将验证这个预判并看实际解题中与预判的差异在哪这些差异点正是需要学习和积累的经验。3. A题实战详解从理解到AC的极限速度A题的标题和题面通常很短但陷阱往往就藏在简短的描述中。3.1 题意解析与模型抽象我们以Round 774 Div.2的A题为例注为通用性此处不粘贴原题以思路分析为主。假设A题是一个关于数组操作的问题给定一个数组每次操作可以合并两个相邻且奇偶性相同的数两数之和替换它们问最终数组可能的最小长度。第一步彻底理解约束。我们必须立刻抓住几个关键操作对象是“相邻”元素条件是“奇偶性相同”操作结果是“替换为和”。目标是“最小长度”。第二步思维实验。在脑中用小规模例子模拟比如[2,4,6]全偶可以合并成[12]长度1。[1,3,2]前两个奇数可合并为[4,2]但4和2奇偶性不同无法再合并长度2。[1,2,3]没有可合并的相邻对长度3。第三步寻找规律与证明。通过几个例子我们发现奇数或偶数的连续段可以被合并成一个数。因为只要相邻两个同奇偶就可以合并合并后的和必然保持同样的奇偶性偶数偶数偶数奇数奇数偶数。等等这里有个关键点奇数奇数偶数这意味着两个奇数合并后变成了一个偶数。这个偶数可能和旁边的偶数继续合并也可能和旁边的奇数无法合并。所以一个连续的奇数段经过内部合并最终会变成一个数如果奇数个数是偶数则最终为偶数如果是奇数则最终为奇数。而偶数和偶数合并永远为偶数。因此问题的核心变成了统计数组中奇数的个数。因为偶数总是可以和偶数合并不影响奇数段的状态。而奇数会“阻塞”合并过程吗让我们推理假设有k个奇数。每两个奇数可以合并成一个偶数这个偶数可以融入偶数群体。如果k是偶数那么所有奇数可以两两配对最终全部转化为偶数的一部分整个数组可能被合并成长度1如果初始有偶数或长度1如果初始全奇数则变成若干个偶数再合并。如果k是奇数那么最后会剩下一个奇数它无法与任何偶数合并因此最小长度至少为2一个奇数一堆合并后的偶数并且可以通过构造达到2。结论最小长度只取决于初始数组中奇数的个数odd_cnt。若odd_cnt为偶数答案为1除非数组长度为1且该数为奇数但此时odd_cnt1为奇数属于下一种情况。若odd_cnt为奇数答案为2等等需要检查odd_cnt1且数组长度1的情况例如[1,2]确实无法合并成长度1答案是2。odd_cnt3例如[1,1,1,2]可以先将两个1合并成偶数2数组变为[2,1,2]然后两个2合并成4变为[4,1]长度2。所以答案是min(2, n)不当odd_cnt为奇数且大于0时答案就是2。因为我们可以通过操作将所有偶数合并为一堆将所有奇数两两合并剩下一个最终得到两个数一个由所有偶数合并而来一个由剩余的那个奇数而来。如果整个数组全是奇数且个数为奇数例如[1,1,1]可以合并两个1得到[2,1]长度2。最终算法读入数组统计奇数个数odd。如果odd是偶数输出1否则输出2。需要特判吗考虑n1的情况如果这唯一的数是奇数odd1为奇数输出1因为只有一个数无法操作长度就是1。所以我们的公式需要修正如果odd是偶数输出1如果odd是奇数则检查n是否等于1且该数为奇数如果是输出1否则输出2。但更简单的做法是如果odd是偶数或者n1输出1否则输出2。因为n1时无论奇偶答案都是1。而odd为偶数时我们已经论证可以合并到1。3.2 代码实现与常见坑点#include using namespace std; int main() { int t; cin t; while (t--) { int n; cin n; vector a(n); int odd_cnt 0; for (int i 0; i n; i) { cin a[i]; if (a[i] % 2 ! 0) odd_cnt; } // 核心判断逻辑 if (odd_cnt % 2 0) { cout 1 endl; } else { if (n 1) { cout 1 endl; } else { cout 2 endl; } } } return 0; }注意事项多组测试数据CF比赛题几乎都是多组测试输入务必使用while(t--)循环。忘记处理多组数据是新手最常见的错误之一。整数溢出本题数据范围小无需考虑。但对于涉及加法和乘法的题要时刻警惕int溢出必要时使用long long。特判边界情况就像我们刚才对n1的讨论。在得出一般性结论后一定要用n0,1数组全同、全奇、全偶等边界情况去验证逻辑。在脑中模拟比盲目提交更重要。输出格式每个答案后要换行cout ans endl;。注意在紧张的比赛中对于A题有时可以通过“猜结论”快速通过。例如本题观察样例输入输出可能直接发现奇数个数为奇时输出2为偶时输出1n1时输出1。但稳妥起见花1分钟进行简单推理验证是值得的可以避免因样例巧合而WA错误答案。4. B题进阶贪心策略的识别与证明B题通常需要比A题更进一步的抽象和策略选择。我们假设本题是一个关于分配或选择的问题。4.1 问题建模与贪心直觉假设B题描述如下有n个任务每个任务有一个奖励值a_i和一个所需时间t_i。你总共有T单位时间。每个任务完成可以获得奖励但一旦超时总时间T则无法获得任何奖励。你可以任意顺序完成任务。问如何安排任务顺序使得在不超过总时间T的前提下获得的总奖励最大。 这显然是一个经典的“日程安排”或“背包”类问题的变种。由于每个任务只有做或不做的选择这里假设不能部分完成且顺序影响是否超时我们首先想到的是按某种顺序排序后贪心地选取。贪心策略的候选按奖励从大到小选不行可能一个奖励高但耗时极长的任务挤占了多个奖励稍低但耗时短的任务。按时间从小到大选优先做快的任务。这听起来合理因为它能最大化任务数量。但可能存在一个耗时稍长但奖励极高的任务替换掉几个耗时短的任务后更优。按“单位时间奖励”即a_i / t_i从大到小选这类似于背包问题的性价比贪心。对于分数背包可拆分是最优的但对于01背包不可拆分问题性价比贪心并非总是最优。 我们需要更精确的建模。由于总时间限制是T这像一个容量为T的背包每个物品重量为t_i价值为a_i。这是经典的01背包问题但n和T如果很大DP复杂度O(n*T)会超时。题目通常会有特殊性质让我们能用贪心。重新审题可能题目有一个关键限制比如“每个任务完成后可以获得一次额外的时间奖励”或者“任务时间都是1”或者“奖励是递增的”。这改变了模型。假设原题有一个性质任务一旦开始必须连续完成且完成任务i后下一个任务的时间消耗会减少或增加一个与顺序相关的值。这时排序的贪心就至关重要。 一个常见的模型是设完成顺序是p1, p2, ..., pk则总耗时是 t_{p1} t_{p2} ...但奖励不是简单的加和可能和完成时间点有关。这时需要推导出一个排序不等式。经验性技巧对于需要排序的贪心题一个万金油的方法是尝试写出交换两个相邻任务后答案的变化公式。如果对于任意相邻对在某种顺序下答案更优那么这种顺序就是全局最优的。这就是“邻项交换法”证明贪心。4.2 实现细节与调试假设我们通过分析确定贪心策略是按a_i / t_i降序排序然后依次选取直到时间超过T。那么实现步骤如下#include #include #include using namespace std; struct Task { int time; int reward; double ratio; // 单位时间奖励 }; bool cmp(const Task x, const Task y) { return x.ratio y.ratio; // 按性价比降序 } int main() { int n, T; cin n T; vector tasks(n); for (int i 0; i n; i) { cin tasks[i].time tasks[i].reward; tasks[i].ratio (double)tasks[i].reward / tasks[i].time; } sort(tasks.begin(), tasks.end(), cmp); long long total_reward 0; int used_time 0; for (int i 0; i n; i) { if (used_time tasks[i].time T) { used_time tasks[i].time; total_reward tasks[i].reward; } else { // 如果题目允许部分完成分数背包这里可以加代码。 // 对于01背包直接break。 break; } } cout total_reward endl; return 0; }注意事项浮点数比较使用double存储比例并进行排序在极端情况下可能存在精度误差。更稳健的做法是使用交叉相乘比较避免浮点数比较a_i / t_i a_j / t_j等价于比较a_i * t_j a_j * t_i。在cmp函数中这样写return x.reward * y.time y.reward * x.time;。数据范围与类型总奖励和总时间可能超过int范围使用long long。贪心策略的证明在比赛中如果时间紧迫对于B题有时可以依赖直觉和样例验证先提交。但如果提交后WA就必须回头严谨证明或寻找反例。准备一个本子快速画几个反例测试你的贪心策略。排序稳定性如果比较函数对相等元素返回true可能导致未定义行为。确保你的比较是严格的。例如当a_i * t_j a_j * t_i时可以按时间小的优先即return x.reward * y.time y.reward * x.time ? x.time y.time : x.reward * y.time y.reward * x.time;。5. C题攻坚算法与数据结构的结合C题开始通常需要明确应用一种经典算法。我们假设本题是一个关于区间查询或二分答案的问题。5.1 识别算法模型假设题目描述给定一个长度为n的数组a和一个整数k你可以进行最多k次操作每次操作可以将数组中任意一个元素加1。问操作后数组的“中位数”最大能是多少中位数定义为排序后第ceil(n/2)个元素模型转换首先要使中位数最大我们肯定只关心排序后位于后半部分的元素特别是位置在mid n/20-indexed及之后的元素。因为无论我们怎么给前半部分的元素加1它们都不会成为中位数排序后位置不变。所以最优策略是集中所有k次操作提升从mid开始到末尾的某些元素使得a[mid]这个位置的值尽可能大。 但并不是单纯地只给a[mid]加。因为数组是排序后的我们需要保证在提升a[mid]的同时a[mid]不能超过a[mid1],a[mid2]...否则中位数就变成了后面的元素。更准确地说我们希望提升a[mid]同时让a[mid]到a[n-1]这一段尽可能“平整”即差值不要太大。问题转化为有m n - mid个元素后半部分初始为a[mid], a[mid1], ..., a[n-1]。我们有k次1操作可以分配给这些元素。目标是让第一个元素即原a[mid]尽可能大同时满足分配后序列非递减因为原始已排序加1后可能破坏顺序我们需要保证结果序列仍然非递减否则中位数位置可能变化。贪心分配一个直观且正确的贪心是从a[mid]开始看它和下一个元素a[mid1]的差距。设diff a[mid1] - a[mid]。如果我们有至少diff次操作我们可以把a[mid]提升到和a[mid1]一样高此时“平等”的元素有2个。然后我们试图将这两个元素一起提升到a[mid2]的高度以此类推。这就像一个“填平”的过程。算法设计排序数组后设定当前中位数索引mid n/2。设i从mid开始向后遍历。我们维护一个变量target表示当前我们试图将a[mid]到a[i]这些元素共同提升到的目标值。初始target a[mid]cnt 1当前考虑的元素个数。当i n-1时看下一个元素a[i1]。如果我们将当前这cnt个元素都提升到a[i1]需要增加操作数need cnt * (a[i1] - target)。如果k need则我们可以完成这次“填平”k - need,target a[i1],cnt,i。如果k need那么我们无法完全填平到a[i1]但我们可以将当前cnt个元素均匀提升add k / cnt次此时target最大可以增加到target add然后k用完结束循环。最终答案循环结束后如果k还有剩余即成功填平了直到末尾的所有台阶那么我们可以将最后这cnt个元素即整个后半部分再一起提升k / cnt次target k / cnt。答案就是target。5.2 代码实现与边界处理#include #include #include using namespace std; int main() { int n; long long k; // k可能很大 cin n k; vector a(n); for (int i 0; i n; i) cin a[i]; sort(a.begin(), a.end()); int mid n / 2; // 中位数位置0-indexed long long target a[mid]; int cnt 1; // 当前考虑的后半段元素个数 for (int i mid; i n - 1; i) { long long diff a[i 1] - target; long long need diff * cnt; if (k need) { k - need; target a[i 1]; cnt; } else { // 无法完全提升到a[i1]计算能提升多少 long long add k / cnt; // 整除每个元素平均提升add次 target add; k 0; // 剩余k不足一次平均分配可以忽略 break; } } // 如果k还有剩余说明整个后半段已经齐平可以整体提升 if (k 0) { target k / cnt; } cout target endl; return 0; }注意事项排序这是前提必须做。数据类型k、need、diff * cnt这些值可能非常大必须使用long long。整除与精度k / cnt是整数除法向下取整这正符合题意操作次数是整数。我们不需要浮点数。循环条件与更新仔细处理i和cnt的更新。cnt初始为1代表当前只考虑了a[mid]自己。每次成功填平到下一个元素cnt增加1代表考虑的元素集合扩大了一个。测试用例简单情况n1, k5, a[1]mid0,target1, 循环不进入最后target5/15输出5正确。需要填平的情况n3, k4, a[1,2,5]排序后[1,2,5],mid1,target2,cnt1。diff5-23,need3*13,k43, 所以k1,target5,cnt2, 循环结束i从1到1in-1即12成立进入下一次循环注意循环内i在更新cnt之后但for循环的i在每次迭代结束后执行。这里需要仔细走一遍初始imid1。第一次迭代diffa[2]-target5-23,need3,kneed成立更新k1,target5,cnt2。然后执行for循环的ii变为2。判断in-1即22不成立循环退出。此时cnt2,target5。剩余k1执行最后的if(k0)target1/20。最终输出5。但这是最优吗我们手动算原始中位数是2。有4次操作。如果全给第一个数2变成6数组[1,6,5]排序后[1,5,6]中位数是5。如果先花3次把2变成5数组[1,5,5]中位数5还剩1次给任意一个5变成6数组[1,5,6]或[1,6,5]中位数还是5。所以最大中位数是5算法正确。无法填平的情况n5, k3, a[1,1,1,2,5]排序后不变mid2,target1,cnt1。diffa[3]-target2-11,need1*11,k31更新k2,target2,cnt2。下一轮i3因为i后为3diffa[4]-target5-23,need3*26,k26进入elseadd2/21,target213输出3。验证原始中位数1。有3次操作。最优策略两个1位置2和3都变成2需要1次把位置2的1变成2现在数组[1,1,2,2,5]中位数2。还剩2次可以把这两个2都变成3需要2次不我们需要把位置2和3的元素现在是2和2都提升到3需要2*(3-2)2次刚好。数组变为[1,1,3,3,5]中位数3。正确。6. D题突破动态规划与状态设计D题往往需要更系统的算法设计。我们假设本题是一个动态规划问题。6.1 问题分析与状态定义假设题目给定一个n x m的网格每个格子是空地.或障碍物#。你从(1,1)出发只能向右或向下移动到达(n,m)。除了起点和终点你还需要访问恰好k个空地包括起点和终点。问有多少条不同的路径结果对某个大质数取模。初步思考如果没有“恰好访问k个空地”的限制就是经典的网格路径计数DPdp[i][j] dp[i-1][j] dp[i][j-1]。但现在有了访问格子数量的约束我们需要在状态中增加一维记录当前路径已经访问的空地数量。状态定义dp[i][j][c]表示从(1,1)走到(i,j)并且路径上包括(i,j)恰好访问了c个空地的方案数。状态转移如果当前格子(i,j)是空地那么从上方(i-1,j)走过来时那条路径的访问空地数必须是c-1从左方(i,j-1)走过来时也是c-1。所以dp[i][j][c] (dp[i-1][j][c-1] dp[i][j-1][c-1]) % MOD前提是c 1。如果当前格子是障碍物那么路径不可能停留在此格所以dp[i][j][c] 0。但题目说“访问空地”障碍物不能算在c内。实际上如果(i,j)是障碍物我们根本不能走到这个格子因为路径只能由空地组成题目通常要求路径只能走在空地上。所以对于障碍物格子所有dp[i][j][c]都应该是0并且它不应该作为转移的中继点。更准确地说在遍历时如果grid[i][j]是障碍直接跳过该格子的所有状态计算。初始化dp[1][1][1] 1如果(1,1)是空地。否则dp[1][1][1] 0且实际上无解。答案dp[n][m][k]。6.2 优化与实现细节直接三维DP复杂度是O(n*m*k)在n,m,k都是2000量级时不可行2000200020008e9。必须优化。观察路径长度是固定的从(1,1)到(n,m)只能向右向下总步数移动次数是(n-1)(m-1) nm-2。路径上经过的格子数包括起点终点是nm-1。而“访问的空地数”c不可能超过路径上的总格子数也不可能超过整个网格的空地总数。但更重要的是c必须至少是路径上的空地数。设路径上必须经过的格子集合即所有从(1,1)到(n,m)的路径都会经过的格子这个集合可能很小。但这不是优化点。关键优化维度通常这类问题中k不会很大或者n,m中的一个很小。题目可能会设置n,m 500,k 10这样的范围使得O(n*m*k)可接受。如果n,m很大k很小我们可以考虑其他方法比如组合数学。 但假设本题n,m 100, k n*m那么O(n*m*k)最大是1e6可以接受。实现注意事项索引处理为了方便我们使用1-indexed。边界条件对于i1或j1的格子只能从一个方向转移。空间优化由于dp[i][j][c]只依赖于dp[i-1][j][c-1]和dp[i][j-1][c-1]我们可以使用滚动数组优化空间将第一维i优化掉只保留dp[j][c]。但需要注意遍历顺序对于每一行ij要从1到m顺序遍历这样在计算dp[j][c]时dp[j][c-1]是当前行已经更新过的左格子dp[j][c-1]从上方来需要用上一行的数据。所以我们需要两个二维数组prev和curr分别代表上一行和当前行。取模每次加法后取模。#include #include using namespace std; const int MOD 1e97; int main() { int n, m, K; cin n m K; vector grid(n1, vector(m1)); for (int i 1; i n; i) { string s; cin s; for (int j 1; j m; j) { grid[i][j] s[j-1]; } } // 如果起点或终点是障碍直接输出0 if (grid[1][1] # || grid[n][m] #) { cout 0 endl; return 0; } // 滚动数组 dp[j][c] vector prev(m1, vector(K1, 0)); vector curr(m1, vector(K1, 0)); // 初始化第一行第一列的状态比较麻烦我们直接在循环中处理 // 但起点需要初始化 // 走到(1,1)访问空地数c1如果它是空地 curr[1][1] 1; // 假设(1,1)是空地我们在上面已经判断过 for (int i 1; i n; i) { for (int j 1; j m; j) { if (i 1 j 1) continue; // 起点已初始化 if (grid[i][j] #) { // 当前格子是障碍所有curr[j][c]应为0 fill(curr[j].begin(), curr[j].end(), 0); continue; } for (int c 1; c K; c) { long long ways 0; // 从上方来 (i-1, j) if (i 1 grid[i-1][j] .) { ways prev[j][c-1]; // 注意从上方来意味着上方的状态是prev[j][...] } // 从左方来 (i, j-1) if (j 1 grid[i][j-1] .) { ways curr[j-1][c-1]; // 左方的状态是当前行已经计算过的curr[j-1][...] } curr[j][c] ways % MOD; } } // 当前行计算完毕准备下一行 swap(prev, curr); // 需要清空curr吗实际上swap后curr变成了旧的prev我们需要清空它以便下一轮使用。 // 更清晰的做法在每行开始时将curr清零。 // 我们调整循环结构将j循环放在内层并在i循环开始时重置curr。 } // 注意由于我们最后swap了prev和curr所以最终结果在prev[m][K]中 cout prev[m][K] endl; return 0; }重新调整循环结构避免状态混乱vector dp_prev(m1, vector(K1, 0)); vector dp_curr(m1, vector(K1, 0)); // 初始化起点 if (grid[1][1] .) dp_curr[1][1] 1; for (int i 1; i n; i) { // 每行开始将dp_curr清零除了第一行第一列已经在初始化时设置 if (i 1) { // 对于i1我们需要从头计算dp_curr所以先清零 for (int j 1; j m; j) fill(dp_curr[j].begin(), dp_curr[j].end(), 0); } for (int j 1; j m; j) { if (i 1 j 1) continue; if (grid[i][j] #) continue; // dp_curr[j][c] already 0 for (int c 1; c K; c) { long long ways 0; // 从上方来 if (i 1 grid[i-1][j] .) { ways dp_prev[j][c-1]; } // 从左方来 if (j 1 grid[i][j-1] .) { ways dp_curr[j-1][c-1]; } dp_curr[j][c] ways % MOD; } } // 当前行处理完毕交换准备下一行 swap(dp_prev, dp_curr); } // 循环结束后最后一行数据在dp_prev中因为swap了 cout dp_prev[m][K] endl;注意事项起点终点判断如果起点或终点是障碍答案直接为0。状态转移的条件不仅要从合法的格子转移i1或j1而且转移过来的那个格子也必须是空地。因为如果上一个格子是障碍你不可能从那里走过来。所以条件grid[i-1][j] .和grid[i][j-1] .是必须的。空间优化细节使用滚动数组时要清楚dp_prev和dp_curr分别代表什么。dp_prev[j][c]存储的是上一行第j列、访问空地数为c的方案数。dp_curr[j-1][c-1]存储的是当前行、左边一列、访问空地数为c-1的方案数。在计算dp_curr[j][c]时dp_curr[j-1]已经计算好了因为j是顺序遍历而dp_prev[j]是上一行的数据。复杂度O(n*m*k)在合理数据范围内可以通过。模运算在加法后立即取模防止溢出。7. 常见错误与调试技巧实录在实战中无法ACAccept是常态。如何快速定位和修复错误是比赛能力的重要组成部分。7.1 典型WA错误答案原因排查清单当提交后得到WA可以按以下顺序排查重新阅读题面确保没有误解题目。特别注意“恰好”、“至少”、“至多”、“模”等关键词。检查输入输出格式、顺序。检查边界情况n0, n1, n最大值。数组全为零、全为负、全部相等。k0, k远大于n。答案可能为0的情况。验证算法逻辑用自己设计的小样例包括边界样例在本地测试。如果样例通过构造一些随机小数据用暴力算法如果可能对拍。检查数据范围和溢出这是WA的常见原因。仔细看题目数据范围计算中间结果和最终结果可能的最大值。int范围约2e9long long约9e18。对于乘法a*b即使结果用long long接收如果a和b都是int相乘时已经以int运算可能溢出再赋值给long long。应使用1LL * a * b。检查初始化DP或全局变量是否在每组测试数据前正确重置多组数据时务必清空所有容器和变量。检查索引数组是否0-indexed或1-indexed循环边界是否正确特别是for (int i0; in; i)和for (int i1; in; i)的混用容易出错。检查特判题目中是否有需要特殊处理的情况比如n1时某些公式不成立。7.2 TLE超时与MLE超内存优化策略复杂度估算在提交前估算最坏情况下的操作次数。C大约1秒可执行1e8次简单操作。如果算法是O(n^2)n5000通常安全n100000则可能超时。输入输出效率对于大量数据输入n 1e5使用scanf/printf或关闭同步的cin/cout。ios::sync_with_stdio(false); cin.tie(nullptr);减少不必要的操作避免在循环内调用memset清空大数组避免使用vector的clear()后立即resize可能不释放内存考虑复用数组。算法优化TLE的根本原因往往是算法复杂度高。思考是否有更优的算法如用二分替代线性搜索用前缀和优化重复计算用DP状态优化降维。数据结构选择频繁查找用set/mapO(log n)但常数大如果键值范围小可用数组模拟。优先使用unordered_map/unordered_setO(1)平均但注意最坏情况。MLE检查是否开了过大的全局数组。局部变量在栈上大数组应开在堆上用vector。注意vector的reserve和shrink_to_fit。7.3 调试技巧与心态管理输出中间变量在怀疑的代码段前后输出关键变量值。比赛环境支持标准错误输出cerr它不影响判题。使用静态检查对于边界条件在脑中或纸上模拟代码执行。构造极端数据自己写一个暴力程序对于小数据范围与你的优化程序对拍随机生成大量小数据比较输出。时间管理如果一道题卡住超过20分钟果断看下一题。有时后面的题反而更简单。全部题目都读一遍有助于把握整体难度分布。保持冷静WA和TLE是比赛的一部分。深呼吸从头梳理。如果一直WA on test 2可能是没理解样例如果WA on pretest 2赛后知道可能是边界情况。