老看到家长和学生在问“CSP-J需要掌握的算法到底有哪些”搜一圈发现要么是太泛的目录要么就是直接甩题号根本不知道从哪儿下手。我自己带过几年信奥集训队也带自己家娃完整走完一轮CSP-J从入门到拿奖的过程这篇文章就把我实际教学和陪跑中反复用到的算法清单、优先级排序、以及最容易踩的坑一次性说清楚。它不是那种“考纲复制粘贴”而是告诉你哪些算法是必须滚瓜烂熟的哪些是学了纯属浪费时间的以及每个算法到底在CSP-J里是怎么被出题人拿来“变着花样考”的。先说一个很多人没意识到的事实CSP-J的算法部分真正需要你“掌握得很深”的其实不超过10个。剩下的大量内容要么是数据结构的底层知识要么是会被包装成“算法题”的数学思维题。2025年的初赛大纲和往年相比并没有发生颠覆性变化核心仍然是枚举、模拟、排序、二分、贪心、搜索、简单动态规划和最基础的图论。所以只要你在策略上不跑偏CSP-J的算法真没你想的那么吓人。1. 先别急着刷题搞清楚CSP-J到底考什么算法很多同学上手就是打开OJ在线评测系统开始疯狂刷题刷了200道还在原地踏步。问题出在你不知道CSP-J的算法边界在哪里。我见过太多人花两周去啃KMP和线段树结果初赛数据结构的题照样错一半复赛该拿的分也没拿到。方向错了努力就是负分。1.1 从官方大纲反推算法范围CSP-J的官方大纲每年都会给出知识点列表但那个列表写得比较“官方”很多家长和同学看完更懵了。我帮你翻译成人话CSP-J涉及的算法和数据结构大体就这几类基础算法枚举、模拟、排序冒泡、选择、插入、归并、快排、桶排、二分、贪心、分治搜索深度优先搜索DFS、广度优先搜索BFS、回溯、简单剪枝动态规划线性DP、背包问题01背包、完全背包、最长上升子序列、最长公共子序列图论入门图的存储邻接矩阵、邻接表、最短路Dijkstra、Floyd、最小生成树Kruskal、Prim常以Kruskal为主、拓扑排序数学基础质数判断、最大公约数欧几里得算法、快速幂、简单组合数字符串基础字符串匹配朴素匹配为主KMP在初赛中会以阅读代码的形式出现复赛很少要求手写看到这个清单心态是不是稳了一点但注意清单“少”不等于“容易”。CSP-J的难不在于算法本身的新颖程度而在于你怎么从一道看似乱七八糟的题目里识别出“哦这是排序”“哦这是二分答案”“哦这是个背包”。1.2 初赛和复赛对算法的要求是两套标准这个是我反复跟学生强调的初赛考的是“认不认识”和“能不能看懂”复赛考的是“能不能写对”和“能不能调出来”。初赛的算法题主要集中在单选题的“阅读程序”和“完善程序”部分。它会给你一段代码里面可能用了递归、二分、排序等算法让你去推导输出的结果或者在空缺处填代码。这时候你对算法的理解停留在“能手动模拟执行”的层面就够了。很多同学代码能力很强但手动模拟能力差初赛就吃亏。复赛则是四道程序设计题每道题背后隐藏的算法往往是“模拟枚举”或者“二分贪心”这种组合。这里的要求是高得多你不仅要认出算法还要能准确无误地实现它并且处理好边界条件。我见过太多学生算法讲得头头是道一写代码就各种数组越界、死循环、没开long long这些都是复赛丢分的大头。2. 排序算法CSP-J的“地基”但别一上来就啃快排排序在CSP-J里的地位很特殊。它单独出题的频率不高但它几乎是无处不在的。每当你需要对数据进行预处理排序就是你第一个应该想到的操作。而且在初赛的阅读程序题里排序算法是出现频率最高的代码素材。2.1 六种排序的优先级排序CSP-J阶段你至少需要掌握以下几种排序但优先级是完全不同的排序算法平均时间复杂度是否常考主要应用场景冒泡排序O(n²)初赛常考理解排序原理手动模拟选择排序O(n²)初赛常考理解“选择最值交换”思想插入排序O(n²)初赛偶考理解“逐步构建有序序列”归并排序O(n log n)重点掌握求逆序对分治思想入门快速排序O(n log n)重点掌握最常用的排序但注意退化风险桶排序/计数排序O(n)重点掌握值域有限的场景效率极高这里我想多说一句C的STL里已经提供了sort()函数竞赛中你直接用它就完了没人会要求你手写快排。但为什么还要学排序算法本身两个原因。第一初赛的阅读程序会考2025年初赛真题里仍然有冒泡排序的代码阅读题第二排序算法背后的分治思想、指针移动技巧是后面学归并排序求逆序对、学二分查找、学树状数组的基础。所以排序算法的代码你可以只记得sort()的用法但排序算法的思想你必须烂熟于心。2.2 冒泡排序为什么是初赛的“常青树”我翻了一下近五年的初赛真题冒泡排序的出现频率高得惊人。原因很现实它代码短逻辑直观适合用来考察学生对循环嵌套和数组下标变换的敏感度。// 经典冒泡排序 void bubbleSort(int a[], int n) { for (int i 0; i n - 1; i) { bool swapped false; for (int j 0; j n - 1 - i; j) { if (a[j] a[j 1]) { swap(a[j], a[j 1]); swapped true; } } if (!swapped) break; // 优化没有交换说明已经有序 } }初赛很喜欢在这个代码的基础上做文章比如问你“假如序列本身已经有序这个函数会执行多少次比较”答案是n-1次因为第一轮发现没有交换就break了。如果你只是死记硬背“冒泡排序要跑n-1轮”这道题就做错了。注意冒泡排序在CSP-J复赛中直接考察的概率极低因为O(n²)的复杂度在很多数据范围下过不去。但它作为“入门排序算法”的教学价值极高还是要认真学。2.3 归并排序的隐藏考法逆序对归并排序在CSP-J里最经典的考法不是排序本身而是“求逆序对”。这道题可以说是每年复赛模拟题和校内训练题的常客。long long mergeCount(int a[], int tmp[], int l, int r) { if (l r) return 0; int mid (l r) / 2; long long ans mergeCount(a, tmp, l, mid) mergeCount(a, tmp, mid 1, r); int i l, j mid 1, k l; while (i mid j r) { if (a[i] a[j]) { tmp[k] a[i]; } else { ans mid - i 1; // 左侧剩余元素都大于a[j] tmp[k] a[j]; } } while (i mid) tmp[k] a[i]; while (j r) tmp[k] a[j]; for (int p l; p r; p) a[p] tmp[p]; return ans; }这道代码的精华在那一句ans mid - i 1。第一次接触的同学往往很难理解为什么只是把右侧元素放前面就能直接算出逆序对数量因为归并的左右两个子数组各自已经有序了当右侧的a[j]小于左侧的a[i]时左侧从i到mid的所有元素都比a[j]大这些元素和a[j]就构成了mid - i 1个逆序对。这个思想属于“分治”的核心应用学懂了它你的算法理解会上一个台阶。3. 二分算法CSP-J区分度的分水岭我一直跟学生说二分算法是CSP-J里性价比最高的算法没有之一。它代码量极小思考量却极大。更重要的是它是“二分答案”这个高级思想的基础而后者在近年来的CSP-J复赛中频繁出现。LUOGUP7909 [CSP-J 2021] 分糖果这道题表面看是数学题背后的本质思维就和二分边界有关。3.1 你真的理解二分查找吗很多同学觉得二分查找简单到了极点不就是在有序数组里不断折半嘛。int binarySearch(int a[], int n, int x) { int l 0, r n - 1; while (l r) { int mid (l r) / 2; if (a[mid] x) return mid; else if (a[mid] x) l mid 1; else r mid - 1; } return -1; }但CSP-J怎么考你它不会给你一个排好序的数组让你找一个数它会把二分的“判断条件”包装得很隐蔽。最常见的一种变式是给你一个数组它先降序再升序或者说是一个“V”形序列让你找到最小值的位置。这时候传统的a[mid] x比较就不存在了你需要比较的是a[mid]和a[mid1]的大小关系。再比如给你一个单调函数f(x)题目要你求满足f(x) target的最小x这就是二分的“下界”问题。很多人在这里就直接懵了因为他脑子里只有“找等于某个值的下标”这一个模板没有真正理解二分的本质是“通过不断缩小答案可能存在的区间最终把答案锁定”。3.2 二分答案把最优化问题变成判定问题CSP-J复赛从2020年开始明显加大了“二分答案”的考察力度。什么叫二分答案就是当题目要求“求最大值的最小值”或者“最小值的最大值”时我们不对数组下标进行二分而是对“解”的取值范围进行二分然后写一个check(x)函数判断这个解x是否可行。举个最典型的例子题目把n个数分成m段使每段和的最大值最小。这个问题如果直接想很难设计出高效的算法。但如果我们换一个角度假设答案是x也就是“每段和的最大值不超过x”那我们只需要贪心地从左到右扫描一旦当前段的和超过x就另起一段最后统计段数是否不超过m即可。这个check(x)的复杂度是O(n)的。然后我们对x的取值范围[max(a[i]), sum(a[i])]进行二分查找总复杂度O(n log sum)完美解决问题。二分答案的难点在于第一你能不能看出来这道题能用二分答案做第二你的check(x)函数能不能写对第三边界条件l和r怎么初始化、循环条件用l r还是l r。这些问题没有统一答案只能通过大量练习来形成肌肉记忆。3.3 和二分搭配的STL技巧在C中STL提供了lower_bound()和upper_bound()两个函数它们在有序数组上的查找效率是O(log n)而且在很多题目里可以替代手写二分。我建议要熟练使用它们但同时也必须能手写二分——因为初赛阅读程序题考的是手写版本而且很多场景下你需要对二分进行魔改STL的固定功能不够用。#include algorithm #include vector using namespace std; vectorint v {1, 3, 5, 5, 7, 9}; // lower_bound 返回第一个 5 的迭代器 auto it1 lower_bound(v.begin(), v.end(), 5); // it1指向第一个5 // upper_bound 返回第一个 5 的迭代器 auto it2 upper_bound(v.begin(), v.end(), 5); // it2指向7注意lower_bound和upper_bound要求数组必须先排序。如果你用完之后修改了数组元素的顺序这两个函数的行为就是未定义的程序可能直接WA答案错误。4. 搜索算法DFS和BFS是通向动态规划的必经之路搜索算法在CSP-J复赛中的角色比较特殊。它很少作为正解出现因为复杂度通常偏高但它在三方面价值巨大第一暴力枚举的做法可以帮你拿部分分第二DFS是理解递归和回溯的关键工具第三很多动态规划问题可以看作是对搜索的“剪枝优化”理解了搜索才可能理解DP。4.1 搜索迷宫DFS/BFS遍历顺序辨析CSP-J初赛特别喜欢考DFS和BFS的遍历顺序。给你一张图或者一个迷宫问你按照DFS顺序访问节点的序列是什么或者BFS的队列变化过程是什么。DFS本质上是“一条道走到黑撞了南墙才回头”它借助的是系统栈或者自己手写栈。BFS本质上是“一圈一圈向外扩散”它借助的是队列。初赛题目往往会给一个四连通或八连通的迷宫让你标出访问顺序。这种题没有技巧就是手动模拟。但手模拟的时候有个易错点多重方向顺序的约定。题目通常会说明“按上下左右顺序”或者“按左、上、右、下顺序”你必须严格按照这个顺序去搜索否则结果和标准答案不一致。我见过太多平时代码能力很强的同学初赛就栽在这类题上。原因就是他写代码的时候习惯了某种方向顺序但题目换了方向顺序他没有仔细审题导致模拟结果错误。4.2 回溯 剪枝搜索的灵魂CSP-J的复赛不会让你直接写一个裸的DFS然后就拿满分因为数据范围会让裸搜索超时。所以 DFS必须搭配剪枝策略。常见的剪枝有最优性剪枝当前方案的代价已经超过已知最优解直接return、可行性剪枝按照当前状态继续搜索下去也不可能到达目标直接return、重复性剪枝用一个vis数组记录访问过的状态。以LUOGUP5663 [CSP-J 2019] 加工零件这道题为例题目乍一看是个图论问题但有的人会想用BFS专门去处理每个查询这就太慢了。正确解法是先做一次最短路预处理然后用奇偶性判断答案。这道题给我们的启示是搜索不能只会朴素地搜还要学会用“预处理结论”来替代重复搜索。还有一类经典题是“八皇后”的变种。裸的DFS是枚举每一行的放置位置复杂度O(n²)但当n达到十几的时候就扛不住了。此时你需要加剪枝检查对角线、检查列是否冲突。这些检查操作通过预先开好布尔数组可以做到O(1)判断。这就是典型的“空间换时间”。4.3 搜索在竞赛实战中的策略价值我给学生的建议是如果你在复赛考场上面对一道题20分钟都想不到正解别死磕。立刻写一个DFS或者BFS的暴力版本先把30%50%的部分分拿到手然后再去优化。信奥赛的评分规则是按测试点给分的你只要过了前几个数据点就有分。很多省一的选手其实第二题、第三题就是用暴力拿了一半以上的分数最后总分够了。为什么强调这一点因为我见过太多学生平时练习时非正解不写觉得暴力丢人。到了考场上又因为紧张想不出正解最后交白卷。这不是能力问题是策略问题。5. 贪心、模拟、数学CSP-J最容易“看起来不难”的三座山很多人冲着“算法”去学觉得排序、二分、搜索才是重点结果忽略了另外三类更阴险的题目贪心、模拟和数学思维题。这三类题在CSP-J里占的分值比重非常高而且往往是压轴题的首选。5.1 贪心算法证明比代码更难贪心算法的代码通常很短短到你怀疑自己是不是看错了题。正确的贪心策略加上正确的排序规则往往十几行就AC了。但问题在于你怎么知道这个贪心策略是对的CSP-J常见的贪心模型有活动安排问题按结束时间排序、区间覆盖问题按左端点排序、哈夫曼编码思想用小顶堆合并、部分背包问题按单位价值排序。以活动安排为例要求选择尽可能多的互不重叠的活动。正确的贪心策略是“按结束时间从早到晚排序”然后依次选择。很多同学容易搞错成“按开始时间从早到晚”这样得出来的不是最优解。为什么按结束时间对因为结束时间越早就可以把剩余时间留出来给后面的活动这是人类做时间管理的直觉但要用严格的数学证明并不容易。在竞赛中你没有时间做严格证明你需要做的是“直觉验证 举反例”。如果举不出反例就大胆写。这个“大胆”很关键但也很危险。我见过太多学生在贪心题上翻车原因就是直觉错了。5.2 模拟题CSP-J真正的“沉默杀手”在讲算法之前我必须提醒你CSP-J复赛四道题里通常有一道是纯粹的模拟题它不涉及任何高级算法就是把题目要求的流程一步一步用代码实现出来。但这类题目的失分率却高得惊人。为什么三个字不耐烦。题目描述往往又长又绕比如“给出一个字符串按照规则进行多轮替换”或者“模拟一个游戏的胜负判定流程”。很多学生看到长题干就烦只看了两遍就开始写写着写着发现漏了一个条件再回头重读时间就浪费了。我的建议是面对模拟题在第一遍读题时就顺手把“关键变量”“状态变化图”“终止条件”写在草稿纸上。尤其是状态变化图它能帮你理清嵌套关系。用纸笔把流程走通再动手写代码。磨刀不误砍柴工这一步至少能帮你减少一半的WA。5.3 用LUOGUP7909分糖果体察“数学思维题”再回头说LUOGUP7909 [CSP-J 2021] 分糖果这道题。题干大概是说有若干个小朋友和若干颗糖果每个小朋友分到的糖果数量要满足在[L, R]区间内问某个人最多能分多少颗。很多同学第一个想法是枚举[L, R]的每一个值这样复杂度可能很高。正确做法是利用模运算的性质分类讨论L / n和R / n的关系直接算出最优解。这道题的本质不是算法是数学观察。CSP-J近年来越来越喜欢出这类“披着算法外衣的数学题”。所以除了刷算法题你还需要有意识地训练“把题目语言转化成数学表达式”的能力。看到“分糖果”“分苹果”“分组”这类词条件反射去想模运算和整除看到“最大最小”条件反射去想二分答案或贪心。6. 最后聊聊数据结构基础与考前冲刺策略数据结构在CSP-J中扮演的角色是“算法的载体”。没有数组排序无从谈起没有栈和队列DFS和BFS就失去了依凭没有树和图的相关概念图论算法就更别提了。6.1 栈、队列和优先队列的竞赛用法CSP-J初赛对栈和队列的考察非常基础通常会结合递归来考察栈的特性结合BFS来考察队列的特性。比如它会给你一个递归函数让你求递归调用的深度这就是在考察“系统栈”的概念。又比如它可以给你一段用栈把中缀表达式转后缀表达式的代码让你模拟运行。这时候你要清楚栈是先进后出队列是先进先出优先队列是按优先级出队。特别提醒C的STL中栈是std::stack队列是std::queue优先队列是std::priority_queue。优先队列默认是大顶堆如果你需要小顶堆要写成priority_queueint, vectorint, greaterint。这是一个高频的易错点。#include queue #include vector using namespace std; // 小顶堆 priority_queueint, vectorint, greaterint pq; pq.push(5); pq.push(1); pq.push(3); // 依次弹出1, 3, 56.2 KMP等在CSP-J中的真实地位热搜词里出现了KMP、粒子群算法、深度学习算法这些“高级货”。这里我要泼一盆冷静水KMP在CSP-J初赛确实出现过但只出现在“阅读程序”里作为代码素材99%的情况下不会让你在复赛手写KMP。至于粒子群、深度学习、混音算法、磁盘寻道算法这些和CSP-J完全无关纯属家长搜索时被算法目录晃花了眼。为什么初赛会出KMP的阅读题因为它代码短逻辑精巧适合考察“你能否看懂常见的字符串匹配优化思想”。但你不需要能默写它你只需要理解它为什么比朴素匹配快利用部分匹配表跳过已匹配的位置。这个理解程度就够了。类似的还有“卡特兰数”“错排公式”这类数学知识初赛可能出现复赛几乎不会让你单独去推一个递推式。备考时不要过深不要本末倒置。6.3 三个月拿奖的刷题规划如果看到这篇文章的时候你距离9月的CSP-J初赛还有3个月左右我的建议是这样的第一个月主攻枚举、模拟、排序、二分、贪心。每天2-3道题不求难求全。这一个月是打地基地基不稳后面全垮。推荐在洛谷上按照“入门”“普及-”的难度梯度刷题每天至少1道“普及-”难度的题。第二个月主攻DFS、BFS、背包DP和简单图论。每天2道题其中1道是搜索或DP另外1道复习前一个月的排序或二分。这个阶段要开始学习“读题-建模-写码-调试”的完整流程并且开始限时训练一道题控制在40分钟内不论做没做出来都要看题解复盘。第三个月进入冲刺阶段。每周至少进行两场完整的模拟考试就用历年的CSP-J复赛真题。模拟考试最关键的一点是完全按照真实考试的时间和环境来不能中途翻书、不能延长时间。考完之后的复盘比考试更重要每一道错题都要搞清楚是哪个环节出了问题——是读题读偏了还是算法选择错了还是代码写挂了。6.4 考场上最容易犯的低级错误我最后再念叨一遍考场上的低级错误这些每年都有一大批人中招而且全是平时训练中明明没问题的好学生忘了开long long。CSP-J的数据范围经常超过int的2^31-1尤其是求和的题一旦超过就WA。我的习惯是见到“求和”“乘积”“方案数”的字样二话不说开long long。数组开小了。图论题开邻接表时边的数量要记得是双向边数组大小要开2 * MAXN。开小了会RE运行时错误而且报错还看不出来。文件操作。CSP-J复赛要求从文件读入、向文件输出很多人平时用标准输入输出习惯了考试忘了写freopen直接爆零。这真的是最冤的丢分方式。调试代码忘了删。平时写代码喜欢加cout或者cerr输出调试信息交卷前一定要检查一遍把调试输出全部删掉。不检查边界条件。比如循环里用到i1就要检查i是否越界用到n-1就要考虑n为0或1的情况。根据我个人的经验这五条里面中两条以上的人复赛成绩基本就会比平时水平低一个档次。所以做题时多花五分钟检查这几个点远比多做一道新题更有价值。最后再分享一个我自己的教学习惯每次复赛模拟考结束我都会让每个学生写一份“错因登记表”把每道错题的原因分成“读题错误”“建模错误”“算法错误”“代码错误”四类。坚持三轮模拟之后他们大多数人错误率会明显下降。这个方法你也可以试试把手上的真题都利用起来把CSP-J的算法从“我会写”变成“我条件反射能写”分数自然就上去了。 
长河君 · 2026/9/13 21:28:20 · 阅读 1.2k CSP-J算法清单与优先级：排序、二分、搜索、贪心备考全攻略
老看到家长和学生在问“CSP-J需要掌握的算法到底有哪些”搜一圈发现要么是太泛的目录要么就是直接甩题号根本不知道从哪儿下手。我自己带过几年信奥集训队也带自己家娃完整走完一轮CSP-J从入门到拿奖的过程这篇文章就把我实际教学和陪跑中反复用到的算法清单、优先级排序、以及最容易踩的坑一次性说清楚。它不是那种“考纲复制粘贴”而是告诉你哪些算法是必须滚瓜烂熟的哪些是学了纯属浪费时间的以及每个算法到底在CSP-J里是怎么被出题人拿来“变着花样考”的。先说一个很多人没意识到的事实CSP-J的算法部分真正需要你“掌握得很深”的其实不超过10个。剩下的大量内容要么是数据结构的底层知识要么是会被包装成“算法题”的数学思维题。2025年的初赛大纲和往年相比并没有发生颠覆性变化核心仍然是枚举、模拟、排序、二分、贪心、搜索、简单动态规划和最基础的图论。所以只要你在策略上不跑偏CSP-J的算法真没你想的那么吓人。1. 先别急着刷题搞清楚CSP-J到底考什么算法很多同学上手就是打开OJ在线评测系统开始疯狂刷题刷了200道还在原地踏步。问题出在你不知道CSP-J的算法边界在哪里。我见过太多人花两周去啃KMP和线段树结果初赛数据结构的题照样错一半复赛该拿的分也没拿到。方向错了努力就是负分。1.1 从官方大纲反推算法范围CSP-J的官方大纲每年都会给出知识点列表但那个列表写得比较“官方”很多家长和同学看完更懵了。我帮你翻译成人话CSP-J涉及的算法和数据结构大体就这几类基础算法枚举、模拟、排序冒泡、选择、插入、归并、快排、桶排、二分、贪心、分治搜索深度优先搜索DFS、广度优先搜索BFS、回溯、简单剪枝动态规划线性DP、背包问题01背包、完全背包、最长上升子序列、最长公共子序列图论入门图的存储邻接矩阵、邻接表、最短路Dijkstra、Floyd、最小生成树Kruskal、Prim常以Kruskal为主、拓扑排序数学基础质数判断、最大公约数欧几里得算法、快速幂、简单组合数字符串基础字符串匹配朴素匹配为主KMP在初赛中会以阅读代码的形式出现复赛很少要求手写看到这个清单心态是不是稳了一点但注意清单“少”不等于“容易”。CSP-J的难不在于算法本身的新颖程度而在于你怎么从一道看似乱七八糟的题目里识别出“哦这是排序”“哦这是二分答案”“哦这是个背包”。1.2 初赛和复赛对算法的要求是两套标准这个是我反复跟学生强调的初赛考的是“认不认识”和“能不能看懂”复赛考的是“能不能写对”和“能不能调出来”。初赛的算法题主要集中在单选题的“阅读程序”和“完善程序”部分。它会给你一段代码里面可能用了递归、二分、排序等算法让你去推导输出的结果或者在空缺处填代码。这时候你对算法的理解停留在“能手动模拟执行”的层面就够了。很多同学代码能力很强但手动模拟能力差初赛就吃亏。复赛则是四道程序设计题每道题背后隐藏的算法往往是“模拟枚举”或者“二分贪心”这种组合。这里的要求是高得多你不仅要认出算法还要能准确无误地实现它并且处理好边界条件。我见过太多学生算法讲得头头是道一写代码就各种数组越界、死循环、没开long long这些都是复赛丢分的大头。2. 排序算法CSP-J的“地基”但别一上来就啃快排排序在CSP-J里的地位很特殊。它单独出题的频率不高但它几乎是无处不在的。每当你需要对数据进行预处理排序就是你第一个应该想到的操作。而且在初赛的阅读程序题里排序算法是出现频率最高的代码素材。2.1 六种排序的优先级排序CSP-J阶段你至少需要掌握以下几种排序但优先级是完全不同的排序算法平均时间复杂度是否常考主要应用场景冒泡排序O(n²)初赛常考理解排序原理手动模拟选择排序O(n²)初赛常考理解“选择最值交换”思想插入排序O(n²)初赛偶考理解“逐步构建有序序列”归并排序O(n log n)重点掌握求逆序对分治思想入门快速排序O(n log n)重点掌握最常用的排序但注意退化风险桶排序/计数排序O(n)重点掌握值域有限的场景效率极高这里我想多说一句C的STL里已经提供了sort()函数竞赛中你直接用它就完了没人会要求你手写快排。但为什么还要学排序算法本身两个原因。第一初赛的阅读程序会考2025年初赛真题里仍然有冒泡排序的代码阅读题第二排序算法背后的分治思想、指针移动技巧是后面学归并排序求逆序对、学二分查找、学树状数组的基础。所以排序算法的代码你可以只记得sort()的用法但排序算法的思想你必须烂熟于心。2.2 冒泡排序为什么是初赛的“常青树”我翻了一下近五年的初赛真题冒泡排序的出现频率高得惊人。原因很现实它代码短逻辑直观适合用来考察学生对循环嵌套和数组下标变换的敏感度。// 经典冒泡排序 void bubbleSort(int a[], int n) { for (int i 0; i n - 1; i) { bool swapped false; for (int j 0; j n - 1 - i; j) { if (a[j] a[j 1]) { swap(a[j], a[j 1]); swapped true; } } if (!swapped) break; // 优化没有交换说明已经有序 } }初赛很喜欢在这个代码的基础上做文章比如问你“假如序列本身已经有序这个函数会执行多少次比较”答案是n-1次因为第一轮发现没有交换就break了。如果你只是死记硬背“冒泡排序要跑n-1轮”这道题就做错了。注意冒泡排序在CSP-J复赛中直接考察的概率极低因为O(n²)的复杂度在很多数据范围下过不去。但它作为“入门排序算法”的教学价值极高还是要认真学。2.3 归并排序的隐藏考法逆序对归并排序在CSP-J里最经典的考法不是排序本身而是“求逆序对”。这道题可以说是每年复赛模拟题和校内训练题的常客。long long mergeCount(int a[], int tmp[], int l, int r) { if (l r) return 0; int mid (l r) / 2; long long ans mergeCount(a, tmp, l, mid) mergeCount(a, tmp, mid 1, r); int i l, j mid 1, k l; while (i mid j r) { if (a[i] a[j]) { tmp[k] a[i]; } else { ans mid - i 1; // 左侧剩余元素都大于a[j] tmp[k] a[j]; } } while (i mid) tmp[k] a[i]; while (j r) tmp[k] a[j]; for (int p l; p r; p) a[p] tmp[p]; return ans; }这道代码的精华在那一句ans mid - i 1。第一次接触的同学往往很难理解为什么只是把右侧元素放前面就能直接算出逆序对数量因为归并的左右两个子数组各自已经有序了当右侧的a[j]小于左侧的a[i]时左侧从i到mid的所有元素都比a[j]大这些元素和a[j]就构成了mid - i 1个逆序对。这个思想属于“分治”的核心应用学懂了它你的算法理解会上一个台阶。3. 二分算法CSP-J区分度的分水岭我一直跟学生说二分算法是CSP-J里性价比最高的算法没有之一。它代码量极小思考量却极大。更重要的是它是“二分答案”这个高级思想的基础而后者在近年来的CSP-J复赛中频繁出现。LUOGUP7909 [CSP-J 2021] 分糖果这道题表面看是数学题背后的本质思维就和二分边界有关。3.1 你真的理解二分查找吗很多同学觉得二分查找简单到了极点不就是在有序数组里不断折半嘛。int binarySearch(int a[], int n, int x) { int l 0, r n - 1; while (l r) { int mid (l r) / 2; if (a[mid] x) return mid; else if (a[mid] x) l mid 1; else r mid - 1; } return -1; }但CSP-J怎么考你它不会给你一个排好序的数组让你找一个数它会把二分的“判断条件”包装得很隐蔽。最常见的一种变式是给你一个数组它先降序再升序或者说是一个“V”形序列让你找到最小值的位置。这时候传统的a[mid] x比较就不存在了你需要比较的是a[mid]和a[mid1]的大小关系。再比如给你一个单调函数f(x)题目要你求满足f(x) target的最小x这就是二分的“下界”问题。很多人在这里就直接懵了因为他脑子里只有“找等于某个值的下标”这一个模板没有真正理解二分的本质是“通过不断缩小答案可能存在的区间最终把答案锁定”。3.2 二分答案把最优化问题变成判定问题CSP-J复赛从2020年开始明显加大了“二分答案”的考察力度。什么叫二分答案就是当题目要求“求最大值的最小值”或者“最小值的最大值”时我们不对数组下标进行二分而是对“解”的取值范围进行二分然后写一个check(x)函数判断这个解x是否可行。举个最典型的例子题目把n个数分成m段使每段和的最大值最小。这个问题如果直接想很难设计出高效的算法。但如果我们换一个角度假设答案是x也就是“每段和的最大值不超过x”那我们只需要贪心地从左到右扫描一旦当前段的和超过x就另起一段最后统计段数是否不超过m即可。这个check(x)的复杂度是O(n)的。然后我们对x的取值范围[max(a[i]), sum(a[i])]进行二分查找总复杂度O(n log sum)完美解决问题。二分答案的难点在于第一你能不能看出来这道题能用二分答案做第二你的check(x)函数能不能写对第三边界条件l和r怎么初始化、循环条件用l r还是l r。这些问题没有统一答案只能通过大量练习来形成肌肉记忆。3.3 和二分搭配的STL技巧在C中STL提供了lower_bound()和upper_bound()两个函数它们在有序数组上的查找效率是O(log n)而且在很多题目里可以替代手写二分。我建议要熟练使用它们但同时也必须能手写二分——因为初赛阅读程序题考的是手写版本而且很多场景下你需要对二分进行魔改STL的固定功能不够用。#include algorithm #include vector using namespace std; vectorint v {1, 3, 5, 5, 7, 9}; // lower_bound 返回第一个 5 的迭代器 auto it1 lower_bound(v.begin(), v.end(), 5); // it1指向第一个5 // upper_bound 返回第一个 5 的迭代器 auto it2 upper_bound(v.begin(), v.end(), 5); // it2指向7注意lower_bound和upper_bound要求数组必须先排序。如果你用完之后修改了数组元素的顺序这两个函数的行为就是未定义的程序可能直接WA答案错误。4. 搜索算法DFS和BFS是通向动态规划的必经之路搜索算法在CSP-J复赛中的角色比较特殊。它很少作为正解出现因为复杂度通常偏高但它在三方面价值巨大第一暴力枚举的做法可以帮你拿部分分第二DFS是理解递归和回溯的关键工具第三很多动态规划问题可以看作是对搜索的“剪枝优化”理解了搜索才可能理解DP。4.1 搜索迷宫DFS/BFS遍历顺序辨析CSP-J初赛特别喜欢考DFS和BFS的遍历顺序。给你一张图或者一个迷宫问你按照DFS顺序访问节点的序列是什么或者BFS的队列变化过程是什么。DFS本质上是“一条道走到黑撞了南墙才回头”它借助的是系统栈或者自己手写栈。BFS本质上是“一圈一圈向外扩散”它借助的是队列。初赛题目往往会给一个四连通或八连通的迷宫让你标出访问顺序。这种题没有技巧就是手动模拟。但手模拟的时候有个易错点多重方向顺序的约定。题目通常会说明“按上下左右顺序”或者“按左、上、右、下顺序”你必须严格按照这个顺序去搜索否则结果和标准答案不一致。我见过太多平时代码能力很强的同学初赛就栽在这类题上。原因就是他写代码的时候习惯了某种方向顺序但题目换了方向顺序他没有仔细审题导致模拟结果错误。4.2 回溯 剪枝搜索的灵魂CSP-J的复赛不会让你直接写一个裸的DFS然后就拿满分因为数据范围会让裸搜索超时。所以 DFS必须搭配剪枝策略。常见的剪枝有最优性剪枝当前方案的代价已经超过已知最优解直接return、可行性剪枝按照当前状态继续搜索下去也不可能到达目标直接return、重复性剪枝用一个vis数组记录访问过的状态。以LUOGUP5663 [CSP-J 2019] 加工零件这道题为例题目乍一看是个图论问题但有的人会想用BFS专门去处理每个查询这就太慢了。正确解法是先做一次最短路预处理然后用奇偶性判断答案。这道题给我们的启示是搜索不能只会朴素地搜还要学会用“预处理结论”来替代重复搜索。还有一类经典题是“八皇后”的变种。裸的DFS是枚举每一行的放置位置复杂度O(n²)但当n达到十几的时候就扛不住了。此时你需要加剪枝检查对角线、检查列是否冲突。这些检查操作通过预先开好布尔数组可以做到O(1)判断。这就是典型的“空间换时间”。4.3 搜索在竞赛实战中的策略价值我给学生的建议是如果你在复赛考场上面对一道题20分钟都想不到正解别死磕。立刻写一个DFS或者BFS的暴力版本先把30%50%的部分分拿到手然后再去优化。信奥赛的评分规则是按测试点给分的你只要过了前几个数据点就有分。很多省一的选手其实第二题、第三题就是用暴力拿了一半以上的分数最后总分够了。为什么强调这一点因为我见过太多学生平时练习时非正解不写觉得暴力丢人。到了考场上又因为紧张想不出正解最后交白卷。这不是能力问题是策略问题。5. 贪心、模拟、数学CSP-J最容易“看起来不难”的三座山很多人冲着“算法”去学觉得排序、二分、搜索才是重点结果忽略了另外三类更阴险的题目贪心、模拟和数学思维题。这三类题在CSP-J里占的分值比重非常高而且往往是压轴题的首选。5.1 贪心算法证明比代码更难贪心算法的代码通常很短短到你怀疑自己是不是看错了题。正确的贪心策略加上正确的排序规则往往十几行就AC了。但问题在于你怎么知道这个贪心策略是对的CSP-J常见的贪心模型有活动安排问题按结束时间排序、区间覆盖问题按左端点排序、哈夫曼编码思想用小顶堆合并、部分背包问题按单位价值排序。以活动安排为例要求选择尽可能多的互不重叠的活动。正确的贪心策略是“按结束时间从早到晚排序”然后依次选择。很多同学容易搞错成“按开始时间从早到晚”这样得出来的不是最优解。为什么按结束时间对因为结束时间越早就可以把剩余时间留出来给后面的活动这是人类做时间管理的直觉但要用严格的数学证明并不容易。在竞赛中你没有时间做严格证明你需要做的是“直觉验证 举反例”。如果举不出反例就大胆写。这个“大胆”很关键但也很危险。我见过太多学生在贪心题上翻车原因就是直觉错了。5.2 模拟题CSP-J真正的“沉默杀手”在讲算法之前我必须提醒你CSP-J复赛四道题里通常有一道是纯粹的模拟题它不涉及任何高级算法就是把题目要求的流程一步一步用代码实现出来。但这类题目的失分率却高得惊人。为什么三个字不耐烦。题目描述往往又长又绕比如“给出一个字符串按照规则进行多轮替换”或者“模拟一个游戏的胜负判定流程”。很多学生看到长题干就烦只看了两遍就开始写写着写着发现漏了一个条件再回头重读时间就浪费了。我的建议是面对模拟题在第一遍读题时就顺手把“关键变量”“状态变化图”“终止条件”写在草稿纸上。尤其是状态变化图它能帮你理清嵌套关系。用纸笔把流程走通再动手写代码。磨刀不误砍柴工这一步至少能帮你减少一半的WA。5.3 用LUOGUP7909分糖果体察“数学思维题”再回头说LUOGUP7909 [CSP-J 2021] 分糖果这道题。题干大概是说有若干个小朋友和若干颗糖果每个小朋友分到的糖果数量要满足在[L, R]区间内问某个人最多能分多少颗。很多同学第一个想法是枚举[L, R]的每一个值这样复杂度可能很高。正确做法是利用模运算的性质分类讨论L / n和R / n的关系直接算出最优解。这道题的本质不是算法是数学观察。CSP-J近年来越来越喜欢出这类“披着算法外衣的数学题”。所以除了刷算法题你还需要有意识地训练“把题目语言转化成数学表达式”的能力。看到“分糖果”“分苹果”“分组”这类词条件反射去想模运算和整除看到“最大最小”条件反射去想二分答案或贪心。6. 最后聊聊数据结构基础与考前冲刺策略数据结构在CSP-J中扮演的角色是“算法的载体”。没有数组排序无从谈起没有栈和队列DFS和BFS就失去了依凭没有树和图的相关概念图论算法就更别提了。6.1 栈、队列和优先队列的竞赛用法CSP-J初赛对栈和队列的考察非常基础通常会结合递归来考察栈的特性结合BFS来考察队列的特性。比如它会给你一个递归函数让你求递归调用的深度这就是在考察“系统栈”的概念。又比如它可以给你一段用栈把中缀表达式转后缀表达式的代码让你模拟运行。这时候你要清楚栈是先进后出队列是先进先出优先队列是按优先级出队。特别提醒C的STL中栈是std::stack队列是std::queue优先队列是std::priority_queue。优先队列默认是大顶堆如果你需要小顶堆要写成priority_queueint, vectorint, greaterint。这是一个高频的易错点。#include queue #include vector using namespace std; // 小顶堆 priority_queueint, vectorint, greaterint pq; pq.push(5); pq.push(1); pq.push(3); // 依次弹出1, 3, 56.2 KMP等在CSP-J中的真实地位热搜词里出现了KMP、粒子群算法、深度学习算法这些“高级货”。这里我要泼一盆冷静水KMP在CSP-J初赛确实出现过但只出现在“阅读程序”里作为代码素材99%的情况下不会让你在复赛手写KMP。至于粒子群、深度学习、混音算法、磁盘寻道算法这些和CSP-J完全无关纯属家长搜索时被算法目录晃花了眼。为什么初赛会出KMP的阅读题因为它代码短逻辑精巧适合考察“你能否看懂常见的字符串匹配优化思想”。但你不需要能默写它你只需要理解它为什么比朴素匹配快利用部分匹配表跳过已匹配的位置。这个理解程度就够了。类似的还有“卡特兰数”“错排公式”这类数学知识初赛可能出现复赛几乎不会让你单独去推一个递推式。备考时不要过深不要本末倒置。6.3 三个月拿奖的刷题规划如果看到这篇文章的时候你距离9月的CSP-J初赛还有3个月左右我的建议是这样的第一个月主攻枚举、模拟、排序、二分、贪心。每天2-3道题不求难求全。这一个月是打地基地基不稳后面全垮。推荐在洛谷上按照“入门”“普及-”的难度梯度刷题每天至少1道“普及-”难度的题。第二个月主攻DFS、BFS、背包DP和简单图论。每天2道题其中1道是搜索或DP另外1道复习前一个月的排序或二分。这个阶段要开始学习“读题-建模-写码-调试”的完整流程并且开始限时训练一道题控制在40分钟内不论做没做出来都要看题解复盘。第三个月进入冲刺阶段。每周至少进行两场完整的模拟考试就用历年的CSP-J复赛真题。模拟考试最关键的一点是完全按照真实考试的时间和环境来不能中途翻书、不能延长时间。考完之后的复盘比考试更重要每一道错题都要搞清楚是哪个环节出了问题——是读题读偏了还是算法选择错了还是代码写挂了。6.4 考场上最容易犯的低级错误我最后再念叨一遍考场上的低级错误这些每年都有一大批人中招而且全是平时训练中明明没问题的好学生忘了开long long。CSP-J的数据范围经常超过int的2^31-1尤其是求和的题一旦超过就WA。我的习惯是见到“求和”“乘积”“方案数”的字样二话不说开long long。数组开小了。图论题开邻接表时边的数量要记得是双向边数组大小要开2 * MAXN。开小了会RE运行时错误而且报错还看不出来。文件操作。CSP-J复赛要求从文件读入、向文件输出很多人平时用标准输入输出习惯了考试忘了写freopen直接爆零。这真的是最冤的丢分方式。调试代码忘了删。平时写代码喜欢加cout或者cerr输出调试信息交卷前一定要检查一遍把调试输出全部删掉。不检查边界条件。比如循环里用到i1就要检查i是否越界用到n-1就要考虑n为0或1的情况。根据我个人的经验这五条里面中两条以上的人复赛成绩基本就会比平时水平低一个档次。所以做题时多花五分钟检查这几个点远比多做一道新题更有价值。最后再分享一个我自己的教学习惯每次复赛模拟考结束我都会让每个学生写一份“错因登记表”把每道错题的原因分成“读题错误”“建模错误”“算法错误”“代码错误”四类。坚持三轮模拟之后他们大多数人错误率会明显下降。这个方法你也可以试试把手上的真题都利用起来把CSP-J的算法从“我会写”变成“我条件反射能写”分数自然就上去了。