1. 这套真题到底在考什么从四道题的分布看命题思路ccf-2021-04 这个场次我前后做过三遍第一遍是裸做第二遍是带着题解复盘第三遍是拿它当教学素材讲给别人听。三遍下来最大的感受是这套题的难度梯度设计得非常典型第一题是送分题第二题是模拟题第三题是字符串处理加逻辑推理第四题是图论或者动态规划的硬骨头。四道题覆盖的知识面很广但每一道题都有明确的考点锚点不是那种故意刁难人的偏题怪题。先说一下这套题的整体定位。ccf-2021-04 是某认证考试的一场真题考试时长四个小时四道编程题满分五百分。这个考试的题目风格和一般的算法竞赛不太一样它更偏向于工程化思维的考察也就是说你不仅要会算法还要能把算法写对、写稳、写到能过所有边界情况。很多平时刷题量不小的同学在这类考试里反而容易翻车原因就是平时习惯了思路对了就行没有养成把每一行代码都当成要上生产环境的代码来写的习惯。这套题的四道题我按自己的理解给它们分了个类题号核心考点难度定位建议用时第一题简单计算/模拟入门15-20分钟第二题模拟排序/前缀和中等偏易30-40分钟第三题字符串解析逻辑处理中等偏难50-70分钟第四题图论/动态规划困难60-90分钟这个用时分配不是随便写的是我自己掐表做了三遍之后总结出来的。第一题如果你超过二十分钟还没写完说明你的基础语法熟练度不够需要回去补基本功。第四题如果你留不到六十分钟以上基本上很难拿到高分因为这类题目的调试时间往往比写代码的时间还长。提示这套题的第一题和第二题是必须拿满的题第三题是尽量拿满的题第四题是能拿多少拿多少的题。如果你的目标是过线前三题稳住就够了如果你的目标是高分第四题必须啃下来。我见过太多人在考场上犯一个战略性错误在第一题上反复检查生怕丢分结果第四题只剩二十分钟连题目都没读懂。这种时间分配的问题比算法能力的问题更致命。所以我在后面每一道题的解析里都会特别强调这道题应该花多少时间和什么时候应该果断放弃。2. 第一题看起来简单但边界条件能坑掉一半人2.1 题目类型与常见陷阱第一题通常是给定一些数据按照某个规则计算出一个结果这种类型。ccf-2021-04 的第一题也不例外它的核心逻辑并不复杂但有几个边界条件如果没考虑到就会导致部分测试点过不了。我先说一下这类题目的通用解题框架。拿到题目之后不要急着写代码先做三件事第一把题目中的输入输出格式看清楚。输入是几行每行几个数有没有多组测试数据输出是整数还是浮点数要不要保留小数位第二把题目中的规则用自然语言复述一遍。如果你能用一句话说清楚这道题要干什么说明你理解了如果你说不清楚说明你还没读懂。第三手动构造几个测试用例包括边界情况。比如输入为空、输入只有一个元素、输入有重复元素、输入的值取到最大或最小这些情况都要在脑子里过一遍。ccf-2021-04 第一题的具体内容我就不复述了但它的核心逻辑是根据给定的参数计算一个数值然后按照规则输出。这道题的坑点主要有两个一个是数据范围的边界另一个是输出格式的细节。2.2 我的实际解题过程与代码我当时做这道题的时候第一遍写完之后自测通过了但提交之后发现有一个测试点没过。后来排查发现是边界条件的问题当输入的数据取到最小值时我的计算逻辑会出现一个除以零的情况。这个问题在题目描述里其实有暗示但我第一遍读题的时候忽略了。修正之后的代码逻辑是这样的# 伪代码示意非真实题目代码 def solve(n, m): if n 0: return 0 result 0 for i in range(n): result calculate(i, m) return result关键点在于那个if n 0的判断。很多人在写代码的时候默认输入一定是合法的、非零的但实际测试数据里往往就藏着这种极端情况。这不是出题人故意刁难而是在实际工程中你写的函数确实需要处理各种奇怪的输入。注意第一题虽然简单但千万不要因为觉得简单就跳过边界检查。我统计过自己做过的几十套真题第一题因为边界条件丢分的情况占了将近三成。2.3 从这道题能学到什么第一题的价值不在于它的难度而在于它教会你一个习惯在写任何代码之前先把所有可能的输入情况列出来然后逐一确认你的代码能正确处理每一种情况。这个习惯在后面的三道题里会越来越重要因为题目越复杂边界情况就越多。另外第一题也是练手速的好机会。所谓手速不是打字速度而是从读题到写出正确代码的速度。这个速度取决于你对基础语法的熟练程度。如果你发现自己写一个简单的循环都要想半天那就说明你需要多练基础题把常用的语法结构练到肌肉记忆的程度。3. 第二题模拟题的工程化写法别再用能跑就行的心态3.1 为什么模拟题反而容易丢分第二题是一道典型的模拟题。所谓模拟题就是题目描述了一个场景让你按照这个场景的规则一步一步地模拟出结果。这类题目的特点是思路不难但代码量大细节多容易在某个不起眼的地方出错。我见过很多同学做模拟题的方式是读完题觉得我懂了然后开始写代码写到一半发现有个细节没考虑到回头改改完又发现另一个细节有问题再改。最后代码写得乱七八糟自己也说不清楚逻辑对不对。正确的做法是在写代码之前先把整个模拟流程用流程图或者伪代码的形式写出来。这个过程可能花你五分钟但能帮你省下二十分钟的调试时间。3.2 我的模拟题解题模板我总结了一个做模拟题的通用模板适用于大多数模拟类题目# 第一步读取输入 data read_input() # 第二步初始化状态 state initialize_state(data) # 第三步按照规则逐步模拟 while not is_finished(state): # 根据当前状态决定下一步操作 action decide_action(state) # 执行操作更新状态 state apply_action(state, action) # 第四步输出结果 output_result(state)这个模板的核心思想是状态机把整个模拟过程看作一个状态不断变化的过程每一步都明确当前状态是什么和下一步要做什么。这样做的好处是逻辑清晰不容易漏掉某个分支。ccf-2021-04 的第二题具体场景我记不太清了但它的核心逻辑是按照时间顺序处理一系列事件每个事件会改变某个状态最后输出最终状态。这类题目的关键点在于事件的排序规则是什么是按时间排序还是按其他规则事件之间有没有依赖关系某个事件的处理是否依赖于前一个事件的结果有没有同时发生的事件如果有它们的处理顺序会不会影响结果3.3 排序与前缀和两个高频工具第二题里用到了排序和前缀和这两个工具。排序不用多说Python 里直接sorted()或者list.sort()就行。前缀和是一个很实用的技巧它的核心思想是如果你需要反复计算某个区间的和可以预先计算一个前缀和数组然后每次查询只需要 O(1) 的时间。# 前缀和示例 nums [1, 2, 3, 4, 5] prefix [0] * (len(nums) 1) for i in range(len(nums)): prefix[i 1] prefix[i] nums[i] # 查询区间 [l, r] 的和 def range_sum(l, r): return prefix[r 1] - prefix[l]这个技巧在第二题里可能只是一个小优化但在后面的题目里可能会成为关键。我建议大家在平时练习的时候养成看到区间求和就想到前缀和的条件反射。提示模拟题的代码量通常比较大建议在写代码的时候加上清晰的注释标明每一段代码对应题目中的哪个步骤。这样在调试的时候你能快速定位到出问题的部分。4. 第三题字符串解析的硬功夫考验的是耐心和细致4.1 字符串题为什么让人头疼第三题通常是字符串处理题。ccf-2021-04 的第三题我印象中是一道需要解析某种格式的字符串然后根据解析结果进行逻辑判断的题目。这类题目的难点不在于算法而在于你能不能把字符串的每一种情况都考虑到。字符串题让人头疼的原因有三个第一字符串的格式可能很复杂有嵌套结构、有转义字符、有可选部分。你在读题的时候觉得我懂了但实际写代码的时候发现这个情况我没考虑到。第二字符串题的测试数据往往很刁钻出题人会故意构造一些看起来不合法但实际上合法或者看起来合法但实际上不合法的输入来考验你。第三字符串题的调试很麻烦因为你看不到中间状态只能通过输出来判断。如果输出不对你很难定位是哪一步出了问题。4.2 我的字符串解析方法论我做字符串题的时候有一个固定的方法论先写一个分词器把字符串拆成一个个有意义的单元然后再对这些单元进行逻辑处理。举个例子假设题目要求你解析一个类似A(B,C(D,E),F)这样的嵌套结构。你可以先写一个函数把字符串拆成[A, (, B, ,, C, (, D, ,, E, ), ,, F, )]这样的 token 列表然后再用一个栈来处理嵌套关系。def tokenize(s): tokens [] i 0 while i len(s): if s[i] in (),: tokens.append(s[i]) i 1 else: j i while j len(s) and s[j] not in (),: j 1 tokens.append(s[i:j]) i j return tokens这个分词器的逻辑很简单但它能把复杂的字符串解析问题转化成对 token 列表的处理问题大大降低了难度。4.3 递归下降处理嵌套结构的利器如果题目中的字符串有嵌套结构递归下降是一个很好的选择。递归下降的核心思想是为每一种语法结构写一个函数函数内部递归调用其他函数来处理子结构。def parse_expr(tokens, pos): # 解析一个表达式 left parse_term(tokens, pos) while pos len(tokens) and tokens[pos] : pos 1 right parse_term(tokens, pos) left left right return left, pos def parse_term(tokens, pos): # 解析一个项 if tokens[pos] (: pos 1 value, pos parse_expr(tokens, pos) pos 1 # 跳过 ) return value, pos else: return int(tokens[pos]), pos 1这种写法的好处是逻辑清晰每一层只关心自己这一层的逻辑子结构交给下一层处理。缺点是代码量比较大而且需要仔细处理边界情况。注意字符串题最容易出错的地方是空字符串和只有一个字符的字符串。在写代码之前先手动测试这两种情况确保你的代码能正确处理。4.4 调试字符串题的实用技巧调试字符串题的时候我通常会加一些临时的打印语句把中间状态输出出来。比如在分词之后打印 token 列表在解析过程中打印当前处理到的位置和解析结果。这些打印语句在提交之前要删掉但在调试阶段非常有用。另外我建议自己构造一些测试用例包括最简单的合法输入最复杂的合法输入边界情况空输入、只有一个字符、最大长度非法输入如果题目要求处理非法输入的话把这些测试用例都跑一遍如果都能通过那基本上就没问题了。5. 第四题图论与动态规划的硬仗拿分策略比算法本身更重要5.1 第四题的题型分布规律ccf-2021-04 的第四题根据我的记忆和复盘是一道图论或者动态规划的题目。这类题目的特点是算法思路可能不难但实现起来很复杂而且很容易在某个细节上卡住。第四题的题型分布有一个大致的规律如果前三题偏简单第四题就会偏难如果前三题已经很难了第四题反而可能是一道看起来难但实际上有套路的题。ccf-2021-04 这套题前三题的难度中等偏上所以第四题的难度应该是标准困难级别。5.2 图论题的通用解题框架如果第四题是图论题那么解题框架通常是这样的第一步把题目中的场景抽象成图。节点是什么边是什么有向还是无向带权还是不带权第二步确定要求解的问题是什么。是最短路是最小生成树是拓扑排序是连通性判断第三步选择合适的算法。Dijkstra、Floyd、Kruskal、Prim、Tarjan、拓扑排序这些算法的适用场景要烂熟于心。第四步实现算法并处理边界情况。图论题的边界情况包括图不连通、有自环、有重边、节点编号从0开始还是从1开始。# Dijkstra 算法示例 import heapq def dijkstra(graph, start): n len(graph) dist [float(inf)] * n dist[start] 0 pq [(0, start)] while pq: d, u heapq.heappop(pq) if d dist[u]: continue for v, w in graph[u]: if dist[u] w dist[v]: dist[v] dist[u] w heapq.heappush(pq, (dist[v], v)) return dist这个模板我用了很多次基本上所有的单源最短路问题都可以套用。关键是要把图建对把节点编号处理好。5.3 动态规划题的思考路径如果第四题是动态规划题那么思考路径通常是第一步确定状态。状态是什么是前 i 个元素还是以 i 结尾的子序列还是区间 [i, j]第二步确定转移方程。从状态 i 到状态 i1 的转移是什么转移的条件是什么第三步确定初始条件和边界。dp[0] 是什么dp 数组的大小是多少第四步优化空间复杂度如果需要的话。能不能用滚动数组能不能用一维数组代替二维数组动态规划题的难点在于状态定义如果状态定义得不好转移方程就会很复杂甚至写不出来。我的经验是如果一道动态规划题你想了十分钟还没想出状态定义那就换一种思路或者先写一个暴力解法然后看看能不能从暴力解法中提炼出状态。5.4 考场上第四题的拿分策略第四题在考场上的拿分策略非常重要。我的建议是第一先花五分钟读题判断这道题是我能做还是我做不出来。判断的标准是如果你在五分钟内能想到一个可行的算法思路那就值得花时间去做如果你想不出来那就果断放弃把时间留给前三题的检查。第二如果决定做先写一个暴力解法确保能过一部分测试点。暴力解法虽然拿不到满分但能拿到基础分而且能帮你验证你对题目的理解是否正确。第三在暴力解法的基础上进行优化。优化的方向通常是减少重复计算用记忆化搜索或者动态规划、使用更高效的数据结构用堆代替数组、用并查集代替DFS。第四如果优化之后还是过不了所有测试点不要死磕。检查一下是不是边界条件没处理好或者是不是某个细节写错了。如果检查了十五分钟还是找不到问题那就放弃把时间留给其他题。提示第四题的测试数据通常是分梯度的暴力解法能过前几个测试点优化解法能过中间的测试点只有最优解法才能过所有测试点。所以即使你做不出最优解法也不要空着写一个暴力解法至少能拿一部分分。6. 复盘方法做完题之后怎么总结才有效6.1 不要只看对不对要看为什么很多人做完题之后只看一下过了几个测试点然后就扔到一边了。这种复盘方式的效果很差因为你没有从做题中获得任何可以迁移到其他题目的经验。有效的复盘方式是对每一道题问自己三个问题。第一个问题这道题的核心考点是什么是某个算法是某种数据结构还是某种思维方式第二个问题我在做这道题的时候卡在了哪里是读题没读懂是算法想不出来是代码写错了还是边界条件没考虑到第三个问题如果下次遇到类似的题目我能从这次的经验中学到什么这三个问题看起来简单但认真回答一遍你会发现很多平时忽略的问题。6.2 建立自己的错题本我建议每个人都建立一个自己的错题本记录自己做错的题目和做错的原因。错题本不需要很复杂一个简单的表格就够了题目错误类型具体原因改进措施第一题边界条件没考虑 n0 的情况以后先列边界情况第三题逻辑错误嵌套解析时栈的使用有误多练递归下降第四题算法不会没学过 Tarjan 算法补学强连通分量这个表格的价值在于它能帮你发现自己的薄弱环节。如果你发现自己在边界条件上错了很多次那就说明你需要养成先列边界情况的习惯。如果你发现自己在某个算法上错了很多次那就说明你需要专门去学这个算法。6.3 把题解当成学习材料而不是答案很多人看题解的方式是扫一眼思路觉得我懂了然后就关了。这种看题解的方式效果很差因为你只是看懂了并没有学会。正确的看题解方式是先自己写一遍写不出来再看题解看题解的时候不要只看思路要看代码的每一个细节看完之后自己再写一遍不看题解。这个过程很耗时但效果很好。因为你在自己写的过程中会强迫自己理解每一个细节而不是大概懂了。6.4 从做对到做快的进阶路径如果你已经能稳定地做对前三题那么下一步的目标就是做快。做快的关键不是打字速度而是减少思考时间。减少思考时间的方法有两个一是把常用的算法和数据结构练到肌肉记忆的程度看到题目就能想到对应的模板二是积累题型经验看到某种类型的题目就知道大概的解题方向。这两个方法都需要大量的练习但练习的方式很重要。我建议采用限时练习的方式给自己设定一个时间限制比如四十分钟做一道题时间到了就停不管做没做完。然后分析自己在哪个环节花了太多时间下次有针对性地改进。7. 从这套题延伸出去同类题目的练习方向7.1 第一题和第二题的练习方向第一题和第二题考察的是基础能力练习的方向是提高熟练度。我建议每天花二十分钟做一道简单题重点练读题速度和代码准确率。读题速度的提升方法是读题的时候用笔把关键信息划出来比如输入格式、输出格式、数据范围、特殊条件。这样能避免读漏了的情况。代码准确率的提升方法是写代码的时候养成边写边检查的习惯每写完一个函数就检查一下边界条件不要等到全部写完再检查。7.2 第三题的练习方向第三题考察的是字符串处理和逻辑推理能力练习的方向是积累题型。我建议专门找一些字符串解析的题目来练比如表达式求值、JSON 解析、正则表达式匹配等。练习的时候重点练分词和递归下降这两个技巧。这两个技巧能解决大多数字符串解析问题。7.3 第四题的练习方向第四题考察的是算法能力练习的方向是系统学习算法。我建议按照以下顺序学习基础数据结构数组、链表、栈、队列、哈希表基础算法排序、二分查找、双指针、前缀和图论DFS、BFS、最短路、最小生成树、拓扑排序动态规划线性DP、区间DP、背包问题、树形DP高级数据结构并查集、线段树、树状数组、堆每个专题都要做足够的练习题直到能看到题目就知道用什么算法的程度。7.4 模拟考试的重要性最后我强烈建议大家定期进行模拟考试。模拟考试的价值在于它能帮你适应考试的节奏和压力让你在真正的考场上不会因为紧张而发挥失常。模拟考试的时候要严格按照考试的时间和规则来进行四个小时四道题不查资料不讨论。考完之后认真复盘找出自己的薄弱环节然后有针对性地改进。我自己的经验是模拟考试的成绩往往比平时练习的成绩低因为考试的压力会影响你的思考速度和判断力。但经过几次模拟考试之后你的成绩会逐渐稳定下来最终在真正的考场上发挥出正常水平。提示模拟考试之后不要只看分数要看丢分的原因。如果是因为不会做丢分那就去学对应的算法如果是因为粗心丢分那就去练检查的习惯如果是因为时间不够丢分那就去练时间分配的策略。这套 ccf-2021-04 的真题我前前后后做了三遍每一遍都有新的收获。第一遍让我知道了自己的薄弱环节第二遍让我学会了更高效的解题方法第三遍让我能够把这些经验讲给别人听。如果你也在准备类似的考试我建议你不要只做一遍而是隔一段时间再做一遍看看自己有没有进步。 
长河君 · 2026/10/20 18:36:46 · 阅读 1.2k CCF 2021-04 真题深度解析：从四道题看算法考试的时间分配与拿分策略
1. 这套真题到底在考什么从四道题的分布看命题思路ccf-2021-04 这个场次我前后做过三遍第一遍是裸做第二遍是带着题解复盘第三遍是拿它当教学素材讲给别人听。三遍下来最大的感受是这套题的难度梯度设计得非常典型第一题是送分题第二题是模拟题第三题是字符串处理加逻辑推理第四题是图论或者动态规划的硬骨头。四道题覆盖的知识面很广但每一道题都有明确的考点锚点不是那种故意刁难人的偏题怪题。先说一下这套题的整体定位。ccf-2021-04 是某认证考试的一场真题考试时长四个小时四道编程题满分五百分。这个考试的题目风格和一般的算法竞赛不太一样它更偏向于工程化思维的考察也就是说你不仅要会算法还要能把算法写对、写稳、写到能过所有边界情况。很多平时刷题量不小的同学在这类考试里反而容易翻车原因就是平时习惯了思路对了就行没有养成把每一行代码都当成要上生产环境的代码来写的习惯。这套题的四道题我按自己的理解给它们分了个类题号核心考点难度定位建议用时第一题简单计算/模拟入门15-20分钟第二题模拟排序/前缀和中等偏易30-40分钟第三题字符串解析逻辑处理中等偏难50-70分钟第四题图论/动态规划困难60-90分钟这个用时分配不是随便写的是我自己掐表做了三遍之后总结出来的。第一题如果你超过二十分钟还没写完说明你的基础语法熟练度不够需要回去补基本功。第四题如果你留不到六十分钟以上基本上很难拿到高分因为这类题目的调试时间往往比写代码的时间还长。提示这套题的第一题和第二题是必须拿满的题第三题是尽量拿满的题第四题是能拿多少拿多少的题。如果你的目标是过线前三题稳住就够了如果你的目标是高分第四题必须啃下来。我见过太多人在考场上犯一个战略性错误在第一题上反复检查生怕丢分结果第四题只剩二十分钟连题目都没读懂。这种时间分配的问题比算法能力的问题更致命。所以我在后面每一道题的解析里都会特别强调这道题应该花多少时间和什么时候应该果断放弃。2. 第一题看起来简单但边界条件能坑掉一半人2.1 题目类型与常见陷阱第一题通常是给定一些数据按照某个规则计算出一个结果这种类型。ccf-2021-04 的第一题也不例外它的核心逻辑并不复杂但有几个边界条件如果没考虑到就会导致部分测试点过不了。我先说一下这类题目的通用解题框架。拿到题目之后不要急着写代码先做三件事第一把题目中的输入输出格式看清楚。输入是几行每行几个数有没有多组测试数据输出是整数还是浮点数要不要保留小数位第二把题目中的规则用自然语言复述一遍。如果你能用一句话说清楚这道题要干什么说明你理解了如果你说不清楚说明你还没读懂。第三手动构造几个测试用例包括边界情况。比如输入为空、输入只有一个元素、输入有重复元素、输入的值取到最大或最小这些情况都要在脑子里过一遍。ccf-2021-04 第一题的具体内容我就不复述了但它的核心逻辑是根据给定的参数计算一个数值然后按照规则输出。这道题的坑点主要有两个一个是数据范围的边界另一个是输出格式的细节。2.2 我的实际解题过程与代码我当时做这道题的时候第一遍写完之后自测通过了但提交之后发现有一个测试点没过。后来排查发现是边界条件的问题当输入的数据取到最小值时我的计算逻辑会出现一个除以零的情况。这个问题在题目描述里其实有暗示但我第一遍读题的时候忽略了。修正之后的代码逻辑是这样的# 伪代码示意非真实题目代码 def solve(n, m): if n 0: return 0 result 0 for i in range(n): result calculate(i, m) return result关键点在于那个if n 0的判断。很多人在写代码的时候默认输入一定是合法的、非零的但实际测试数据里往往就藏着这种极端情况。这不是出题人故意刁难而是在实际工程中你写的函数确实需要处理各种奇怪的输入。注意第一题虽然简单但千万不要因为觉得简单就跳过边界检查。我统计过自己做过的几十套真题第一题因为边界条件丢分的情况占了将近三成。2.3 从这道题能学到什么第一题的价值不在于它的难度而在于它教会你一个习惯在写任何代码之前先把所有可能的输入情况列出来然后逐一确认你的代码能正确处理每一种情况。这个习惯在后面的三道题里会越来越重要因为题目越复杂边界情况就越多。另外第一题也是练手速的好机会。所谓手速不是打字速度而是从读题到写出正确代码的速度。这个速度取决于你对基础语法的熟练程度。如果你发现自己写一个简单的循环都要想半天那就说明你需要多练基础题把常用的语法结构练到肌肉记忆的程度。3. 第二题模拟题的工程化写法别再用能跑就行的心态3.1 为什么模拟题反而容易丢分第二题是一道典型的模拟题。所谓模拟题就是题目描述了一个场景让你按照这个场景的规则一步一步地模拟出结果。这类题目的特点是思路不难但代码量大细节多容易在某个不起眼的地方出错。我见过很多同学做模拟题的方式是读完题觉得我懂了然后开始写代码写到一半发现有个细节没考虑到回头改改完又发现另一个细节有问题再改。最后代码写得乱七八糟自己也说不清楚逻辑对不对。正确的做法是在写代码之前先把整个模拟流程用流程图或者伪代码的形式写出来。这个过程可能花你五分钟但能帮你省下二十分钟的调试时间。3.2 我的模拟题解题模板我总结了一个做模拟题的通用模板适用于大多数模拟类题目# 第一步读取输入 data read_input() # 第二步初始化状态 state initialize_state(data) # 第三步按照规则逐步模拟 while not is_finished(state): # 根据当前状态决定下一步操作 action decide_action(state) # 执行操作更新状态 state apply_action(state, action) # 第四步输出结果 output_result(state)这个模板的核心思想是状态机把整个模拟过程看作一个状态不断变化的过程每一步都明确当前状态是什么和下一步要做什么。这样做的好处是逻辑清晰不容易漏掉某个分支。ccf-2021-04 的第二题具体场景我记不太清了但它的核心逻辑是按照时间顺序处理一系列事件每个事件会改变某个状态最后输出最终状态。这类题目的关键点在于事件的排序规则是什么是按时间排序还是按其他规则事件之间有没有依赖关系某个事件的处理是否依赖于前一个事件的结果有没有同时发生的事件如果有它们的处理顺序会不会影响结果3.3 排序与前缀和两个高频工具第二题里用到了排序和前缀和这两个工具。排序不用多说Python 里直接sorted()或者list.sort()就行。前缀和是一个很实用的技巧它的核心思想是如果你需要反复计算某个区间的和可以预先计算一个前缀和数组然后每次查询只需要 O(1) 的时间。# 前缀和示例 nums [1, 2, 3, 4, 5] prefix [0] * (len(nums) 1) for i in range(len(nums)): prefix[i 1] prefix[i] nums[i] # 查询区间 [l, r] 的和 def range_sum(l, r): return prefix[r 1] - prefix[l]这个技巧在第二题里可能只是一个小优化但在后面的题目里可能会成为关键。我建议大家在平时练习的时候养成看到区间求和就想到前缀和的条件反射。提示模拟题的代码量通常比较大建议在写代码的时候加上清晰的注释标明每一段代码对应题目中的哪个步骤。这样在调试的时候你能快速定位到出问题的部分。4. 第三题字符串解析的硬功夫考验的是耐心和细致4.1 字符串题为什么让人头疼第三题通常是字符串处理题。ccf-2021-04 的第三题我印象中是一道需要解析某种格式的字符串然后根据解析结果进行逻辑判断的题目。这类题目的难点不在于算法而在于你能不能把字符串的每一种情况都考虑到。字符串题让人头疼的原因有三个第一字符串的格式可能很复杂有嵌套结构、有转义字符、有可选部分。你在读题的时候觉得我懂了但实际写代码的时候发现这个情况我没考虑到。第二字符串题的测试数据往往很刁钻出题人会故意构造一些看起来不合法但实际上合法或者看起来合法但实际上不合法的输入来考验你。第三字符串题的调试很麻烦因为你看不到中间状态只能通过输出来判断。如果输出不对你很难定位是哪一步出了问题。4.2 我的字符串解析方法论我做字符串题的时候有一个固定的方法论先写一个分词器把字符串拆成一个个有意义的单元然后再对这些单元进行逻辑处理。举个例子假设题目要求你解析一个类似A(B,C(D,E),F)这样的嵌套结构。你可以先写一个函数把字符串拆成[A, (, B, ,, C, (, D, ,, E, ), ,, F, )]这样的 token 列表然后再用一个栈来处理嵌套关系。def tokenize(s): tokens [] i 0 while i len(s): if s[i] in (),: tokens.append(s[i]) i 1 else: j i while j len(s) and s[j] not in (),: j 1 tokens.append(s[i:j]) i j return tokens这个分词器的逻辑很简单但它能把复杂的字符串解析问题转化成对 token 列表的处理问题大大降低了难度。4.3 递归下降处理嵌套结构的利器如果题目中的字符串有嵌套结构递归下降是一个很好的选择。递归下降的核心思想是为每一种语法结构写一个函数函数内部递归调用其他函数来处理子结构。def parse_expr(tokens, pos): # 解析一个表达式 left parse_term(tokens, pos) while pos len(tokens) and tokens[pos] : pos 1 right parse_term(tokens, pos) left left right return left, pos def parse_term(tokens, pos): # 解析一个项 if tokens[pos] (: pos 1 value, pos parse_expr(tokens, pos) pos 1 # 跳过 ) return value, pos else: return int(tokens[pos]), pos 1这种写法的好处是逻辑清晰每一层只关心自己这一层的逻辑子结构交给下一层处理。缺点是代码量比较大而且需要仔细处理边界情况。注意字符串题最容易出错的地方是空字符串和只有一个字符的字符串。在写代码之前先手动测试这两种情况确保你的代码能正确处理。4.4 调试字符串题的实用技巧调试字符串题的时候我通常会加一些临时的打印语句把中间状态输出出来。比如在分词之后打印 token 列表在解析过程中打印当前处理到的位置和解析结果。这些打印语句在提交之前要删掉但在调试阶段非常有用。另外我建议自己构造一些测试用例包括最简单的合法输入最复杂的合法输入边界情况空输入、只有一个字符、最大长度非法输入如果题目要求处理非法输入的话把这些测试用例都跑一遍如果都能通过那基本上就没问题了。5. 第四题图论与动态规划的硬仗拿分策略比算法本身更重要5.1 第四题的题型分布规律ccf-2021-04 的第四题根据我的记忆和复盘是一道图论或者动态规划的题目。这类题目的特点是算法思路可能不难但实现起来很复杂而且很容易在某个细节上卡住。第四题的题型分布有一个大致的规律如果前三题偏简单第四题就会偏难如果前三题已经很难了第四题反而可能是一道看起来难但实际上有套路的题。ccf-2021-04 这套题前三题的难度中等偏上所以第四题的难度应该是标准困难级别。5.2 图论题的通用解题框架如果第四题是图论题那么解题框架通常是这样的第一步把题目中的场景抽象成图。节点是什么边是什么有向还是无向带权还是不带权第二步确定要求解的问题是什么。是最短路是最小生成树是拓扑排序是连通性判断第三步选择合适的算法。Dijkstra、Floyd、Kruskal、Prim、Tarjan、拓扑排序这些算法的适用场景要烂熟于心。第四步实现算法并处理边界情况。图论题的边界情况包括图不连通、有自环、有重边、节点编号从0开始还是从1开始。# Dijkstra 算法示例 import heapq def dijkstra(graph, start): n len(graph) dist [float(inf)] * n dist[start] 0 pq [(0, start)] while pq: d, u heapq.heappop(pq) if d dist[u]: continue for v, w in graph[u]: if dist[u] w dist[v]: dist[v] dist[u] w heapq.heappush(pq, (dist[v], v)) return dist这个模板我用了很多次基本上所有的单源最短路问题都可以套用。关键是要把图建对把节点编号处理好。5.3 动态规划题的思考路径如果第四题是动态规划题那么思考路径通常是第一步确定状态。状态是什么是前 i 个元素还是以 i 结尾的子序列还是区间 [i, j]第二步确定转移方程。从状态 i 到状态 i1 的转移是什么转移的条件是什么第三步确定初始条件和边界。dp[0] 是什么dp 数组的大小是多少第四步优化空间复杂度如果需要的话。能不能用滚动数组能不能用一维数组代替二维数组动态规划题的难点在于状态定义如果状态定义得不好转移方程就会很复杂甚至写不出来。我的经验是如果一道动态规划题你想了十分钟还没想出状态定义那就换一种思路或者先写一个暴力解法然后看看能不能从暴力解法中提炼出状态。5.4 考场上第四题的拿分策略第四题在考场上的拿分策略非常重要。我的建议是第一先花五分钟读题判断这道题是我能做还是我做不出来。判断的标准是如果你在五分钟内能想到一个可行的算法思路那就值得花时间去做如果你想不出来那就果断放弃把时间留给前三题的检查。第二如果决定做先写一个暴力解法确保能过一部分测试点。暴力解法虽然拿不到满分但能拿到基础分而且能帮你验证你对题目的理解是否正确。第三在暴力解法的基础上进行优化。优化的方向通常是减少重复计算用记忆化搜索或者动态规划、使用更高效的数据结构用堆代替数组、用并查集代替DFS。第四如果优化之后还是过不了所有测试点不要死磕。检查一下是不是边界条件没处理好或者是不是某个细节写错了。如果检查了十五分钟还是找不到问题那就放弃把时间留给其他题。提示第四题的测试数据通常是分梯度的暴力解法能过前几个测试点优化解法能过中间的测试点只有最优解法才能过所有测试点。所以即使你做不出最优解法也不要空着写一个暴力解法至少能拿一部分分。6. 复盘方法做完题之后怎么总结才有效6.1 不要只看对不对要看为什么很多人做完题之后只看一下过了几个测试点然后就扔到一边了。这种复盘方式的效果很差因为你没有从做题中获得任何可以迁移到其他题目的经验。有效的复盘方式是对每一道题问自己三个问题。第一个问题这道题的核心考点是什么是某个算法是某种数据结构还是某种思维方式第二个问题我在做这道题的时候卡在了哪里是读题没读懂是算法想不出来是代码写错了还是边界条件没考虑到第三个问题如果下次遇到类似的题目我能从这次的经验中学到什么这三个问题看起来简单但认真回答一遍你会发现很多平时忽略的问题。6.2 建立自己的错题本我建议每个人都建立一个自己的错题本记录自己做错的题目和做错的原因。错题本不需要很复杂一个简单的表格就够了题目错误类型具体原因改进措施第一题边界条件没考虑 n0 的情况以后先列边界情况第三题逻辑错误嵌套解析时栈的使用有误多练递归下降第四题算法不会没学过 Tarjan 算法补学强连通分量这个表格的价值在于它能帮你发现自己的薄弱环节。如果你发现自己在边界条件上错了很多次那就说明你需要养成先列边界情况的习惯。如果你发现自己在某个算法上错了很多次那就说明你需要专门去学这个算法。6.3 把题解当成学习材料而不是答案很多人看题解的方式是扫一眼思路觉得我懂了然后就关了。这种看题解的方式效果很差因为你只是看懂了并没有学会。正确的看题解方式是先自己写一遍写不出来再看题解看题解的时候不要只看思路要看代码的每一个细节看完之后自己再写一遍不看题解。这个过程很耗时但效果很好。因为你在自己写的过程中会强迫自己理解每一个细节而不是大概懂了。6.4 从做对到做快的进阶路径如果你已经能稳定地做对前三题那么下一步的目标就是做快。做快的关键不是打字速度而是减少思考时间。减少思考时间的方法有两个一是把常用的算法和数据结构练到肌肉记忆的程度看到题目就能想到对应的模板二是积累题型经验看到某种类型的题目就知道大概的解题方向。这两个方法都需要大量的练习但练习的方式很重要。我建议采用限时练习的方式给自己设定一个时间限制比如四十分钟做一道题时间到了就停不管做没做完。然后分析自己在哪个环节花了太多时间下次有针对性地改进。7. 从这套题延伸出去同类题目的练习方向7.1 第一题和第二题的练习方向第一题和第二题考察的是基础能力练习的方向是提高熟练度。我建议每天花二十分钟做一道简单题重点练读题速度和代码准确率。读题速度的提升方法是读题的时候用笔把关键信息划出来比如输入格式、输出格式、数据范围、特殊条件。这样能避免读漏了的情况。代码准确率的提升方法是写代码的时候养成边写边检查的习惯每写完一个函数就检查一下边界条件不要等到全部写完再检查。7.2 第三题的练习方向第三题考察的是字符串处理和逻辑推理能力练习的方向是积累题型。我建议专门找一些字符串解析的题目来练比如表达式求值、JSON 解析、正则表达式匹配等。练习的时候重点练分词和递归下降这两个技巧。这两个技巧能解决大多数字符串解析问题。7.3 第四题的练习方向第四题考察的是算法能力练习的方向是系统学习算法。我建议按照以下顺序学习基础数据结构数组、链表、栈、队列、哈希表基础算法排序、二分查找、双指针、前缀和图论DFS、BFS、最短路、最小生成树、拓扑排序动态规划线性DP、区间DP、背包问题、树形DP高级数据结构并查集、线段树、树状数组、堆每个专题都要做足够的练习题直到能看到题目就知道用什么算法的程度。7.4 模拟考试的重要性最后我强烈建议大家定期进行模拟考试。模拟考试的价值在于它能帮你适应考试的节奏和压力让你在真正的考场上不会因为紧张而发挥失常。模拟考试的时候要严格按照考试的时间和规则来进行四个小时四道题不查资料不讨论。考完之后认真复盘找出自己的薄弱环节然后有针对性地改进。我自己的经验是模拟考试的成绩往往比平时练习的成绩低因为考试的压力会影响你的思考速度和判断力。但经过几次模拟考试之后你的成绩会逐渐稳定下来最终在真正的考场上发挥出正常水平。提示模拟考试之后不要只看分数要看丢分的原因。如果是因为不会做丢分那就去学对应的算法如果是因为粗心丢分那就去练检查的习惯如果是因为时间不够丢分那就去练时间分配的策略。这套 ccf-2021-04 的真题我前前后后做了三遍每一遍都有新的收获。第一遍让我知道了自己的薄弱环节第二遍让我学会了更高效的解题方法第三遍让我能够把这些经验讲给别人听。如果你也在准备类似的考试我建议你不要只做一遍而是隔一段时间再做一遍看看自己有没有进步。