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_cnt=1为奇数，属于下一种情况）。若odd_cnt为奇数，答案为2？等等，需要检查odd_cnt=1且数组长度>1的情况：例如[1,2]，确实无法合并成长度1，答案是2。odd_cnt=3，例如[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。需要特判吗？考虑n=1的情况：如果这唯一的数是奇数，odd=1为奇数，输出1（因为只有一个数，无法操作，长度就是1）。所以我们的公式需要修正：如果odd是偶数，输出1；如果odd是奇数，则检查n是否等于1且该数为奇数，如果是输出1，否则输出2。但更简单的做法是：如果odd是偶数，或者n==1，输出1；否则输出2。因为n==1时，无论奇偶，答案都是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; }

注意事项：

1. 多组测试数据：CF比赛题几乎都是多组测试输入，务必使用while(t--)循环。忘记处理多组数据是新手最常见的错误之一。
2. 整数溢出：本题数据范围小，无需考虑。但对于涉及加法和乘法的题，要时刻警惕int溢出，必要时使用long long。
3. 特判边界情况：就像我们刚才对n=1的讨论。在得出一般性结论后，一定要用n=0,1，数组全同、全奇、全偶等边界情况去验证逻辑。在脑中模拟比盲目提交更重要。
4. 输出格式：每个答案后要换行，cout << ans << endl;。

注意：在紧张的比赛中，对于A题，有时可以通过“猜结论”快速通过。例如本题，观察样例输入输出，可能直接发现奇数个数为奇时输出2，为偶时输出1，n=1时输出1。但稳妥起见，花1分钟进行简单推理验证是值得的，可以避免因样例巧合而WA（错误答案）。

4. B题进阶：贪心策略的识别与证明

B题通常需要比A题更进一步的抽象和策略选择。我们假设本题是一个关于分配或选择的问题。

4.1 问题建模与贪心直觉

假设B题描述如下：有n个任务，每个任务有一个奖励值a_i和一个所需时间t_i。你总共有T单位时间。每个任务完成可以获得奖励，但一旦超时总时间T，则无法获得任何奖励。你可以任意顺序完成任务。问如何安排任务顺序，使得在不超过总时间T的前提下，获得的总奖励最大。 这显然是一个经典的“日程安排”或“背包”类问题的变种。由于每个任务只有做或不做的选择（这里假设不能部分完成），且顺序影响是否超时，我们首先想到的是按某种顺序排序后，贪心地选取。贪心策略的候选：

1. 按奖励从大到小选？不行，可能一个奖励高但耗时极长的任务挤占了多个奖励稍低但耗时短的任务。
2. 按时间从小到大选？优先做快的任务。这听起来合理，因为它能最大化任务数量。但可能存在一个耗时稍长但奖励极高的任务，替换掉几个耗时短的任务后更优。
3. 按“单位时间奖励”（即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; }

注意事项：

1. 浮点数比较：使用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;。
2. 数据范围与类型：总奖励和总时间可能超过int范围，使用long long。
3. 贪心策略的证明：在比赛中，如果时间紧迫，对于B题有时可以依赖直觉和样例验证先提交。但如果提交后WA，就必须回头严谨证明或寻找反例。准备一个本子，快速画几个反例测试你的贪心策略。
4. 排序稳定性：如果比较函数对相等元素返回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/2（0-indexed）及之后的元素。因为无论我们怎么给前半部分的元素加1，它们都不会成为中位数（排序后位置不变）。所以，最优策略是：集中所有k次操作，提升从mid开始到末尾的某些元素，使得a[mid]这个位置的值尽可能大。 但并不是单纯地只给a[mid]加。因为数组是排序后的，我们需要保证在提升a[mid]的同时，a[mid]不能超过a[mid+1],a[mid+2]...，否则中位数就变成了后面的元素。更准确地说，我们希望提升a[mid]，同时让a[mid]到a[n-1]这一段尽可能“平整”，即差值不要太大。问题转化为：有m = n - mid个元素（后半部分），初始为a[mid], a[mid+1], ..., a[n-1]。我们有k次+1操作，可以分配给这些元素。目标是让第一个元素（即原a[mid]）尽可能大，同时满足分配后序列非递减（因为原始已排序，加1后可能破坏顺序，我们需要保证结果序列仍然非递减，否则中位数位置可能变化）。贪心分配：一个直观且正确的贪心是：从a[mid]开始，看它和下一个元素a[mid+1]的差距。设diff = a[mid+1] - a[mid]。如果我们有至少diff次操作，我们可以把a[mid]提升到和a[mid+1]一样高，此时“平等”的元素有2个。然后，我们试图将这两个元素一起提升到a[mid+2]的高度，以此类推。这就像一个“填平”的过程。算法设计：排序数组后，设定当前中位数索引mid = n/2。设i从mid开始，向后遍历。我们维护一个变量target，表示当前我们试图将a[mid]到a[i]这些元素共同提升到的目标值。初始target = a[mid]，cnt = 1（当前考虑的元素个数）。当i < n-1时，看下一个元素a[i+1]。如果我们将当前这cnt个元素都提升到a[i+1]，需要增加操作数need = cnt * (a[i+1] - target)。如果k >= need，则我们可以完成这次“填平”，k -= need,target = a[i+1],cnt++,i++。如果k < need，那么我们无法完全填平到a[i+1]，但我们可以将当前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[i+1]，计算能提升多少 long long add = k / cnt; // 整除，每个元素平均提升add次 target += add; k = 0; // 剩余k不足一次平均分配，可以忽略 break; } } // 如果k还有剩余，说明整个后半段已经齐平，可以整体提升 if (k > 0) { target += k / cnt; } cout << target << endl; return 0; }

