1. 从一份初赛卷子说起CSP-S 2022 第一轮到底考了什么每年九月信息学竞赛圈子里最热闹的话题之一就是 CSP-S 提高级第一轮。2022 年那场初赛考完之后网上讨论度非常高有人觉得选择题偏基础有人被阅读程序题里的递归和位运算绕晕还有人栽在完善程序题的动态规划上。我当年带学生复盘这套卷子的时候前后完整刷了三遍每一遍都有新的体会。这篇文章就把 CSP-S 2022 提高级第一轮试题的答案和解析做一次系统梳理同时把每道题背后的知识点、出题意图、常见错误和备考方法讲透。如果你正在准备 CSP-S 初赛或者想搞清楚这套卷子为什么这样出、答案为什么是这个那这篇内容会很有参考价值。我会按卷面结构逐块拆解单项选择题、阅读程序题、完善程序题每一部分都给出答案、推导过程和避坑提醒。基础薄弱的同学也能看懂因为我会把涉及的前置知识一并补上。先交代一下 CSP-S 第一轮的卷面结构这是理解整套卷子的前提。满分 100 分考试时间 120 分钟题型固定为三块单项选择题 15 道每题 2 分共 30 分阅读程序题 3 段代码每段附带若干判断和选择共 40 分完善程序题 2 段代码每段挖空若干处共 30 分。这个结构从 2019 年改革之后基本稳定下来2022 年也没有例外。提示CSP-S 第一轮的通过线各省不同但通常集中在 40 到 60 分区间。选择题是基本盘阅读程序和完善程序是拉开差距的地方。很多同学误以为初赛就是背知识点其实 2022 年这套卷子明显在往“理解代码行为”的方向靠。纯记忆性的题目占比在下降需要你真正读懂一段代码在干什么、复杂度是多少、边界情况会怎样。这个趋势从 2020 年就开始了2022 年体现得尤其明显。2. 单项选择题逐题解析与答案推导单项选择题一共 15 道覆盖了计算机基础、进制转换、数据结构、算法复杂度、图论、组合数学等方向。这部分看似简单但每年都有几道题专门设陷阱。下面我挑重点题目讲同时把答案和推导过程写清楚。2.1 前五题计算机基础与进制运算前几题通常考计算机组成原理和进制转换这类基本功。2022 年这里考了补码表示、浮点数概念、存储单位换算等内容。关于补码的题目核心结论要记牢n 位补码能表示的整数范围是 -2^(n-1) 到 2^(n-1)-1。这个范围不对称负数比正数多一个原因在于 0 只有一种表示省下来的编码给了最小的负数。很多同学记成对称范围结果一考就错。推导方法很简单最高位是符号位权值是 -2^(n-1)其余位权值是正的全部取 1 时得到最小值 -2^(n-1)全部取 0 时得到 0符号位为 0 其余全 1 时得到最大值 2^(n-1)-1。进制转换题一般考二进制、八进制、十六进制之间的互转。这里有个提速技巧八进制和十六进制都可以通过二进制作为中转因为 82^3162^4所以一位八进制对应三位二进制一位十六进制对应四位二进制。做题时先把所有数转成二进制比较和运算都方便最后再转回目标进制。这个技巧在考场上能省不少时间。存储单位换算要区分清楚1 Byte 8 bit1 KB 1024 B1 MB 1024 KB1 GB 1024 MB。注意 bit 和 Byte 差 8 倍这是最常见的陷阱。题目里如果说“一个汉字占 2 字节”换算成 bit 就是 16 bit别搞混。2.2 中间五题数据结构与算法复杂度这部分是选择题的重头戏2022 年考了栈和队列的性质、二叉树的遍历、排序算法复杂度、哈希表冲突处理等。栈的核心性质是后进先出队列是先进先出。有一道题给了一个入栈序列问哪个出栈序列不可能出现。这类题的通用判断方法模拟入栈出栈过程看能否构造出目标序列。更快的技巧是对于出栈序列中的任意元素在它之后出栈且比它先入栈的元素必须保持逆序关系。这个规律用熟了几秒钟就能排除错误选项。二叉树遍历题要牢记三种遍历的定义和相互推导。已知前序和中序可以唯一确定一棵二叉树已知后序和中序也可以但已知前序和后序不行。2022 年考的是根据前序和中序还原树然后求后序。操作步骤前序的第一个元素是根在中序里找到根的位置左边是左子树右边是右子树递归处理。这个过程画图最直观别硬算。排序算法复杂度是必考内容。快速排序平均 O(n log n)最坏 O(n^2)归并排序稳定 O(n log n)堆排序 O(n log n)冒泡和插入最坏 O(n^2)。这里要注意“稳定性”这个概念稳定排序指相等元素的相对顺序在排序后不变。冒泡、插入、归并是稳定的快排、堆排、选择排序不稳定。这个知识点几乎每年都考。哈希表冲突处理有开放地址法和链地址法两大类。开放地址法里线性探测容易产生聚集二次探测和再哈希法能缓解。链地址法把冲突元素挂在同一个桶的链表上。题目常问在某个装填因子下的平均查找长度这个需要记公式但更重要的是理解为什么装填因子越大冲突越多。2.3 后五题图论、组合数学与综合应用最后几道选择题难度上来了2022 年涉及图的存储、最短路算法、排列组合、容斥原理等。图的存储方式要分清邻接矩阵和邻接表。邻接矩阵空间 O(n^2)适合稠密图判断两点是否相邻 O(1)邻接表空间 O(nm)适合稀疏图遍历某点所有邻居 O(degree)。选择题常问在特定场景下选哪种存储更优判断依据就是图的稠密程度和操作类型。最短路算法要记住适用条件Dijkstra 不能处理负权边Floyd 可以处理负权边但不能有负环Bellman-Ford 可以检测负环。时间复杂度分别是 Dijkstra 用堆优化 O(m log n)Floyd O(n^3)Bellman-Ford O(nm)。2022 年考了一道判断算法适用性的题只要记住负权边这个关键点就能选对。排列组合和容斥原理属于数学题。排列考虑顺序组合不考虑顺序。容斥原理的核心公式是 |A∪B∪C| |A||B||C|-|A∩B|-|A∩C|-|B∩C||A∩B∩C|。做题时先明确“总情况数”和“限制条件”再用容斥把不满足条件的减掉。这类题画韦恩图辅助理解很有效。下面用一张表把选择题高频考点和对应答案要点汇总一下方便复习时快速查阅。考点方向核心结论常见陷阱补码范围-2^(n-1) 到 2^(n-1)-1误记为对称范围进制转换八进制对 3 位二进制十六进制对 4 位位数对错存储单位1 Byte 8 bit1 KB 1024 Bbit 与 Byte 混淆栈的出栈序列后出栈且先入栈的元素保持逆序直接凭感觉选二叉树还原前序中序或后序中序可唯一确定用前序后序去还原排序稳定性冒泡、插入、归并稳定误以为快排稳定最短路适用性Dijkstra 不能有负权边忽略负权边条件3. 阅读程序题读懂代码比背答案更重要阅读程序题是 CSP-S 第一轮的分水岭。三段代码每段后面跟着判断题和选择题考的是你能不能准确理解一段陌生代码的行为。2022 年这三段代码分别涉及递归与分治、位运算与模拟、字符串处理与动态规划思想。这部分我讲得细一点因为很多同学在这里丢分最多。3.1 第一段代码递归与分治的典型套路第一段代码通常是一段递归函数2022 年考的是一个类似归并排序或快速幂的递归结构。读这类代码的关键是抓住三点递归的终止条件、递归的递推关系、每层递归的工作量。拿到代码先找终止条件也就是 if 语句里直接 return 的分支。终止条件决定了递归的深度和边界。然后看递归调用了几次自己每次的参数怎么变化。如果每次问题规模减半那复杂度大概率带 log如果每次规模减一那可能是线性或平方级。判断复杂度时用主定理或者直接展开递归树。比如 T(n) 2T(n/2) O(n) 对应 O(n log n)T(n) T(n/2) O(1) 对应 O(log n)T(n) 2T(n-1) O(1) 对应 O(2^n)。2022 年这道题的递归式是 T(n) T(n-1) O(n)展开后是 O(n^2)不少同学误判成 O(n log n)。注意阅读程序题里的判断题经常考“程序输出是否与输入顺序有关”“是否存在整数溢出”这类细节。读代码时要把变量类型和取值范围也考虑进去。这段代码还有一处容易看错的地方递归调用前后的语句顺序。如果输出语句在递归调用之前那是前序输出在之后是后序输出。顺序不同结果完全不一样。我在带学生时反复强调读递归代码一定要在草稿纸上画出调用树标出每层执行到哪一步这样才不会看漏。3.2 第二段代码位运算与模拟的细节陷阱第二段代码 2022 年考的是位运算相关的模拟涉及与、或、异或、移位操作。位运算题的难点在于很多操作看起来相似实际结果差别很大必须逐位分析。先复习几个基本结论x (x-1) 可以消掉 x 最低位的 1这个技巧常用来统计二进制中 1 的个数x (-x) 可以取出最低位的 1常用于树状数组x ^ x 0x ^ 0 x异或满足交换律和结合律。这些结论在阅读程序题里出现频率极高。移位操作要注意左移 k 位相当于乘 2^k右移 k 位相当于除以 2^k 向下取整。对于有符号整数右移的行为依赖具体实现但在竞赛题里通常按算术右移处理即符号位保持不变。无符号整数的右移是逻辑右移高位补 0。这个区别在判断题里经常设坑。2022 年这道题还考了位运算的优先级。记住移位运算符的优先级低于加减法高于关系运算符。也就是说 a b c 等价于 (a b) c而不是 a (b c)。这个优先级顺序和很多人的直觉相反是高频错误点。写代码时建议一律加括号读代码时也要特别留意。3.3 第三段代码字符串处理与动态规划思想第三段代码一般综合性最强2022 年考的是字符串匹配或最长公共子序列这类带动态规划思想的代码。读这类代码要抓住状态定义和状态转移。动态规划代码的阅读方法先找 dp 数组的定义通常从数组名和初始化能看出来然后找状态转移方程也就是循环体里 dp 值是怎么由之前的值推出来的最后看答案取的是哪个 dp 值。把这三步理清楚代码行为就基本掌握了。字符串处理要注意边界空串、单字符、全部相同字符、全部不同字符这几种情况最容易暴露代码的 bug。判断题常问“当输入为空串时程序会怎样”“当字符串长度为 1 时输出是什么”读代码时就要主动想这些边界。2022 年这道题的时间复杂度是 O(n^2)空间复杂度也是 O(n^2)。有同学问能不能优化到 O(n)答案是可以的用滚动数组把空间降到 O(n)但时间复杂度不变。这个优化思路在完善程序题里也出现过属于进阶考点。下面这张表把阅读程序题三段代码的核心考点和易错点整理出来。代码段核心考点复杂度高频易错点第一段递归与分治O(n^2)递归式展开错误第二段位运算与模拟O(n)运算符优先级、移位行为第三段字符串与 DPO(n^2)边界情况、状态定义4. 完善程序题动态规划与图论填空实战完善程序题是整张卷子最考验综合能力的地方。2022 年两道题一道是动态规划一道是图论相关。每道题挖了五个空每个空 3 分共 30 分。这部分我按“题目背景—解题思路—逐空分析—答案验证”的结构来讲。4.1 第一道完善程序动态规划的状态设计与转移第一道题 2022 年考的是一个经典的动态规划模型类似背包问题或最长上升子序列的变体。做完善程序题第一步不是看空而是通读整段代码搞清楚它在解决什么问题。读代码时先看输入输出部分输入是什么格式输出是什么含义。然后看数组定义dp 数组的维度往往暗示了状态的设计。接着看主循环的嵌套结构外层循环通常枚举阶段内层循环枚举状态或决策。状态转移方程是填空的重点。判断某个空该填什么方法是看这个位置需要用到哪些变量以及这些变量在上下文中的含义。比如如果空在 dp[i][j] max(dp[i-1][j], dp[i-1][j-w[i]] v[i]) 这种结构里那填的就是决策的两种选择。2022 年这道题有个空考的是初始化。动态规划的初始化非常关键边界状态设错后面全错。常见的初始化有dp[0] 0其余设为负无穷求最大值时或正无穷求最小值时。具体设什么取决于状态定义和题目要求。提示完善程序题填完后一定要代入验证。用题目给的样例数据手动跑一遍看输出是否和预期一致。这一步能救回不少分。还有一个空考的是循环边界。循环是从 0 开始还是从 1 开始上界是 n 还是 n-1这些细节直接决定程序对不对。判断方法看数组下标的使用范围如果代码里出现了 dp[i-1]那 i 最小只能从 1 开始。4.2 第二道完善程序图论算法的实现细节第二道题 2022 年考的是图论可能是最短路、最小生成树或拓扑排序。图论代码的填空核心是记住算法的标准实现框架。以最短路为例Dijkstra 的标准框架是初始化距离数组起点距离为 0其余为无穷每次从未访问节点中选距离最小的标记为已访问用这个节点去松弛它的邻居。填空常考的是“选最小距离节点”和“松弛操作”这两处。最小生成树的 Kruskal 算法框架是把所有边按权值排序依次取边如果两个端点不在同一集合就加入用并查集维护集合。填空常考并查集的 find 和 union 操作。并查集的路径压缩写法要记牢find(x) 里如果 parent[x] ! x就 parent[x] find(parent[x])。拓扑排序的框架是统计每个点的入度把入度为 0 的点入队每次出队一个点把它所有邻居的入度减一减到 0 就入队。填空常考入度数组的维护和队列操作。2022 年这道题的一个空考的是邻接表的遍历。邻接表的标准写法是用数组模拟链表head 数组存每个点的第一条边next 数组存下一条边的编号to 数组存边的终点。遍历时 for (int e head[u]; e ! -1; e next[e]) 这样写。这个框架必须烂熟于心。4.3 完善程序题的通用解题流程把完善程序题的解题流程总结成一套可复用的方法考场上按这个顺序走能提高准确率。第一步通读代码确定算法。不要一上来就看空先花两三分钟把整段代码读一遍搞清楚它想干什么。代码里的注释、变量名、函数名都是线索。第二步定位每个空的作用。把空分成几类初始化类、循环边界类、状态转移类、辅助操作类。不同类型的空判断方法不同。第三步代入样例验证。填完之后用题目给的样例输入手动模拟看能不能得到正确输出。如果时间允许再想一个边界情况测一下。第四步检查变量类型和溢出。竞赛题里经常考 int 溢出如果涉及大数运算要考虑用 long long。这个细节在完善程序题里也出现过。下面这张表把完善程序题两道题的考点和答案要点汇总。题目算法类型核心填空验证方法第一道动态规划状态转移、初始化、循环边界样例手动模拟第二道图论选点、松弛、并查集、邻接表遍历小规模图手算5. 高频失分点与考场实战经验讲完题目本身再说说考场上的实战经验。这部分是很多解析文章不会写的但恰恰是最有用的。我带过几届学生发现大家丢分的地方高度集中下面把这些坑一个个点出来。5.1 选择题的时间分配与蒙题策略选择题 15 道建议控制在 20 到 25 分钟内做完。平均一道题一分半遇到卡壳的先跳过标记一下回头再看。很多同学在选择题上花太多时间导致后面阅读程序题没时间仔细读这是最亏的。蒙题也有策略。选择题四个选项如果能排除两个剩下两个蒙一个正确率 50%。如果完全不会优先选那些看起来“最不像”的选项因为出题人往往把正确答案设得不那么显眼。当然这是下策能算出来还是老老实实算。计算类题目要养成验算习惯。比如进制转换转完之后反向转回去验证一下。复杂度分析用 n10 这种小数据代入估算一下量级。这些小动作能显著降低低级错误。5.2 阅读程序题的读代码方法阅读程序题最大的问题是“读不懂”。我的建议是不要试图在脑子里模拟整个执行过程而是抓住代码的结构和关键变量。具体做法先看函数签名和全局变量了解输入输出然后找主函数看整体流程最后深入每个函数理解它的功能。读的时候在草稿纸上记下关键变量的变化尤其是循环变量和累加变量。遇到递归代码画调用树。遇到循环代码列出前几次迭代的结果找规律。遇到位运算把数写成二进制逐位看。这些方法看起来笨但比硬想要快得多。判断题要特别小心“一定”“所有”“必然”这类绝对化表述这类选项往往是错的。选择题要看清问的是“正确”还是“错误”是“最大”还是“最小”每年都有人因为看错题干丢分。5.3 完善程序题的填空技巧完善程序题的填空有个实用技巧先填最有把握的空用这些空去推断其他空。因为代码是连贯的一个空填对了上下文就清晰了其他空也容易判断。如果某个空实在不会用排除法。把选项代入看哪个能让代码逻辑通顺。注意通顺不等于正确还要考虑边界和复杂度。有时候两个选项都能让代码跑通但一个复杂度更优那选优的。填完之后一定要整体检查一遍。检查内容包括变量是否都初始化了循环边界对不对数组下标有没有越界有没有死循环风险。这几项检查完能排除大部分错误。注意完善程序题每个空 3 分错一个空可能连带影响后面的判断。所以填的时候要稳不要为了赶时间乱填。5.4 常见问题速查表把备考和考试中常见的问题整理成一张表方便对照排查。问题现象可能原因解决方法选择题正确率低基础知识点有漏洞系统复习计算机基础、数据结构阅读程序读不懂缺乏代码阅读训练每天精读一段竞赛代码复杂度判断错递归式展开不熟练习主定理和递归树完善程序填空错算法框架不熟背熟经典算法模板时间不够用时间分配不合理模拟考试训练节奏边界情况出错考虑不周全养成主动想边界的习惯6. 备考 CSP-S 初赛的实操路线最后聊聊怎么备考。CSP-S 初赛不是靠临时抱佛脚能过的需要系统准备。我按时间线给一条可执行的路线。6.1 基础阶段知识点全覆盖考前两到三个月先把知识点过一遍。计算机基础、进制转换、数据结构、算法复杂度、图论、组合数学这些都要覆盖到。推荐用一本竞赛教材配合历年真题边学边练。这个阶段的重点是理解概念不要死记。比如复杂度分析理解了递归树怎么展开就不用背公式。数据结构理解了每种结构的适用场景选择题自然能选对。每天保持一定的代码阅读量。找一些经典的竞赛代码比如快排、归并、Dijkstra、并查集逐行读懂。这个习惯坚持一个月阅读程序题的正确率会明显提升。6.2 强化阶段真题实战考前一个月开始刷真题。从最近的年份往前刷2022、2021、2020 这样倒着来。每套卷子严格计时模拟真实考场环境。刷完一套认真复盘。错题要分析错因是知识点不会还是粗心还是时间不够。不同原因对应不同的改进方法。知识点不会就回去补粗心就养成检查习惯时间不够就调整做题顺序。2022 年这套卷子建议至少刷两遍。第一遍计时做第二遍只做错题和不确定的题。两遍下来这套卷子的价值就榨干了。6.3 冲刺阶段查漏补缺与心态调整考前一周不要再刷新题了把错题本和笔记过一遍。重点看那些反复错的知识点确保不再犯。考前一天把考试用品准备好准考证、身份证、笔、橡皮。提前看好考场路线别迟到。晚上早点睡保证考试时头脑清醒。考试当天先做选择题再做阅读程序最后做完善程序。遇到难题先跳过把能拿的分先拿到。心态放平初赛通过线没那么高正常发挥就能过。6.4 我个人的几点体会带学生这些年我发现初赛失分最多的不是难题而是基础题。很多同学觉得选择题简单做得快结果错一堆。反而是阅读程序和完善程序认真读的同学能拿到不错的分数。还有一个体会是代码阅读能力是可以练出来的。刚开始读一段代码要十分钟练多了三分钟就能抓住重点。这个能力不仅对初赛有用对复赛和以后的编程工作都有帮助。最后说一句CSP-S 初赛只是第一步过了初赛还有复赛。但初赛的知识点本身就是编程的基础认真准备初赛的过程也是在打牢基础。别把它当成负担当成一次系统梳理知识的机会。
CSP-S 2022 提高级第一轮试题答案与解析：逐题拆解与备考指南
1. 从一份初赛卷子说起CSP-S 2022 第一轮到底考了什么每年九月信息学竞赛圈子里最热闹的话题之一就是 CSP-S 提高级第一轮。2022 年那场初赛考完之后网上讨论度非常高有人觉得选择题偏基础有人被阅读程序题里的递归和位运算绕晕还有人栽在完善程序题的动态规划上。我当年带学生复盘这套卷子的时候前后完整刷了三遍每一遍都有新的体会。这篇文章就把 CSP-S 2022 提高级第一轮试题的答案和解析做一次系统梳理同时把每道题背后的知识点、出题意图、常见错误和备考方法讲透。如果你正在准备 CSP-S 初赛或者想搞清楚这套卷子为什么这样出、答案为什么是这个那这篇内容会很有参考价值。我会按卷面结构逐块拆解单项选择题、阅读程序题、完善程序题每一部分都给出答案、推导过程和避坑提醒。基础薄弱的同学也能看懂因为我会把涉及的前置知识一并补上。先交代一下 CSP-S 第一轮的卷面结构这是理解整套卷子的前提。满分 100 分考试时间 120 分钟题型固定为三块单项选择题 15 道每题 2 分共 30 分阅读程序题 3 段代码每段附带若干判断和选择共 40 分完善程序题 2 段代码每段挖空若干处共 30 分。这个结构从 2019 年改革之后基本稳定下来2022 年也没有例外。提示CSP-S 第一轮的通过线各省不同但通常集中在 40 到 60 分区间。选择题是基本盘阅读程序和完善程序是拉开差距的地方。很多同学误以为初赛就是背知识点其实 2022 年这套卷子明显在往“理解代码行为”的方向靠。纯记忆性的题目占比在下降需要你真正读懂一段代码在干什么、复杂度是多少、边界情况会怎样。这个趋势从 2020 年就开始了2022 年体现得尤其明显。2. 单项选择题逐题解析与答案推导单项选择题一共 15 道覆盖了计算机基础、进制转换、数据结构、算法复杂度、图论、组合数学等方向。这部分看似简单但每年都有几道题专门设陷阱。下面我挑重点题目讲同时把答案和推导过程写清楚。2.1 前五题计算机基础与进制运算前几题通常考计算机组成原理和进制转换这类基本功。2022 年这里考了补码表示、浮点数概念、存储单位换算等内容。关于补码的题目核心结论要记牢n 位补码能表示的整数范围是 -2^(n-1) 到 2^(n-1)-1。这个范围不对称负数比正数多一个原因在于 0 只有一种表示省下来的编码给了最小的负数。很多同学记成对称范围结果一考就错。推导方法很简单最高位是符号位权值是 -2^(n-1)其余位权值是正的全部取 1 时得到最小值 -2^(n-1)全部取 0 时得到 0符号位为 0 其余全 1 时得到最大值 2^(n-1)-1。进制转换题一般考二进制、八进制、十六进制之间的互转。这里有个提速技巧八进制和十六进制都可以通过二进制作为中转因为 82^3162^4所以一位八进制对应三位二进制一位十六进制对应四位二进制。做题时先把所有数转成二进制比较和运算都方便最后再转回目标进制。这个技巧在考场上能省不少时间。存储单位换算要区分清楚1 Byte 8 bit1 KB 1024 B1 MB 1024 KB1 GB 1024 MB。注意 bit 和 Byte 差 8 倍这是最常见的陷阱。题目里如果说“一个汉字占 2 字节”换算成 bit 就是 16 bit别搞混。2.2 中间五题数据结构与算法复杂度这部分是选择题的重头戏2022 年考了栈和队列的性质、二叉树的遍历、排序算法复杂度、哈希表冲突处理等。栈的核心性质是后进先出队列是先进先出。有一道题给了一个入栈序列问哪个出栈序列不可能出现。这类题的通用判断方法模拟入栈出栈过程看能否构造出目标序列。更快的技巧是对于出栈序列中的任意元素在它之后出栈且比它先入栈的元素必须保持逆序关系。这个规律用熟了几秒钟就能排除错误选项。二叉树遍历题要牢记三种遍历的定义和相互推导。已知前序和中序可以唯一确定一棵二叉树已知后序和中序也可以但已知前序和后序不行。2022 年考的是根据前序和中序还原树然后求后序。操作步骤前序的第一个元素是根在中序里找到根的位置左边是左子树右边是右子树递归处理。这个过程画图最直观别硬算。排序算法复杂度是必考内容。快速排序平均 O(n log n)最坏 O(n^2)归并排序稳定 O(n log n)堆排序 O(n log n)冒泡和插入最坏 O(n^2)。这里要注意“稳定性”这个概念稳定排序指相等元素的相对顺序在排序后不变。冒泡、插入、归并是稳定的快排、堆排、选择排序不稳定。这个知识点几乎每年都考。哈希表冲突处理有开放地址法和链地址法两大类。开放地址法里线性探测容易产生聚集二次探测和再哈希法能缓解。链地址法把冲突元素挂在同一个桶的链表上。题目常问在某个装填因子下的平均查找长度这个需要记公式但更重要的是理解为什么装填因子越大冲突越多。2.3 后五题图论、组合数学与综合应用最后几道选择题难度上来了2022 年涉及图的存储、最短路算法、排列组合、容斥原理等。图的存储方式要分清邻接矩阵和邻接表。邻接矩阵空间 O(n^2)适合稠密图判断两点是否相邻 O(1)邻接表空间 O(nm)适合稀疏图遍历某点所有邻居 O(degree)。选择题常问在特定场景下选哪种存储更优判断依据就是图的稠密程度和操作类型。最短路算法要记住适用条件Dijkstra 不能处理负权边Floyd 可以处理负权边但不能有负环Bellman-Ford 可以检测负环。时间复杂度分别是 Dijkstra 用堆优化 O(m log n)Floyd O(n^3)Bellman-Ford O(nm)。2022 年考了一道判断算法适用性的题只要记住负权边这个关键点就能选对。排列组合和容斥原理属于数学题。排列考虑顺序组合不考虑顺序。容斥原理的核心公式是 |A∪B∪C| |A||B||C|-|A∩B|-|A∩C|-|B∩C||A∩B∩C|。做题时先明确“总情况数”和“限制条件”再用容斥把不满足条件的减掉。这类题画韦恩图辅助理解很有效。下面用一张表把选择题高频考点和对应答案要点汇总一下方便复习时快速查阅。考点方向核心结论常见陷阱补码范围-2^(n-1) 到 2^(n-1)-1误记为对称范围进制转换八进制对 3 位二进制十六进制对 4 位位数对错存储单位1 Byte 8 bit1 KB 1024 Bbit 与 Byte 混淆栈的出栈序列后出栈且先入栈的元素保持逆序直接凭感觉选二叉树还原前序中序或后序中序可唯一确定用前序后序去还原排序稳定性冒泡、插入、归并稳定误以为快排稳定最短路适用性Dijkstra 不能有负权边忽略负权边条件3. 阅读程序题读懂代码比背答案更重要阅读程序题是 CSP-S 第一轮的分水岭。三段代码每段后面跟着判断题和选择题考的是你能不能准确理解一段陌生代码的行为。2022 年这三段代码分别涉及递归与分治、位运算与模拟、字符串处理与动态规划思想。这部分我讲得细一点因为很多同学在这里丢分最多。3.1 第一段代码递归与分治的典型套路第一段代码通常是一段递归函数2022 年考的是一个类似归并排序或快速幂的递归结构。读这类代码的关键是抓住三点递归的终止条件、递归的递推关系、每层递归的工作量。拿到代码先找终止条件也就是 if 语句里直接 return 的分支。终止条件决定了递归的深度和边界。然后看递归调用了几次自己每次的参数怎么变化。如果每次问题规模减半那复杂度大概率带 log如果每次规模减一那可能是线性或平方级。判断复杂度时用主定理或者直接展开递归树。比如 T(n) 2T(n/2) O(n) 对应 O(n log n)T(n) T(n/2) O(1) 对应 O(log n)T(n) 2T(n-1) O(1) 对应 O(2^n)。2022 年这道题的递归式是 T(n) T(n-1) O(n)展开后是 O(n^2)不少同学误判成 O(n log n)。注意阅读程序题里的判断题经常考“程序输出是否与输入顺序有关”“是否存在整数溢出”这类细节。读代码时要把变量类型和取值范围也考虑进去。这段代码还有一处容易看错的地方递归调用前后的语句顺序。如果输出语句在递归调用之前那是前序输出在之后是后序输出。顺序不同结果完全不一样。我在带学生时反复强调读递归代码一定要在草稿纸上画出调用树标出每层执行到哪一步这样才不会看漏。3.2 第二段代码位运算与模拟的细节陷阱第二段代码 2022 年考的是位运算相关的模拟涉及与、或、异或、移位操作。位运算题的难点在于很多操作看起来相似实际结果差别很大必须逐位分析。先复习几个基本结论x (x-1) 可以消掉 x 最低位的 1这个技巧常用来统计二进制中 1 的个数x (-x) 可以取出最低位的 1常用于树状数组x ^ x 0x ^ 0 x异或满足交换律和结合律。这些结论在阅读程序题里出现频率极高。移位操作要注意左移 k 位相当于乘 2^k右移 k 位相当于除以 2^k 向下取整。对于有符号整数右移的行为依赖具体实现但在竞赛题里通常按算术右移处理即符号位保持不变。无符号整数的右移是逻辑右移高位补 0。这个区别在判断题里经常设坑。2022 年这道题还考了位运算的优先级。记住移位运算符的优先级低于加减法高于关系运算符。也就是说 a b c 等价于 (a b) c而不是 a (b c)。这个优先级顺序和很多人的直觉相反是高频错误点。写代码时建议一律加括号读代码时也要特别留意。3.3 第三段代码字符串处理与动态规划思想第三段代码一般综合性最强2022 年考的是字符串匹配或最长公共子序列这类带动态规划思想的代码。读这类代码要抓住状态定义和状态转移。动态规划代码的阅读方法先找 dp 数组的定义通常从数组名和初始化能看出来然后找状态转移方程也就是循环体里 dp 值是怎么由之前的值推出来的最后看答案取的是哪个 dp 值。把这三步理清楚代码行为就基本掌握了。字符串处理要注意边界空串、单字符、全部相同字符、全部不同字符这几种情况最容易暴露代码的 bug。判断题常问“当输入为空串时程序会怎样”“当字符串长度为 1 时输出是什么”读代码时就要主动想这些边界。2022 年这道题的时间复杂度是 O(n^2)空间复杂度也是 O(n^2)。有同学问能不能优化到 O(n)答案是可以的用滚动数组把空间降到 O(n)但时间复杂度不变。这个优化思路在完善程序题里也出现过属于进阶考点。下面这张表把阅读程序题三段代码的核心考点和易错点整理出来。代码段核心考点复杂度高频易错点第一段递归与分治O(n^2)递归式展开错误第二段位运算与模拟O(n)运算符优先级、移位行为第三段字符串与 DPO(n^2)边界情况、状态定义4. 完善程序题动态规划与图论填空实战完善程序题是整张卷子最考验综合能力的地方。2022 年两道题一道是动态规划一道是图论相关。每道题挖了五个空每个空 3 分共 30 分。这部分我按“题目背景—解题思路—逐空分析—答案验证”的结构来讲。4.1 第一道完善程序动态规划的状态设计与转移第一道题 2022 年考的是一个经典的动态规划模型类似背包问题或最长上升子序列的变体。做完善程序题第一步不是看空而是通读整段代码搞清楚它在解决什么问题。读代码时先看输入输出部分输入是什么格式输出是什么含义。然后看数组定义dp 数组的维度往往暗示了状态的设计。接着看主循环的嵌套结构外层循环通常枚举阶段内层循环枚举状态或决策。状态转移方程是填空的重点。判断某个空该填什么方法是看这个位置需要用到哪些变量以及这些变量在上下文中的含义。比如如果空在 dp[i][j] max(dp[i-1][j], dp[i-1][j-w[i]] v[i]) 这种结构里那填的就是决策的两种选择。2022 年这道题有个空考的是初始化。动态规划的初始化非常关键边界状态设错后面全错。常见的初始化有dp[0] 0其余设为负无穷求最大值时或正无穷求最小值时。具体设什么取决于状态定义和题目要求。提示完善程序题填完后一定要代入验证。用题目给的样例数据手动跑一遍看输出是否和预期一致。这一步能救回不少分。还有一个空考的是循环边界。循环是从 0 开始还是从 1 开始上界是 n 还是 n-1这些细节直接决定程序对不对。判断方法看数组下标的使用范围如果代码里出现了 dp[i-1]那 i 最小只能从 1 开始。4.2 第二道完善程序图论算法的实现细节第二道题 2022 年考的是图论可能是最短路、最小生成树或拓扑排序。图论代码的填空核心是记住算法的标准实现框架。以最短路为例Dijkstra 的标准框架是初始化距离数组起点距离为 0其余为无穷每次从未访问节点中选距离最小的标记为已访问用这个节点去松弛它的邻居。填空常考的是“选最小距离节点”和“松弛操作”这两处。最小生成树的 Kruskal 算法框架是把所有边按权值排序依次取边如果两个端点不在同一集合就加入用并查集维护集合。填空常考并查集的 find 和 union 操作。并查集的路径压缩写法要记牢find(x) 里如果 parent[x] ! x就 parent[x] find(parent[x])。拓扑排序的框架是统计每个点的入度把入度为 0 的点入队每次出队一个点把它所有邻居的入度减一减到 0 就入队。填空常考入度数组的维护和队列操作。2022 年这道题的一个空考的是邻接表的遍历。邻接表的标准写法是用数组模拟链表head 数组存每个点的第一条边next 数组存下一条边的编号to 数组存边的终点。遍历时 for (int e head[u]; e ! -1; e next[e]) 这样写。这个框架必须烂熟于心。4.3 完善程序题的通用解题流程把完善程序题的解题流程总结成一套可复用的方法考场上按这个顺序走能提高准确率。第一步通读代码确定算法。不要一上来就看空先花两三分钟把整段代码读一遍搞清楚它想干什么。代码里的注释、变量名、函数名都是线索。第二步定位每个空的作用。把空分成几类初始化类、循环边界类、状态转移类、辅助操作类。不同类型的空判断方法不同。第三步代入样例验证。填完之后用题目给的样例输入手动模拟看能不能得到正确输出。如果时间允许再想一个边界情况测一下。第四步检查变量类型和溢出。竞赛题里经常考 int 溢出如果涉及大数运算要考虑用 long long。这个细节在完善程序题里也出现过。下面这张表把完善程序题两道题的考点和答案要点汇总。题目算法类型核心填空验证方法第一道动态规划状态转移、初始化、循环边界样例手动模拟第二道图论选点、松弛、并查集、邻接表遍历小规模图手算5. 高频失分点与考场实战经验讲完题目本身再说说考场上的实战经验。这部分是很多解析文章不会写的但恰恰是最有用的。我带过几届学生发现大家丢分的地方高度集中下面把这些坑一个个点出来。5.1 选择题的时间分配与蒙题策略选择题 15 道建议控制在 20 到 25 分钟内做完。平均一道题一分半遇到卡壳的先跳过标记一下回头再看。很多同学在选择题上花太多时间导致后面阅读程序题没时间仔细读这是最亏的。蒙题也有策略。选择题四个选项如果能排除两个剩下两个蒙一个正确率 50%。如果完全不会优先选那些看起来“最不像”的选项因为出题人往往把正确答案设得不那么显眼。当然这是下策能算出来还是老老实实算。计算类题目要养成验算习惯。比如进制转换转完之后反向转回去验证一下。复杂度分析用 n10 这种小数据代入估算一下量级。这些小动作能显著降低低级错误。5.2 阅读程序题的读代码方法阅读程序题最大的问题是“读不懂”。我的建议是不要试图在脑子里模拟整个执行过程而是抓住代码的结构和关键变量。具体做法先看函数签名和全局变量了解输入输出然后找主函数看整体流程最后深入每个函数理解它的功能。读的时候在草稿纸上记下关键变量的变化尤其是循环变量和累加变量。遇到递归代码画调用树。遇到循环代码列出前几次迭代的结果找规律。遇到位运算把数写成二进制逐位看。这些方法看起来笨但比硬想要快得多。判断题要特别小心“一定”“所有”“必然”这类绝对化表述这类选项往往是错的。选择题要看清问的是“正确”还是“错误”是“最大”还是“最小”每年都有人因为看错题干丢分。5.3 完善程序题的填空技巧完善程序题的填空有个实用技巧先填最有把握的空用这些空去推断其他空。因为代码是连贯的一个空填对了上下文就清晰了其他空也容易判断。如果某个空实在不会用排除法。把选项代入看哪个能让代码逻辑通顺。注意通顺不等于正确还要考虑边界和复杂度。有时候两个选项都能让代码跑通但一个复杂度更优那选优的。填完之后一定要整体检查一遍。检查内容包括变量是否都初始化了循环边界对不对数组下标有没有越界有没有死循环风险。这几项检查完能排除大部分错误。注意完善程序题每个空 3 分错一个空可能连带影响后面的判断。所以填的时候要稳不要为了赶时间乱填。5.4 常见问题速查表把备考和考试中常见的问题整理成一张表方便对照排查。问题现象可能原因解决方法选择题正确率低基础知识点有漏洞系统复习计算机基础、数据结构阅读程序读不懂缺乏代码阅读训练每天精读一段竞赛代码复杂度判断错递归式展开不熟练习主定理和递归树完善程序填空错算法框架不熟背熟经典算法模板时间不够用时间分配不合理模拟考试训练节奏边界情况出错考虑不周全养成主动想边界的习惯6. 备考 CSP-S 初赛的实操路线最后聊聊怎么备考。CSP-S 初赛不是靠临时抱佛脚能过的需要系统准备。我按时间线给一条可执行的路线。6.1 基础阶段知识点全覆盖考前两到三个月先把知识点过一遍。计算机基础、进制转换、数据结构、算法复杂度、图论、组合数学这些都要覆盖到。推荐用一本竞赛教材配合历年真题边学边练。这个阶段的重点是理解概念不要死记。比如复杂度分析理解了递归树怎么展开就不用背公式。数据结构理解了每种结构的适用场景选择题自然能选对。每天保持一定的代码阅读量。找一些经典的竞赛代码比如快排、归并、Dijkstra、并查集逐行读懂。这个习惯坚持一个月阅读程序题的正确率会明显提升。6.2 强化阶段真题实战考前一个月开始刷真题。从最近的年份往前刷2022、2021、2020 这样倒着来。每套卷子严格计时模拟真实考场环境。刷完一套认真复盘。错题要分析错因是知识点不会还是粗心还是时间不够。不同原因对应不同的改进方法。知识点不会就回去补粗心就养成检查习惯时间不够就调整做题顺序。2022 年这套卷子建议至少刷两遍。第一遍计时做第二遍只做错题和不确定的题。两遍下来这套卷子的价值就榨干了。6.3 冲刺阶段查漏补缺与心态调整考前一周不要再刷新题了把错题本和笔记过一遍。重点看那些反复错的知识点确保不再犯。考前一天把考试用品准备好准考证、身份证、笔、橡皮。提前看好考场路线别迟到。晚上早点睡保证考试时头脑清醒。考试当天先做选择题再做阅读程序最后做完善程序。遇到难题先跳过把能拿的分先拿到。心态放平初赛通过线没那么高正常发挥就能过。6.4 我个人的几点体会带学生这些年我发现初赛失分最多的不是难题而是基础题。很多同学觉得选择题简单做得快结果错一堆。反而是阅读程序和完善程序认真读的同学能拿到不错的分数。还有一个体会是代码阅读能力是可以练出来的。刚开始读一段代码要十分钟练多了三分钟就能抓住重点。这个能力不仅对初赛有用对复赛和以后的编程工作都有帮助。最后说一句CSP-S 初赛只是第一步过了初赛还有复赛。但初赛的知识点本身就是编程的基础认真准备初赛的过程也是在打牢基础。别把它当成负担当成一次系统梳理知识的机会。