第40次CCF-CSP认证结束后的那个晚上我刷了一会儿讨论帖发现热度最高的不是第三题那个图论大题怎么拿满分而是第一题到底该用printf(%.0f)还是自己写整数四舍五入。这个场景几乎每届都要上演一次——前三题看着简单真正写起来到处是细节。这篇复盘把前三题的题面大意、推导过程、现场代码和踩坑记录整理出来目标是让准备参加认证的同学心里有底前两题必须稳拿满分第三题至少把常规思路写出来拿到该拿的分剩下就是把常见套路练熟。我按自己做题顺序来讲。第一题是“加权平均数”本质是签到题第二题是“相邻合并”考栈的经典应用第三题是“最短路径方案数”Dijkstra加计数属于中等偏上的套路题。难度分布其实非常典型时间安排合理的话前三题可以在一个小时内全部拿下。1. 第40次CSP前三题的整体认知与选题策略1.1 先看试卷再动手难度分布与分值策略CSP认证的题目风格这些年其实很稳定第一题基本是送分题考简单的计算、排序、模拟但偶尔在输入输出格式或数值处理上留一个小坑第二题是一道需要一点思维量的模拟或经典数据结构题难度开始拉开差距第三题往往直接步入算法正题图论、动态规划、字符串处理都是常客会就是会不会就是不会。第40次这三题恰好是三种典型代表。“加权平均数”只要读懂题就能写“相邻合并”需要用栈来模拟连续合并思维上有一点小转弯“最短路径方案数”则需要同时跑最短路和计数代码量中等偏上。如果按分数目标来分第一题是必拿分第二题是稳定得分点第三题是冲刺满分的关键。我的建议是拿到试卷先花三分钟把三题都扫一遍判断第三题的类型自己熟不熟再决定做题顺序不要傻乎乎从第一题闷头做到第三题结果第三题只剩二十分钟。1.2 时间分配前45分钟留给前三题CSP一共五道题考试时间四小时。很多人的问题是把时间大量花在第一二题上反复检查导致后面大题没时间写。我的习惯是给前三题卡一个45分钟的硬截止时间第四题第五题再难也要留够两个半小时去啃部分分。实际操作上第一题控制在5到8分钟第二题15分钟左右第三题20到25分钟。如果第三题想了10分钟还没有明确思路果断先写一个暴力版本或者部分分版本保证已经有基础的分数再去优化。这个策略听起来简单但考场上非常管用——你永远不知道自己会在第四题的某个角落卡多久前三题留出的富余时间就是整个考试的缓冲垫。2. 第一题“加权平均数”签到题也不能在取整上翻车2.1 题面大意与样例手算题目大意是输入一个整数n然后给n个整数a_i和n个正整数权重w_i计算所有数据的加权平均数结果四舍五入到最接近的整数。形式上就是计算S (a_1 * w_1 a_2 * w_2 ... a_n * w_n) / (w_1 w_2 ... w_n)然后输出四舍五入后的整数结果。我当场随手验了一个样例3 10 20 30 1 2 1分子是101 202 30*1 80分母是1214结果是20直接输出20。再看一个带小数的2 1 4 1 1分子是5分母是2结果是2.5四舍五入后输出3。看起来确实是签到题但“四舍五入”这三个字才是真正的考点。CSP里四舍五入的定义是“远离零方向取整”也就是对非负数就是常见的四舍五入。问题是你用什么方式实现。2.2 用double写法为什么有风险我看到不少同学的代码是这样写的double sum1 0, sum2 0; for (int i 0; i n; i) { sum1 a[i] * w[i]; sum2 w[i]; } double ans sum1 / sum2; printf(%.0f\n, ans);这个写法在简单数据上完全没问题。但printf(%.0f)的取整规则依赖编译器和运行环境在部分在线评测环境中它执行的是四舍五入但某些情况下银行家舍入会带来意想不到的结果。更关键的是当n很大、a_i和w_i都到1e4级别时分子的数量级是1e13double的53位有效数字刚好够但一旦数值继续增大精度就开始有隐患。我不喜欢在签到题上赌浮点行为。尽量所有中间计算都用整数四舍五入也用手写整数方式一行代码的事情但确定性拉满。2.3 整数四舍五入的正确写法用long long保存分子和分母四舍五入的公式可以表示为round(S) floor((2 * sum wsum) / (2 * wsum))这里的sum是分子wsum是分母。原理就是普通几何里的“加0.5再向下取整”只不过把除以分母这个过程提前放进了整数运算里。完整代码如下#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; vectorlong long a(n), w(n); for (int i 0; i n; i) cin a[i]; for (int i 0; i n; i) cin w[i]; long long sum 0, wsum 0; for (int i 0; i n; i) { sum a[i] * w[i]; wsum w[i]; } long long ans (2 * sum wsum) / (2 * wsum); cout ans \n; return 0; }这个写法有几个好处一是全程整数运算不存在浮点精度问题二是四舍五入规则明确远离零方向取整在非负数场景下就是期望的行为三是代码量没有增加复杂度O(n)跑1e5的数据毫无压力。第一题给我的经验是越是送分题越要警惕“实现方式的小差异”。你永远不知道评测环境用的取整规则是什么与其赌环境不如赌数学。3. 第二题“相邻合并”从暴力递归到栈模拟的思维转折3.1 直接模拟会怎样第二题的大意是给定一个长度为n的正整数序列每次可以选择两个相邻且数值相同的元素x将它们删除并替换成一个新的元素2x。替换产生的新元素也可以继续参与后续的合并。问经过任意多次操作后数组最短可以变成多长。比如序列1 1 1 1先把中间两个1合并成2变成1 2 1此时相邻两个1已经不相邻了看起来没办法继续。但如果换一种顺序先把前两个1合并成2得到2 1 1再把后两个1合并成2得到2 2最后把两个2合并成4长度变成1。说明合并顺序很重要。如果真去模拟区间合并或者搜索所有可能的合并顺序指数级枚举n稍微一大就完蛋。我当时第一反应是这题可能和“消消乐”类似考虑用栈来解决。但为了确定栈的思路正确我先把暴力的模型想了一遍每次合并都只影响相邻的两个元素并且一旦某个元素不与右侧发生关系它的状态就固定了。这给了用单调处理的机会。3.2 栈为什么天然匹配这个操作从左到右扫描整个序列维护一个栈栈中存放的是“当前已经处理完、暂时无法继续合并的元素”。每读入一个新元素x设当前值为curx然后不断检查栈顶是否等于cur。如果相等说明栈顶元素和新元素可以合并弹出栈顶cur翻倍继续与新的栈顶比较。这个过程一直重复到栈顶不等于cur再把cur压入栈中。为什么这样是对的关键在于“相邻”这个条件。当我们从左往右处理时新元素只可能与它左边紧挨着的元素发生合并。合并后产生的新元素又只可能与更左边的元素发生合并。栈底到栈顶的顺序恰好就是序列从左到右的顺序栈顶就是当前元素的左邻居。所以用栈模拟这个连锁反应非常自然。还有一个反直觉的点为什么贪心合并不会漏掉最优解因为每次只要栈顶与新值相等这个合并就是必然要发生的。如果不合并两个相等且相邻的元素会一直存在但任何后续更优的合并方案都必须先把这两个相邻元素处理掉而合并它们产生的新值对更左侧元素的影响是唯一的。所以能合并就合并不会错过任何可能的更优结果。3.3 完整实现与复杂度分析#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; vectorlong long stk; stk.reserve(n); for (int i 0; i n; i) { long long x; cin x; long long cur x; while (!stk.empty() stk.back() cur) { stk.pop_back(); cur * 2; } stk.push_back(cur); } cout stk.size() \n; return 0; }这里有个细节cur可能因为连续的合并而变得很大比如16个1合并一次变成2、4、8、16最终可能到65536如果n再大一点或者输入值本身很大int会溢出。直接用long long一劳永逸。复杂度是O(n)的。每个元素进栈一次每次合并都会让栈中元素数量减一所以总体均摊下来是线性的。这个复杂度在CSP第二题的范围里属于轻松跑满。这题给我的启发很大看到“相邻”“替换”“连锁反应”这些词优先想栈或者队列而不是上来就DFS。栈模拟的代码短、速度快、不容易错是第二题这类题目的标准解法。4. 第三题“最短路径方案数”Dijkstra加计数的经典套路4.1 最短路径条数和长度能不能同时算第三题大意是一个无向连通图n个节点m条边边权都是正整数。求从节点1到节点n的最短路径长度以及这样的最短路径一共有多少条路径数量对1e97取模。这题最直接的想法是先用Dijkstra求出dist数组然后在新图里做一次拓扑排序或DFS来统计条数。但Dijkstra本身在松弛边的时候其实是可以同步维护“方案数”的。每当我们发现一条到达v的更短路径就用u的方案数覆盖v的方案数当我们发现一条同样短的新路径就把u的方案数加到v的方案数上。我一开始担心的是会不会漏计或者重复计分析下来只要边权为正Dijkstra每次弹出的节点距离是全局最小的那么当u被弹出时所有从起点到u的最短路径条数已经完整确定。此时用u去更新邻居v不管是严格小于还是等于都已经覆盖了所有经过u到达v的最短路情况。因为边权为正dist[u]一定小于dist[v]所以按照距离从小到大处理所有能到达v的“前驱最短路径节点”都会在v被弹出之前处理完。4.2 可复制的完整代码#include bits/stdc.h using namespace std; using ll long long; const ll INF 4e18; const ll MOD 1e9 7; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin n m; vectorvectorpairint, ll g(n 1); for (int i 0; i m; i) { int u, v; ll w; cin u v w; g[u].push_back({v, w}); g[v].push_back({u, w}); } vectorll dist(n 1, INF); vectorll ways(n 1, 0); vectorint vis(n 1, 0); priority_queuepairll, int, vectorpairll, int, greaterpairll, int pq; dist[1] 0; ways[1] 1; pq.push({0, 1}); while (!pq.empty()) { auto [d, u] pq.top(); pq.pop(); if (vis[u]) continue; vis[u] 1; for (auto [v, w] : g[u]) { if (vis[v]) continue; if (dist[v] d w) { dist[v] d w; ways[v] ways[u]; pq.push({dist[v], v}); } else if (dist[v] d w) { ways[v] (ways[v] ways[u]) % MOD; } } } if (dist[n] INF) { cout -1 0\n; } else { cout dist[n] ways[n] \n; } return 0; }INF取4e18是经过考虑的。题目里边权如果到1e9n到1e5最坏情况一条路径的总长度可能到1e14量级4e18足够大而且加上单条边权也不会溢出long long。如果你写作1e18加一条1e9的边也可能溢出虽然概率小但没必要冒险。4.3 等号更新的严谨性为什么不会漏算很多人写Dijkstra计数时会在等号判断里判断dist[v] dist[u] w但漏掉对vis[v]的判断导致某个节点已经被弹出后还会被后面弹出的节点再次“等号更新”结果重复计数。我使用的方案是只要v已经被访问过就不再更新。这个判断和Dijkstra本身的性质是兼容的。为什么等号更新不会漏关键是所有用于等号更新的u它们的dist一定严格小于v的dist因为w是正数。而Dijkstra选取节点的顺序是按dist从小到大所以u一定在v之前弹出。当v还没被访问时所有产生最短路径的前驱u都已经处理完毕ways[v]在被弹出前已经累加结束。一旦v被标记为vis就代表它的答案已经确定后面任何等号更新都是重复计算直接跳过。这样既不会漏也不会重复。另外一个需要注意的点是重边。如果1到2之间有两条边权都为1的边第一条边会让dist[2]1ways[2]ways[1]1第二条边走等号分支ways[2]累加一次变成2。这恰好是应该有的结果。重边不需要特殊处理只要松弛逻辑正确计数自然正确。第三题这类“最短路计数”组合非常经典考场上我建议把它当模板背下来。不只是CCF-CSP考很多算法竞赛的图论题都是这个套路。掌握一次以后就是白送的分。5. 考场失误与调试记录我踩过的三个坑5.1 第一题round的四舍五入分歧我在本地测试的时候用printf(%.0f)输出2.5显示是3但换到某个在线环境就变成了2。后来查了一下C标准对浮点转字符串的取整行为并没有强制要求“远离零方向取整”不同编译器、不同舍入模式可能给出不同的结果。从那以后我在CSP里凡是遇到四舍五入一律用整数公式手写绝不依赖printf或者round。这类坑的排查方式其实很固定先在本地跑一遍自己的样例再去评论区看有没有人提出争议。往往一道题下面吵得最凶的就是这种“实现细节”问题提前看一眼能省很多时间。5.2 第二题while循环合并写错成if我最初提交第二题时把栈模拟写成了if (!stk.empty() stk.back() cur) { stk.pop_back(); cur * 2; }这就漏掉了连锁合并的情况。比如序列1 1 1 1按这个写法只会合并一次最终栈里元素数量就不对。改成while之后2 2这种情况才能正确合并成4。这个坑的教训是涉及到“合并后产生的新值可能继续参与操作”时处理逻辑必须是循环而不是单次判断。用栈模拟时这个循环天然地处理了“新值一路向左吞并”的过程写代码时一定要把while写在if的位置上。5.3 第三题忘记跳过已确定节点导致重复计数第三题我一开始没有vis判断而是在弹出时用if (d ! dist[u]) continue跳过旧记录。理论上这样也能工作但等号更新的时机需要更精细地考虑。因为一个节点可能在dist确定后仍在队列里此时如果另一个更短路径节点更新它就走等号分支累加方案数。问题在于当这个节点最终从队列弹出时所有可能的等号更新是否都已经发生了答案依赖于优先级队列的弹出顺序虽然边权为正时数学上是对的但代码可读性差而且一旦写错很难排查。加上vis数组后逻辑更直白已确定节点彻底锁死后面不参与任何更新。如果你对Dijkstra的运行顺序没有那么强的信心建议像我一样用vis数组代码会安全很多。6. 备赛心法把前三题变成稳定拿分点6.1 按套路分类刷题比盲目刷难题有效CSP前三题的考点其实很集中。第一题无非是数学计算、简单模拟、数组处理偶尔有一点日期和字符串关键是多注意边界条件和数值范围。第二题往往用到栈、队列、哈希表、贪心、双指针核心是找出题目里隐含的“顺序结构”。第三题高频的是最短路、最小生成树、拓扑排序、简单动态规划、字符串处理。我备赛时是按套路刷题的比如集中练一周栈的题目再做一周图论最短路。刻意训练比每天随机刷两三道“感觉有意思的题”效率高很多因为你会形成条件反射看到“相邻合并”就知道压栈看到“单源最短路”就先把Dijkstra模板写出来。6.2 考场最后10分钟检查什么我强烈建议不要提前交卷哪怕前三题都做完了。最后10分钟把每份代码重新读一遍重点检查三件事数组下标有没有从0写成1数据类型有没有int和long long混用边界条件比如n1或输入为空时会不会崩溃。我个人的习惯是给代码专门留一个“极限数据”测试第一题用n100000、数值拉满第二题用全1序列第三题用两个点一条边的最小图。大部分低级错误在这种自测下都会现出原形。CSP的分数不是看你“会不会”而是看你“稳不稳”。前三题是整张试卷的基本盘把这部分练到肌肉记忆后面的难题才能真正放开手脚去冲。至少我在第40次这次考试里最大的体会就是把简单的题稳稳做完比在难题上花太多时间赌运气要划算得多。