注意事项：

1. 排序：这是前提，必须做。
2. 数据类型：k、need、diff * cnt这些值可能非常大，必须使用long long。
3. 整除与精度：k / cnt是整数除法，向下取整，这正符合题意（操作次数是整数）。我们不需要浮点数。
4. 循环条件与更新：仔细处理i和cnt的更新。cnt初始为1，代表当前只考虑了a[mid]自己。每次成功填平到下一个元素，cnt增加1，代表考虑的元素集合扩大了一个。
5. 测试用例：
   • 简单情况：n=1, k=5, a=[1]，mid=0,target=1, 循环不进入，最后target+=5/1=5，输出5，正确。
   • 需要填平的情况：n=3, k=4, a=[1,2,5]，排序后[1,2,5],mid=1,target=2,cnt=1。diff=5-2=3,need=3*1=3,k=4>=3, 所以k=1,target=5,cnt=2, 循环结束（i从1到1，i<n-1即1<2成立，进入下一次循环？注意循环内i++在更新cnt之后，但for循环的i++在每次迭代结束后执行。这里需要仔细走一遍：初始i=mid=1。第一次迭代：diff=a[2]-target=5-2=3,need=3,k>=need成立，更新k=1,target=5,cnt=2。然后执行for循环的i++，i变为2。判断i<n-1即2<2不成立，循环退出。此时cnt=2,target=5。剩余k=1，执行最后的if(k>0)，target+=1/2=0。最终输出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，算法正确。
   • 无法填平的情况：n=5, k=3, a=[1,1,1,2,5]，排序后不变，mid=2,target=1,cnt=1。diff=a[3]-target=2-1=1,need=1*1=1,k=3>=1，更新k=2,target=2,cnt=2。下一轮i=3（因为i++后为3），diff=a[4]-target=5-2=3,need=3*2=6,k=2<6，进入else，add=2/2=1,target=2+1=3，输出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个空地”的限制，就是经典的网格路径计数DP，dp[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量级时不可行（200020002000=8e9）。必须优化。观察：路径长度是固定的！从(1,1)到(n,m)，只能向右向下，总步数（移动次数）是(n-1)+(m-1) = n+m-2。路径上经过的格子数（包括起点终点）是n+m-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. 索引处理：为了方便，我们使用1-indexed。
2. 边界条件：对于i=1或j=1的格子，只能从一个方向转移。
3. 空间优化：由于dp[i][j][c]只依赖于dp[i-1][j][c-1]和dp[i][j-1][c-1]，我们可以使用滚动数组优化空间，将第一维i优化掉，只保留dp[j][c]。但需要注意遍历顺序，对于每一行i，j要从1到m顺序遍历，这样在计算dp[j][c]时，dp[j][c-1]是当前行已经更新过的左格子，dp[j][c-1]（从上方来）需要用上一行的数据。所以我们需要两个二维数组prev和curr，分别代表上一行和当前行。
4. 取模：每次加法后取模。

#include #include using namespace std; const int MOD = 1e9+7; int main() { int n, m, K; cin >> n >> m >> K; vector grid(n+1, vector(m+1)); 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(m+1, vector(K+1, 0)); vector> curr(m+1, vector(K+1, 0)); // 初始化第一行第一列的状态比较麻烦，我们直接在循环中处理 // 但起点需要初始化 // 走到(1,1)，访问空地数c=1（如果它是空地） 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(m+1, vector(K+1, 0)); vector> dp_curr(m+1, vector(K+1, 0)); // 初始化起点 if (grid[1][1] == '.') dp_curr[1][1] = 1; for (int i = 1; i <= n; ++i) { // 每行开始，将dp_curr清零（除了第一行第一列已经在初始化时设置） if (i > 1) { // 对于i>1，我们需要从头计算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;

注意事项：

1. 起点终点判断：如果起点或终点是障碍，答案直接为0。
2. 状态转移的条件：不仅要从合法的格子转移（i>1或j>1），而且转移过来的那个格子也必须是空地。因为如果上一个格子是障碍，你不可能从那里走过来。所以条件grid[i-1][j] == '.'和grid[i][j-1] == '.'是必须的。
3. 空间优化细节：使用滚动数组时，要清楚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]是上一行的数据。
4. 复杂度：O(n*m*k)，在合理数据范围内可以通过。
5. 模运算：在加法后立即取模，防止溢出。

