写这篇C算法笔记是因为我自己也是从只会写顺序结构的菜鸟一点点啃到能稳定拿下中等难度题的。整个过程下来最大的感受是算法题的重点从来不是“背多少模板”而是你能不能把C这门语言用到顺手同时把边界情况、复杂度、调试手法这些细节融进每一次提交里。这篇笔记不会去讲那些大而全的语法教程而是聚焦在刷题和复盘时真正天天用得上的东西STL的正确打开方式、二分和DP这些高频模板的边界处理、不同数据范围下复杂度怎么估、以及本地能过一提交就WA的排查思路。适合刚学完C语法、正准备系统刷题的同学也适合已经刷了不少题但总觉得效率不高的人对照自查一遍。1. C算法笔记的前置准备编译选项与编码习惯很多新手拿到题目第一件事就是写代码忽略了对编译环境和基础编码习惯的检查结果往往是后面调试花费的时间比写代码还多。我这里先讲几个“隐藏的坑”提前排掉能省一大半时间。1.1 编译器与标准选择你现在打开任何一个OJ在线判题系统或者算法竞赛普遍用的都是GCC/Clang 这一套标准一般是C17。本地编辑器和OJ的编译器版本可能不一样但尽量统一到一个相对较新的标准上能少很多兼容性问题。我在本地习惯用这样的命令编译g -stdc17 -O2 -Wall -Wextra -g -o main main.cpp简单拆解一下这几个参数为什么是必需的-stdc17明确指定C17标准避免编译器默认标准过旧带来的差异比如某些泛型写法、结构化绑定在旧标准下不支持。-O2开启优化这个极其关键。很多算法题的时间瓶颈只有在开启O2之后才体现真实水平也能暴露出某些依赖未定义行为UB的代码问题。-Wall -Wextra打开警告。我见过太多人提交的代码里藏着“有符号/无符号比较”、“变量可能未初始化”这类地雷OJ很多时候不会提示等到Wrong Answer才追悔莫及。-g生成调试信息配合GDB或IDE断点使用。早期刷题阶段调试器比你的眼睛靠谱十倍。1.2 输入输出优化cin/cout还是scanf/printf这个争论老生常谈了直接给结论。在算法竞赛中数据量上百万甚至更大时cin/cout默认确实比scanf/printf慢因为iostream要和C标准IO保持同步导致频繁刷新缓冲区。解决办法很简单在main函数的第一行加上ios::sync_with_stdio(false); cin.tie(nullptr);这两句把C流和C标准IO的同步关系切断同时让cin不再和cout绑定、提前刷新。之后cin/cout的速度基本就能追上scanf/printf日常刷题完全够用。不过在极端大数据量下比如总共要读几百万个整数我依然会考虑自己写快读inline int read() { int x 0, f 1; char c getchar(); while (c 0 || c 9) { if (c -) f -1; c getchar(); } while (c 0 c 9) { x x * 10 (c - 0); c getchar(); } return x * f; }这段快读的原理是逐个字符读取并转换为整数。注意一定要处理负号如果题目里有负数而你漏了f的翻转轻则WAWrong Answer重则整个人debug到怀疑人生。1.3 调试三件套assert、cerr与sanitizer调试阶段我最常用的三样东西是assert、cerr和编译器的sanitizer。assert用来在关键逻辑处插入前置条件。比如你手写二分时可以先用assert(l r)确保区间合法。注意正式提交前要把所有assert注释掉因为它们在Release模式下依然会占用时间。cerr调试输出的“最佳配角”。千万不要在正式提交里用cerr打印东西它不像cout那样受sync_with_stdio(false)影响速度极慢而且会刷屏。但本地调试时cerr val endl能帮你确认每个循环变量在某个时刻的值。sanitizer现代编译器一大利器尤其针对数组越界、内存泄漏这类“幽灵问题”。在本地编译时加一把g -stdc17 -fsanitizeaddress,undefined -g -o main main.cppaddress是AddressSanitizer能检测越界访问、野指针、栈溢出等undefined是UndefinedBehaviorSanitizer能检测未定义行为。每次WA之前先跑一遍sanitizer十次有九次能直接定位原因。2. 数据结构的底层感觉从STL到手写模板的边界刷题到一定阶段你会发现数据结构选型直接决定了解法能否落地。C的STL不是银弹用对了是神兵用错了是累赘。这一节说说我对几个常用容器的个人体验。2.1 vector不只是“动态数组”vector是最常用的容器但很多人用起来还是太随意。我有三个习惯第一能用reserve就提前估长度。如果你提前知道最多会有多少个元素直接vectorint v; v.reserve(n);可以避免反复扩容、复制旧元素带来的性能损耗。特别是在循环里反复push_back的场景这个优化非常明显。第二访问元素时尽量用引用或const引用。for (auto x : vec)这种写法复杂结构体场景下能减少拷贝构造和析构的开销。for (auto x : vec)会复制每个元素数据量大时拖慢不少。第三注意size()返回的是size_t是无符号整数。在做类似v.size() - 1运算时如果v为空会变成极其大的正整数。所以写for (int i 0; i (int)v.size(); i)我一般会显式转换目的就是避免无符号和有符号比较的坑。2.2 unordered_map的哈希陷阱unordered_map是哈希表实现的理论上查找是O(1)真用起来问题不少。首先是迭代顺序不固定这个在很多涉及“字典序输出”的题目里会坑人。你需要排序输出时直接把键值对拿出来放vector再sort就好。其次是哈希碰撞与退化。标准库的哈希函数对整数来说通常是“取模”在恶意数据下可能退化到O(n)。但更多时候问题出在并发场景以外的冲突概率上——总之当数据规模很大而且你发现unordered_map表现异常慢时可以先试试换map红黑树严格O(log n)但常数更大或者手动调整参数。还有一个容易被忽略的点unordered_map的扩容是非常昂贵的操作。同样如果已知最大插入量可以提前reserveunordered_mapint, int mp; mp.reserve(1024); mp.max_load_factor(0.7);max_load_factor设置得低一点让哈希表没那么“满”查找效率会更高代价是更多内存。刷题环境下内存一般够用可以这么换时间。2.3 set与priority_queue谁来解决TopK问题set和multiset底层是红黑树自带排序和唯一性在需要动态维护有序集合并查找前驱后继时很好用。但如果你只需要“每次取最大/最小的那一个”priority_queue才是正解因为它的常数比set小得多底层是二叉堆插入和删除都是O(log n)。常见的小根堆写法priority_queueint, vectorint, greaterint pq;默认priority_queueint是大根堆会取最大值。用greaterint改成小根堆。这里注意greaterint需要包含头文件functional。在实际写题时判断“该用set还是priority_queue”有个很简单的标准你需不需要在任意时刻删除某个中间元素需要就用set不需要就用堆。比如经典的“数据流中的中位数”一边是大根堆存较小一半一边是小根堆存较大一半用两个priority_queue就能高效维护。2.4 手写数据结构的必要时刻刷题初期会觉得“STL够用就行为什么要手写”。等遇到单调栈、单调队列、并查集、线段树你会发现它们本质上是数据结构和算法思维的结合体STL根本没有现成版本。比如单调队列通常用来维护区间最值我习惯用数组模拟双端队列dequeint dq; for (int i 0; i n; i) { while (!dq.empty() a[dq.back()] a[i]) dq.pop_back(); dq.push_back(i); // 窗口滑出队首 while (!dq.empty() dq.front() i - k) dq.pop_front(); }如果数据量特别大deque的封装可能会有额外开销可以用静态数组模拟int q[N]; int head 0, tail 0;下标存元素编号。类似的还有手写并查集路径压缩和按秩合并的写法非常固定背下来几乎是送分题。3. 高频算法模板与思路避坑从暴力到最优解算法题归根结底是套路题。下面几个模板是我在刷题时遇到的最高频且最容易写错的类型每个都值得单独拿出来推敲。3.1 二分查找永远的边界问题二分查找的边界问题是所有算法初学者最大的“血泪区”。代码本身很短但每一行都有讲究。标准库提供的lower_bound和upper_bound其实已经能解决大部分查询问题lower_bound返回第一个大于等于目标值的迭代器upper_bound返回第一个大于目标值的迭代器。直接用它们不要自己手写二分去查有序数组中的固定值。但有些题目的条件并不是“查找一个值”而是“给定一种判定函数求满足条件的最小/最大解”也就是“二分答案”。我总结了一套行之有效的写法// 求满足check(mid)的最小值 int l 0, r n - 1; while (l r) { int mid (l r) 1; if (check(mid)) r mid; else l mid 1; } // 此时 l r 即为答案如果要求满足条件的最大值则用另一套写法int l 0, r n - 1; while (l r) { int mid (l r 1) 1; if (check(mid)) l mid; else r mid - 1; }注意第二套里mid (l r 1) 1多了个1。原因很简单如果l和r相邻mid (l r) 1会等于l一旦check(mid)依然成立l mid后就陷入了l和r都不变的死循环。这个1就是用来让mid偏向右侧从而跳出循环。我在某次模拟题里就曾用错第二套模板导致死循环本地完全看不出问题OJ直接Time Limit Exceeded。从那以后我就把两套模板写在笔记开头每次二分都先分清是“求左边界”还是“求右边界”。3.2 动态规划状态设计四步法动态规划DP看起来千变万化其实核心就是四件事状态定义、初始化、状态转移方程、最终答案取哪个值。我写DP题有个习惯先问自己“如果我现在只关心某个阶段的某个信息最少需要记录什么”。比如背包问题最少需要记录的就是“当前容量下能装的最大价值”所以状态是dp[j]表示容量为j时的最大价值。然后初始化dp[0] 0其他为负无穷表示这些状态不可达。最后转移for (int i 0; i n; i) { for (int j W; j w[i]; j--) { dp[j] max(dp[j], dp[j - w[i]] v[i]); } }这里为什么从W倒序遍历到w[i]因为01背包要求每个物品只能选一次如果正序遍历dp[j - w[i]]可能已经在当前轮次更新过相当于同一个物品被用了多次。倒序则保证每个物品最多被放入一次。经典的最长递增子序列LIS除了O(n^2)的DP外还有O(n log n)的贪心二分做法维护一个tails数组记录长度为i的递增子序列最小末尾值。这类从“基础DP”到“优化DP”的进阶路径其实就是算法笔记里最值得记的部分。3.3 DFS/BFS搜索界的flood fill与剪枝搜索题最忌一上来就写递归。我的习惯是先判断图是稠密还是稀疏、状态是连续还是离散再决定用DFS还是BFS。BFS天然适合计算无权图的最短路因为它按层扩展第一次到达某个点时走的步数一定是最短的。模板很固定queueint q; vectorint dist(n, -1); dist[start] 0; q.push(start); while (!q.empty()) { int u q.front(); q.pop(); for (int v : adj[u]) { if (dist[v] -1) { dist[v] dist[u] 1; q.push(v); } } }DFS则更适合需要枚举所有路径、判断连通性、以及在图上进行回溯的场景。写DFS时我特别关注两件事一是显式的visited数组。有时候图不是简单的二维网格可能出现通过不同路径到达同一状态但步数不同这时需要结合“状态压缩”或“最短路思想”。二是剪枝的顺序。先走优先级高的分支往往能更快找到可行解并排除更多无效分支这种“启发式剪枝”在数独、N皇后等问题上立竿见影。3.4 贪心证明习惯比代码更重要贪心算法的坑在于“看起来对”的解法经常是错的。所以我养成了一个习惯每写一个贪心策略先花几分钟想反例再用排序不等式或交换论证法证明其最优性。举个经典例子区间调度问题给一堆区间挑出互不重叠的最多区间。正确策略是按右端点排序然后尽量选右端点靠前的区间。为什么因为右端点越小给后面留的空间越大。用交换论证法可以严格证明任何最优解如果不包含右端点最小的那个区间一定可以用它替换掉第一个区间而不影响数量。如果题目表面上是贪心但你需要处理的东西带优先级、顺序约束往往就要回到DP或网络流。判断标准很简单局部最优能不能直接推到全局最优如果能才考虑贪心。3.5 图论常用模板Dijkstra与并查集Dijkstra用优先队列优化后非常简洁我放在手边当“板子”用priority_queuepairint,int, vectorpairint,int, greaterpairint,int pq; vectorint dist(n, 0x3f3f3f3f); dist[s] 0; pq.push({0, s}); while (!pq.empty()) { auto [d, u] pq.top(); pq.pop(); if (d dist[u]) continue; for (auto [v, w] : adj[u]) { if (dist[v] d w) { dist[v] d w; pq.push({dist[v], v}); } } }0x3f3f3f3f是常用的“无穷大”技巧因为它满足“无穷大加无穷大还在int范围内”方便做松弛操作。并查集的模板则是int find(int x) { return fa[x] x ? x : fa[x] find(fa[x]); // 路径压缩 } void unite(int x, int y) { int fx find(x), fy find(y); if (fx fy) return; fa[fx] fy; }记得初始化fa[i] i。如果讲究效率还可以加sz数组做按大小合并。我在实际写题中发现很多“判断图是否连通”“动态连边”的题目并查集是最直接的工具复杂度低到几乎可以忽略。4. 时间与空间复杂度刷题时的“算账”能力算法能不能过很多情况下不是看你写的多优雅而是看你有没有提前估算复杂度避开超时的坑。4.1 一秒大概能跑多少次运算不少同学听到“1秒内需要完成约1e8次简单运算”这个经验值但实际比这个更保守。现代CPU在O2优化下可能跑更多但OJ上还有IO开销、STL常数、分支预测失败等因素。我的经验是纯循环累加、数组遍历1e8次通常没问题如果有sortO(n log n)、unordered_map操作、递归调用1e7到5e7就比较紧张如果涉及高精度、字符串拼接、动态分配1e6次操作都可能在1秒边缘。所以拿到题先看数据范围再反推算法复杂度数据范围 n能接受的复杂度n ≤ 10O(n!) 或 2^n 级别的枚举n ≤ 20O(2^n) 或 n*2^n 状态压缩n ≤ 100O(n^3) DP或Floyd类n ≤ 1000O(n^2) 常规DP、暴力n ≤ 1e5O(n log n) sort、二分、线段树n ≤ 1e6O(n) 线性扫描n ≤ 1e7几乎只能O(n)且常数非常小这张表基本上是刷题界的“基准汇率表”。看到n ≤ 1e5你脑子里直接浮现“排序二分/树状数组/线段树”看到n ≤ 20可以试着状压DP。这种“范围→复杂度→数据结构”的映射能力是拿题之后第一步要练的。4.2 iostream在实际题目中的表现前面提到ios::sync_with_stdio(false)后cin/cout可以变快那是不是可以放心用cin了大部分情况下是但有两个例外你混用了cin和scanf。如果开了sync_with_stdio(false)后又调用scanf整个IO状态会变得不可预测轻则顺序错乱重则死循环。输出量极大且频繁使用endl。endl不只是换行还附带刷新缓冲区刷几百次就慢了。换成\n性能会回归正常。属于“用错了工具”而不是“工具不好”。我自己一般只在大整数输入时才用快读其他时候全用cin/cout没有任何心理负担。4.3 cache友好与内存布局很多性能问题的根源不是算法复杂度而是缓存命中率太低。刷题阶段最容易踩的一个坑是用一个二维数组vectorvectorint存矩阵并且按行遍历和按列遍历的性能差距能到好几倍。原因在于CPU缓存是按块加载的连续内存访问命中率高。所以能开静态数组就开静态数组const int N 1005; int a[N][N];如果必须用vector也尽量一次性开一个一维数组然后自己计算下标idx i * m j。这种方式既避免分配过多小块内存又能让访问尽量连续。还有一个优化细节尽量少用new和delete刷题时优先使用静态内存或栈上数组。new是堆分配性能差且容易内存碎片化。4.4 栈空间与递归深度递归写起来爽但栈空间是有限的。在OJ上默认栈大小可能只有8MB左右一个DFS深度达到几十万上万就可能导致栈溢出Segmentation Fault。之前我在某道搜索题上递归深度是n而n可以到1e5本地跑得好好的OJ上直接RE。后来我把DFS改成了显式栈的迭代写法或者用BFS从叶子向上处理才过了题。一个大数组变量如果定义在函数内部且是局部变量也可能把栈撑爆。解决办法很简单把大数组设置成全局静态变量放在.bss段不占用运行时栈空间。这个习惯在新手阶段就应该养成。5. 本地AC提交却RE/WA问题排查与调试实录我敢打赌每个刷题的人都被“本地明明运行正常一交上去就错”折磨过。下面是我踩坑最多、也是群里同学问最多的几类情况。5.1 段错误RE的三大来源段错误最典型的原因有数组越界。比如数组开成a[100]循环却访问a[100]下标越界。解决办法要么数组开大一格要么写循环时严格注意边界 n。野指针或者空指针解引用。比如vector里存的坐标可能超出边界却没有先判断。递归栈溢出。这我已经在4.4节反复说了优先用迭代。定位段错误最快的方法是本地开-fsanitizeaddress它会在越界发生的第一时间报出具体文件和行号比猜半天瞎改快得多。5.2 整数溢出与负数取模刷题必须养成一个习惯凡是可能累积到10^9以上的量直接开long long。别觉得“题目前面明明是int范围”过程值溢出不等于最终结果溢出。比如计算a * b c如果a和b都是inta * b这一步就可能溢出。正确写法是1LL * a * b c或提前把a、b转成long long。负数取模也是一个大坑。C里(-5) % 3的结果是-2而不是1。很多题目要求对负模的结果是非负的此时需要手动调整int mod (x % MOD MOD) % MOD;另外INT_MIN取绝对值也会溢出处理时先转long long再取绝对值。5.3 unordered_map被卡的“不科学”情况我有一段时间在某个数据量较大的题目里用了unordered_map本地自测随机数据全过提交上去却TLE。后来才意识到这是典型的哈希碰撞攻击或者说是STL默认哈希策略在大量整数取模时不够“均匀”。常见的应对方式有三个换成mapint, int红黑树稳定O(log n)但常数较大。自定义哈希函数让它更随机地分布到桶中struct custom_hash { static uint64_t splitmix64(uint64_t x) { x 0x9e3779b97f4a7c15; x (x ^ (x 30)) * 0xbf58476d1ce4e5b9; x (x ^ (x 27)) * 0x94d049bb133111eb; return x ^ (x 31); } size_t operator()(uint64_t x) const { static const uint64_t FIXED_RANDOM chrono::steady_clock::now().time_since_epoch().count(); return splitmix64(x FIXED_RANDOM); } }; unordered_mapint, int, custom_hash mp;如果键是整数且范围不大直接开数组用下标当键连哈希都省了。说实话我后来很多题目直接用桶或者map反而少了很多烦恼。只有在“需要频繁查找且插入删除量巨大”时才考虑自定义哈希的unordered_map。5.4 多组数据初始化的隐患OJ题经常说“输入包含多组测试数据”这时候最怕全局变量或静态数组没清空。比如你定义了一个全局的vis数组上一次数据把它变成全1第二组数据判断某个状态是否访问过时就会全部跳过导致答案错误。我的习惯是while (cin n) { // 每一轮开始都要重置需要用的数组和容器 fill(vis, vis N, 0); for (int i 0; i N; i) adj[i].clear(); // ... 处理这组数据 ... }或者直接用memset(vis, 0, sizeof(vis))但要小心memset只能对连续内存的普通数组有效对vector用memset是未定义行为千万别干。5.5 边界条件自查清单我提交前通常会过一遍这个清单n1时循环是否还能进去数组下标会不会到-1或n如果输入是空串/空数组代码会不会直接崩溃有没有用到未初始化的变量二分模板有没有可能死循环数据范围是否必须开long long这些问题比“我的思路对不对”更致命因为思路错了还能换个思路边界错了往往让你百思不得其解。6. 如何让C算法笔记真正“长”在你的能力里最后这部分不是讲某个模板而是讲“笔记”和“能力”之间的关系。我自己也走过为了记笔记而记笔记的弯路后来才总结出几个实用的维护方法。6.1 笔记要记什么不是抄代码而是记决策很多人写算法笔记就是从题解里抄一遍代码然后收藏吃灰。真正有用的笔记应该包含下面几类信息题目背后的考察点。例如“这题考察二分答案贪心判定”比记住代码要紧得多。错误点分析。每次WA或TLE后把原因写下来例如“数组开小了导致越界”、“没做负数取模处理”、“sort比较函数没写严格弱序”。这些是你个人的“避雷数据库”。复杂度推导。哪怕是抄的题解你也可以自己算一下为什么复杂度是O(n log n)把推导过程写两行比背结论强。同类型题目的对比。比如“单调栈可以处理左边第一个比当前元素大的位置”和“单调队列可以处理滑动窗口最值”放在一起对比记忆。6.2 从刷题模板到工程思维的迁移刷算法题有一个额外的好处当你能持续写出边界正确、效率合格的C代码时再做工程项目里那些模块开发你对内存和复杂度的敏感度会明显比别人高。比如工程里要求尽量少构造临时对象、尽量用move语义传参、注意缓存局部性这些和刷题时用reserve、用连续内存、少开大对象是同一套逻辑。算法笔记里积累的STL用法将来在写生产代码时也会经常用上。所以我建议不要把算法题目标仅仅看成“答题”当成一种系统性训练C编码能力的练习会让你的学习动力更持久。6.3 小技巧写题解给别人看一个很有效的记忆方法每做完一道有价值的题尝试把它讲给一个完全没思路的人听。你不用真的找到听众可以自己写一段文字解释“为什么这么想”“第一步为什么是排序”“为什么用这个数据结构”。当你发现自己没法清晰解释某一步时说明你理解还不到位这恰好是重新查资料、补漏洞的时机。我现在还能几乎条件反射地默写出二分模板、Dijkstra模板、并查集模板其实不是因为我把它们背了多少遍而是我在写题解时反复把“为什么”解释了一遍又一遍。这种内化的过程比任何收藏夹都管用。