7. 常见错误与调试技巧实录

在实战中，无法AC（Accept）是常态。如何快速定位和修复错误，是比赛能力的重要组成部分。

7.1 典型WA（错误答案）原因排查清单

当提交后得到WA，可以按以下顺序排查：

1. 重新阅读题面：确保没有误解题目。特别注意“恰好”、“至少”、“至多”、“模”等关键词。检查输入输出格式、顺序。
2. 检查边界情况：
   • n=0, n=1, n=最大值。
   • 数组全为零、全为负、全部相等。
   • k=0, k远大于n。
   • 答案可能为0的情况。
3. 验证算法逻辑：用自己设计的小样例（包括边界样例）在本地测试。如果样例通过，构造一些随机小数据，用暴力算法（如果可能）对拍。
4. 检查数据范围和溢出：这是WA的常见原因。仔细看题目数据范围，计算中间结果和最终结果可能的最大值。int范围约2e9，long long约9e18。对于乘法a*b，即使结果用long long接收，如果a和b都是int，相乘时已经以int运算可能溢出，再赋值给long long。应使用1LL * a * b。
5. 检查初始化：DP或全局变量是否在每组测试数据前正确重置？多组数据时，务必清空所有容器和变量。
6. 检查索引：数组是否0-indexed或1-indexed？循环边界是否正确？特别是for (int i=0; i<n; ++i)和for (int i=1; i<=n; ++i)的混用容易出错。
7. 检查特判：题目中是否有需要特殊处理的情况？比如n=1时，某些公式不成立。

7.2 TLE（超时）与MLE（超内存）优化策略

1. 复杂度估算：在提交前，估算最坏情况下的操作次数。C++大约1秒可执行1e8次简单操作。如果算法是O(n^2)，n<=5000通常安全，n<=100000则可能超时。
2. 输入输出效率：对于大量数据输入（n > 1e5），使用scanf/printf或关闭同步的cin/cout。

   ios::sync_with_stdio(false); cin.tie(nullptr);

3. 减少不必要的操作：避免在循环内调用memset清空大数组，避免使用vector的clear()后立即resize（可能不释放内存），考虑复用数组。
4. 算法优化：TLE的根本原因往往是算法复杂度高。思考是否有更优的算法（如用二分替代线性搜索，用前缀和优化重复计算，用DP状态优化降维）。
5. 数据结构选择：频繁查找用set/map（O(log n)），但常数大；如果键值范围小，可用数组模拟。优先使用unordered_map/unordered_set（O(1)平均），但注意最坏情况。
6. MLE：检查是否开了过大的全局数组。局部变量在栈上，大数组应开在堆上（用vector）。注意vector的reserve和shrink_to_fit。

7.3 调试技巧与心态管理

1. 输出中间变量：在怀疑的代码段前后，输出关键变量值。比赛环境支持标准错误输出cerr，它不影响判题。
2. 使用静态检查：对于边界条件，在脑中或纸上模拟代码执行。
3. 构造极端数据：自己写一个暴力程序（对于小数据范围），与你的优化程序对拍，随机生成大量小数据，比较输出。
4. 时间管理：如果一道题卡住超过20分钟，果断看下一题。有时后面的题反而更简单。全部题目都读一遍，有助于把握整体难度分布。
5. 保持冷静：WA和TLE是比赛的一部分。深呼吸，从头梳理。如果一直WA on test 2，可能是没理解样例；如果WA on pretest 2（赛后知道），可能是边界情况。