1. 先把 C 算法的地图画出来C 算法这个词在多数人的语境里其实混着两层含义一层是数据结构与算法课上那套东西排序、查找、图论、动态规划另一层是 C 标准库algorithm里已经封装好的那批函数sort、lower_bound、next_permutation之类。这两层不是一回事但实际写代码时几乎天天要交叉使用所以一开始就把边界分清楚后面学起来不会拧巴。用最朴素的话讲算法就是把输入变成输出的有限步骤。输入可能是十个整数也可能是几十万个节点的一张图输出可能是一个排好序的数组也可能是一条最短路径。C 在这件事上的特殊之处在于它把运行效率的掌控权交还给了写代码的人——同一道题你用std::vector和用裸数组用值传递和用引用传递跑出来的时间可能差好几倍。这就是为什么很多人明明学了算法思路一提交还是超时。这篇东西适合谁看正在被 C 八股文和笔试题折磨的在校生、写了两三年业务代码但没系统梳理过算法的工程师、以及想从 Python 或 Java 转过来写 C 的人。我会按“分类讲思路 给能直接跑的代码 说清楚什么时候不该用”的方式铺开不搞那种只留个结论的条目式罗列。代码默认用 C17 编译因为结构化绑定和std::greater的透明比较在刷题里太省事了。写到这里先给一张全局表方便你决定先看哪一节。这张表我建议存下来它不是知识清单而是选型清单。算法大类典型代表常见触发场景数据规模感受排序快排、归并、堆排、计数排序数据整理、去重前置、贪心前置n 从 10 到 1e7查找二分、哈希、KMP有序数据定位、字符串匹配查询次数远大于 1图论Dijkstra、Kruskal、拓扑排序路径规划、依赖解析、网络流点边数 1e3 到 1e5动态规划背包、LIS、区间 DP最优化问题、方案计数状态数通常 1e6 以内贪心区间调度、跳跃游戏局部最优可证明全局最优排序后线性扫数论与位运算gcd、快速幂、筛法、lowbit密码、哈希、状态压缩常常是常数级优化搜索与剪枝DFS、BFS、模拟退火状态空间大但可剪指数级必须剪1.1 从业务场景倒推算法分类我不太喜欢按教科书目录去背算法那种“第一章排序、第二章查找”的顺序容易让人学完就忘。更靠谱的做法是从场景倒推你手上有个什么任务任务里最痛的那个点是什么然后去找对应算法。比如日志分析要对 IP 做 TopK 统计那核心就是堆或者nth_element跟排序整个数组没关系比如做任务调度器要判断依赖有没有环那核心就是拓扑排序DFS 三色标记或者 Kahn 入度法都行。这种倒推法的好处是你记的不是名字而是“这一类问题的解法长什么样”。等你遇到新问题能立刻判断它属于哪一类。我见过不少同学背得出十种排序的复杂度但真让他从十亿条日志里找出现次数最多的一百个词他会下意识想“先排序再取”然后内存直接爆掉。顺带说一个热词里常出现的困惑“算法是什么意思”。很多刚入门的人以为算法就是“最优解”其实不是。算法首先得是正确的其次才是高效的。一个跑得飞快但结果错的程序工程价值是负的。所以下面每一节我都会先讲清楚正确性来自哪里再谈怎么优化常数。1.2 一套务实的优先级排法如果时间有限我建议按这个顺序补数组双指针和二分、哈希表、五种排序中的快排和归并、BFS/DFS、Dijkstra、背包和 LIS。这几样覆盖了日常刷题和面试的八成场景。剩下的 Prim、匈牙利算法、模拟退火、KMP属于特定题型才用得上遇到了再学完全来得及。至于复杂度估算这是所有优化的地基。粗略记几条就够了1e8 次简单操作大概一秒不同机器差异很大只是个量级感递归深度超过 1e5 基本会爆栈二维 DP 开到 1e4 × 1e4 就已经是 4 亿 int内存大概 1.6 GB肯定超限。心里有这几个数字写代码前就能筛掉一批注定超时的方案。2. 排序算法面试和工程都绕不开的一类排序是算法的起点也是面试出现频率最高的地方。但要注意面试官问“手写快排”和工程里“该不该自己写排序”是两个完全不同的问题。工程里 99% 的情况你应该直接调用std::sort它的内省排序introsort实现比你临时写的任何版本都稳。手写排序的意义在于理解分治、理解比较次数、理解稳定性这些概念。先说一个容易被忽略的点稳定性。稳定排序意味着相等元素的相对顺序在排序后不变。这个性质在处理“先按时间排再按优先级排”这种多关键字场景时非常关键。std::sort是不稳定的std::stable_sort才是稳定的。我曾经用std::sort处理一个带时间戳的订单列表结果同一秒内的订单顺序被打乱下游对账直接出错排查了两个小时才发现是稳定性问题。2.1 冒泡、选择、插入慢但必须理解冒泡排序的核心是相邻比较交换每轮把最大值“冒”到末尾。加了提前退出标志后最好情况能退化到 O(n)这也是它唯一的亮点。void bubbleSort(std::vectorint a) { int n static_castint(a.size()); 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]) { std::swap(a[j], a[j 1]); swapped true; } } if (!swapped) break; // 本轮无交换已经有序 } }选择排序每轮从未排序区间里挑最小值放到前面比较次数固定为 n(n-1)/2不管数据初始状态如何。它的优点是交换次数最少只有 n-1 次所以在“写操作代价极高”的场景比如某些闪存或外部存储场景反而有一点价值。插入排序是这三个里唯一真正能上生产环境的。它的特点是数据越接近有序越快最好情况 O(n)。很多标准库的排序实现在小数组通常是长度小于 16时会退化成插入排序因为它的常数因子极小在短区间上比快排还快。注意冒泡、选择、插入的平均复杂度都是 O(n²)n 上到 5000 以上就会明显卡顿。刷题时如果看到 n ≤ 5000 并且允许 O(n²)那大概率是让你写这三样的变体比如统计逆序对用插入排序或归并。2.2 归并排序与快速排序分治的两条路归并排序是“先分到底再合并上来”稳定复杂度恒为 O(n log n)代价是需要 O(n) 的额外空间。它的最大价值不只是排序而是归并过程本身可以用来统计逆序对。void mergeSort(std::vectorint a, int l, int r, std::vectorint tmp) { if (l r) return; int m l (r - l) / 2; mergeSort(a, l, m, tmp); mergeSort(a, m 1, r, tmp); int i l, j m 1, k l; while (i m j r) tmp[k] (a[i] a[j]) ? a[i] : a[j]; while (i m) tmp[k] a[i]; while (j r) tmp[k] a[j]; for (int t l; t r; t) a[t] tmp[t]; }快速排序是“先分区再递归”原地排序平均 O(n log n)但最坏会退化到 O(n²)。退化的典型触发条件是“每次都选到极值作为基准”所以在已排好序的数组上直接用首元素做基准是最糟糕的写法。工程上的解法是随机选基准或者三数取中。void quickSort(std::vectorint a, int l, int r) { if (l r) return; int i l - 1, j r 1; int pivot a[l (r - l) / 2]; while (i j) { do i; while (a[i] pivot); do --j; while (a[j] pivot); if (i j) std::swap(a[i], a[j]); } quickSort(a, l, j); quickSort(a, j 1, r); }这段 Hoare 划分写法的好处是不会出现基准值集中在一侧导致的极端退化配合中间取基准实际表现很稳。我实测过在 1e6 随机整数上它和std::sort差距在 10% 以内但如果数组里有大量重复值这段代码会退化成 O(n²)因为划分后重复值被均匀分到两边。这种时候要用三路划分把等于基准的元素单独聚成一堆。2.3 堆排序与优先队列TopK 的正确打开方式堆排序的核心是siftDown这个下沉操作。建堆从最后一个非叶节点开始往前复杂度是 O(n) 而不是 O(n log n)这一点很多人不知道。排序阶段做 n 次“堆顶与末尾交换 下沉”总计 O(n log n)。void siftDown(std::vectorint a, int n, int i) { while (true) { int l 2 * i 1, r 2 * i 2, best i; if (l n a[l] a[best]) best l; if (r n a[r] a[best]) best r; if (best i) break; std::swap(a[i], a[best]); i best; } } void heapSort(std::vectorint a) { int n static_castint(a.size()); for (int i n / 2 - 1; i 0; --i) siftDown(a, n, i); for (int i n - 1; i 0; --i) { std::swap(a[0], a[i]); siftDown(a, i, 0); } }真正在生产里高频出现的是std::priority_queue。求“最大的一百个数”不需要把全部数据排序维护一个大小为 100 的小顶堆即可每次新元素比堆顶大就替换并下沉复杂度 O(n log k)空间 O(k)。数据量上千万的时候这个方案比全排序快一个数量级内存占用还小。2.4 非比较排序的适用边界计数排序适合值域很小的情况比如统计年龄分布0 到 120复杂度 O(n k)。基数排序适合定长整数或字符串从低位到高位逐位分桶。桶排序适合数据均匀分布的场景。这三种的共同点是都突破了 O(n log n) 的比较排序下界代价是对数据分布有假设。使用前必须问自己两个问题值域到底多大数据分布是否可假设我见过有人对一个取值范围到 2^31 的数据做计数排序申请了 20 多亿的数组程序直接被系统杀掉。值域超过 1e7 就基本别考虑计数排序了。2.5 排序算法横向对比与选型算法平均最坏空间稳定性什么时候用冒泡O(n²)O(n²)O(1)稳定教学n 极小且近有序选择O(n²)O(n²)O(1)不稳定写操作代价极高的场景插入O(n²)O(n²)O(1)稳定n 小于 32 的短数组库内部实现归并O(n log n)O(n log n)O(n)稳定要求稳定、或要统计逆序对快排O(n log n)O(n²)O(log n)不稳定通用场景加随机化堆排O(n log n)O(n log n)O(1)不稳定内存吃紧、只关心 TopK计数O(nk)O(nk)O(k)稳定值域小且为整数选型的口诀很简单默认std::sort要稳定用std::stable_sort只求第 k 个用std::nth_element只求前 k 个用优先队列值域小考虑计数排序。这四条能覆盖你写业务代码时 95% 的排序需求。3. 查找与字符串匹配算法查找这块最容易被低估。很多人觉得二分查找“太简单了”结果面试手写十个里有六个写出死循环或者边界错误。二分查找的坑全在while (l r)还是while (l r)、mid更新加不加一这四行代码上。3.1 二分查找边界比思路重要二分的核心前提是单调性。数组必须有序或者判定函数具有单调性这一步更抽象叫“二分答案”。标准写法如下// 返回第一个 target 的位置找不到返回 n int lowerBound(const std::vectorint a, int target) { int l 0, r static_castint(a.size()); // 左闭右开 while (l r) { int mid l (r - l) / 2; // 防溢出 if (a[mid] target) l mid 1; else r mid; } return l; }用左闭右开区间[l, r)可以避免一大堆边界讨论我的建议是永远固定这一种写法不要换。mid l (r - l) / 2这个写法是为了防止l r溢出虽然 C 里 int 溢出是未定义行为但用减法写法图个心安也让代码更容易迁移到其他语言。工程里其实直接用std::lower_bound和std::upper_bound就够了。要特别注意的是upper_bound返回的是第一个大于目标的位置两者相减就是目标值的出现次数。这个技巧在统计频次时很好用int cnt std::upper_bound(a.begin(), a.end(), x) - std::lower_bound(a.begin(), a.end(), x);二分答案是个值得单独拎出来的技巧。当题目问“最小的最大”“最大的最小”时八成是二分答案加一个 check 函数。比如“把 n 本书分给 k 个人抄让抄得最多的人耗时最少”答案的单调性是显然的给的时间越多越容易满足。这类题的写法是把二分套在答案值域上check 函数用贪心验证。3.2 哈希查找与冲突处理std::unordered_map的平均查找是 O(1)但它不是银弹。第一它的常数因子比std::map大不少第二哈希函数被恶意构造时会被卡成 O(n)第三它在 C 标准里不保证迭代顺序稳定。最大的坑是自定义 key 类型时必须提供哈希函数和相等比较。很多人写了个结构体当 key编译时报了一堆模板错误其实只要补两个东西struct Point { int x, y; bool operator(const Point o) const { return x o.x y o.y; } }; struct PointHash { size_t operator()(const Point p) const { return std::hashint()(p.x) * 1315423911u ^ std::hashint()(p.y); } }; std::unordered_mapPoint, int, PointHash mp;另外提醒一句性能如果数据规模不大几千以内直接用std::map或者排序后二分实测经常比unordered_map更快因为它没有分配和哈希开销。这个结论跟直觉相反但你写个 benchmark 一跑就知道了。3.3 KMPnext 数组在干什么KMP 解决的问题是“在主串中找模式串第一次出现的位置”。暴力匹配在失配时会把主串指针回退KMP 的做法是让主串指针永不回退靠模式串自己记录“失配时该跳到哪”。next[i]的含义是模式串前 i1 个字符中最长的相等前后缀长度。失配时跳到next[j-1]因为那里之前的部分一定是匹配的。std::vectorint buildNext(const std::string p) { std::vectorint nxt(p.size(), 0); for (int i 1, j 0; i static_castint(p.size()); i) { while (j 0 p[i] ! p[j]) j nxt[j - 1]; if (p[i] p[j]) j; nxt[i] j; } return nxt; } int kmp(const std::string s, const std::string p) { if (p.empty()) return 0; std::vectorint nxt buildNext(p); for (int i 0, j 0; i static_castint(s.size()); i) { while (j 0 s[i] ! p[j]) j nxt[j - 1]; if (s[i] p[j]) j; if (j static_castint(p.size())) return i - j 1; } return -1; }这两段代码的结构几乎完全一样理解了一个就理解了两个。我建议自己拿纸画一遍p ababaca的 next 数组画完就再也忘不掉了。注意真实工程里做子串查找几十 KB 的文本用std::string::find就够上 GB 的文本检索应该用专门的索引结构而不是纠结 KMP。KMP 的价值更多在算法思维和面试题比如“最短回文串拼接”这类题就是 next 数组的变形。3.4 剪枝搜索算法的生命线剪枝严格说不算独立算法而是 DFS/BFS 的优化手段。核心思想是在搜索过程中提前判断某个分支不可能产生最优解直接砍掉。常见的有最优性剪枝当前代价已超过已知最优解就返回、可行性剪枝剩余量不够满足约束就返回、搜索顺序剪枝先搜分支少的变量。一道典型的题是“数独求解”。不加剪枝的暴力 DFS 要跑到天荒地老加上“优先填候选数字最少的空格”这一条顺序剪枝速度能快几个数量级。记忆化搜索也是一种广义剪枝把已经算过的状态存下来本质是用空间换时间。我这里给个实操建议写 DFS 时先写出最朴素的版本验证正确性跑通之后再逐条加剪枝每加一条都测一下时间变化。一上来就堆五条剪枝很容易出错而且说不清哪条有用。4. 图论算法从最短路到二分图匹配图论算法的学习曲线比排序陡得多因为首先要过“图的存储”这一关。存得不对后面的算法再快也白搭。4.1 存储方式的选择三种主流存法邻接矩阵vectorvectorint g(n, vectorint(n, INF))适合点少边多的稠密图n 一般在 300 以内。优点是查询 O(1)Floyd 算法必须用它。邻接表vectorvectorint g(n)或带权版本vectorvectorpairint,int适合稀疏图是默认选择。链式前向星用数组模拟链表head、to、next、w四个数组内存紧凑常数小竞赛里大量使用但可读性差。我个人的判断标准是n 超过 5000 就一定要用邻接表或前向星邻接矩阵会爆内存。带权图用pairint,int存{邻点, 权重}配合结构化绑定写起来很清爽。4.2 最短路选对算法比优化常数更重要最短路有三个主要算法适用的图性质完全不同。Dijkstra用于非负权图堆优化后复杂度 O(m log n)。核心是每次从优先队列里取出当前距离最小的点用它松弛邻居。const int INF 0x3f3f3f3f; std::vectorint dijkstra(int n, int s, const std::vectorstd::vectorstd::pairint,int g) { std::vectorint dist(n, INF); dist[s] 0; std::priority_queuestd::pairint,int, std::vectorstd::pairint,int, std::greater pq; pq.push({0, s}); while (!pq.empty()) { auto [d, u] pq.top(); pq.pop(); if (d dist[u]) continue; // 过期条目直接跳过 for (auto [v, w] : g[u]) { if (dist[u] w dist[v]) { dist[v] dist[u] w; pq.push({dist[v], v}); } } } return dist; }那段if (d dist[u]) continue;是懒删除的关键。优先队列不支持修改已有的元素所以同一个点可能入队多次比的时候直接跳过旧的即可。少了这一行复杂度会退化。Bellman-Ford用于含负权边的图复杂度 O(nm)。它的额外价值是能判断负环如果第 n 次松弛还能更新说明存在负环。SPFA 是它的队列优化版本平均快很多但最坏仍是 O(nm)某些精心构造的数据能把它卡死。Floyd用于求所有点对的最短路只有三行for (int k 0; k n; k) for (int i 0; i n; i) for (int j 0; j n; j) d[i][j] std::min(d[i][j], d[i][k] d[k][j]);三层循环的顺序绝对不能换k必须在最外层这是动态规划的阶段维度。我见过有人把k放最里面结果在小数据上也能过样例一交就挂。4.3 最小生成树Prim 与 Kruskal最小生成树解决的是“用最小的总代价把所有点连通”。Prim 从任意一个点开始每次把距离生成树最近的点拉进来适合稠密图。Kruskal 把边排序后从小到大尝试加入用并查集判环适合稀疏图。Kruskal 的代码结构非常固定并查集写熟之后五分钟能写完struct DSU { std::vectorint p, sz; explicit DSU(int n) : p(n), sz(n, 1) { std::iota(p.begin(), p.end(), 0); } int find(int x) { return p[x] x ? x : p[x] find(p[x]); } bool unite(int a, int b) { a find(a); b find(b); if (a b) return false; if (sz[a] sz[b]) std::swap(a, b); p[b] a; sz[a] sz[b]; return true; } };路径压缩加按大小合并之后并查集的单次操作复杂度几乎可以看作常数。这里的find用了递归写法合并了路径压缩代码极短。如果点数特别大递归可能爆栈可以改成循环版本。Kruskal 的主流程是边按权排序逐条调unite成功就计数并累加权重累计到 n-1 条边就停。最后判断边数是否为 n-1不是就说明图不连通。4.4 拓扑排序与 BFS/DFS 通用框架拓扑排序处理的是有向无环图上的依赖顺序问题。Kahn 算法最直观统计每个点的入度入度为 0 的入队出队时把邻居入度减一减到 0 就入队。最后如果输出的点数小于总点数说明图里有环。std::vectorint topoSort(int n, const std::vectorstd::vectorint g) { std::vectorint indeg(n, 0), order; for (int u 0; u n; u) for (int v : g[u]) indeg[v]; std::queueint q; for (int i 0; i n; i) if (indeg[i] 0) q.push(i); while (!q.empty()) { int u q.front(); q.pop(); order.push_back(u); for (int v : g[u]) if (--indeg[v] 0) q.push(v); } return order.size() static_castsize_t(n) ? order : std::vectorint{}; }这个模板在工程里对应的场景很多构建系统解析编译依赖、任务调度器排执行顺序、包管理器解析版本依赖。我之前写过一个配置热更新的小工具就用它检测用户配置项之间的循环引用报错信息比系统自带的清晰得多。BFS 求无权图最短路也是必会的从起点开始逐层扩展第一次访问到某个点时的层数就是最短距离。DFS 则用于连通块计数、路径枚举、树上问题。4.5 匈牙利算法与二分图匹配入门匈牙利算法解决的是二分图最大匹配左边一堆点右边一堆点中间有若干可行连线问最多能配成多少对。经典场景是任务分配和排课。核心思路是不断找增广路。对左边每个点尝试匹配如果右边的目标点已被占用就递归地问“那个占用者能不能换一个”能换就让出来。bool dfs(int u, const std::vectorstd::vectorint g, std::vectorint match, std::vectorint vis, int tag) { for (int v : g[u]) { if (vis[v] tag) continue; vis[v] tag; if (match[v] -1 || dfs(match[v], g, match, vis, tag)) { match[v] u; return true; } } return false; }vis数组用tag标记而不是每次清零是个小优化技巧能省掉 O(n) 的清空开销。整体复杂度 O(nm)点数在 500 以内通常没问题。5. 动态规划与贪心最容易被滥用的两类动态规划的核心不是“写出转移方程”而是定义状态。状态定义对了方程自然就出来了状态定义歪了怎么推都别扭。5.1 状态定义的三条经验第一状态要能描述“子问题”也就是“前 i 个元素的最优解是什么”。第二状态要满足最优子结构大问题的最优解能从小问题推出来。第三状态要满足无后效性当前状态确定后后面的决策不受之前怎么走到这里的影响。举个反面例子求最长递增子序列时如果定义为dp[i]表示前 i 个元素的最长递增子序列长度会发现推不动因为不知道结尾元素是多少。正确做法是定义为“以第 i 个元素结尾的最长长度”这样才能比较。5.2 背包问题一维数组的方向是关键01 背包的二维版本是dp[i][j]表示前 i 件物品、容量 j 的最大价值。滚动到一维后容量必须倒序遍历// 01 背包每件物品最多取一次 std::vectorint dp(W 1, 0); for (int i 0; i n; i) for (int j W; j w[i]; --j) dp[j] std::max(dp[j], dp[j - w[i]] v[i]);为什么倒序因为一维数组里dp[j - w[i]]如果被正序遍历先更新了那它就已经包含“第 i 件物品被选过”的信息会导致同一件物品被重复选。倒序保证读到的是上一轮的状态。完全背包每件可取无限次则正好相反容量正序遍历for (int i 0; i n; i) for (int j w[i]; j W; j) dp[j] std::max(dp[j], dp[j - w[i]] v[i]);这两个方向的差异我建议自己动手打断点看一遍数组变化比看十篇博客都管用。多重背包、分组背包都是在这个基础上的变形掌握了基础版本再推很快。5.3 LISO(n²) 到 O(n log n) 的跨越最长递增子序列的朴素做法是 O(n²)用二分优化后可以做到 O(n log n)。做法是维护一个数组tailstails[k]表示长度为 k1 的递增子序列的末尾最小值。这个定义有点绕但性质很好tails本身是严格递增的所以可以二分。int lengthOfLIS(const std::vectorint a) { std::vectorint tails; for (int x : a) { auto it std::lower_bound(tails.begin(), tails.end(), x); if (it tails.end()) tails.push_back(x); else *it x; } return static_castint(tails.size()); }这里用lower_bound求的是严格递增如果要非严格递增允许相等换成upper_bound即可。这是一个非常高频的细节坑。5.4 贪心证明比代码重要贪心的代码往往只有几行难的是证明它是对的。常见证明手段有交换论证把任意最优解通过交换变成贪心解而不变差和归纳法。经典的“跳跃游戏”就是贪心在每个位置能跳到的范围内选一个“下一步能跳最远”的位置作为落点。局部选最远全局也最优这个结论可以用反证法证。区间调度问题也是同类按右端点排序后能选就选得到的区间数最多。我踩过的坑是有些题看起来像贪心实际上必须用 DP。判断标准是“局部最优能不能保证全局最优”如果举得出反例那就老老实实上 DP。比如“硬币找零”面值是任意给定的时候贪心就不成立必须用完全背包。5.5 模拟退火非精确算法的定位模拟退火、粒子群这类启发式算法属于“求近似最优解”的范畴适合解空间巨大、精确算法算不动的场景比如函数极值搜索、旅行商问题的近似解。它们的共同点是有随机性需要调参初始温度、降温系数、迭代次数而且结果不稳定。我的建议是这类算法先在参数上做粗调步长、温度范围再考虑优化收敛速度。而且一定要设一个“保底解”也就是记录搜索过程中历史最优值防止最后一步跳到一个差解上。要不要用它们取决于业务能不能接受“大概对”的结果。6. 数论、位运算与其他高频小算法6.1 质数判断的优化写法判断单个质数的暴力做法是从 2 试到 √n已经够用。进一步优化可以只试 2、3 和形如 6k±1 的数因为所有大于 3 的质数都满足这个形式循环次数能砍掉三分之二。bool isPrime(long long n) { if (n 2) return false; if (n % 2 0) return n 2; if (n % 3 0) return n 3; for (long long i 5; i * i n; i 6) { if (n % i 0 || n % (i 2) 0) return false; } return true; }注意i * i n这里要用long long否则 i 接近 5 万时 i*i 虽然不溢出 int但 n 是 64 位的时候会出问题。这个细节在“判断质数 C 优化”这类场景里被反复提及属于必知项。如果需要判断 1e7 以内的所有质数就要用筛法。埃氏筛 O(n log log n) 已经很够用欧拉线性筛能保证每个合数只被最小质因子筛掉一次复杂度 O(n)代码稍长但常数也不大。写筛法时记得用vectorbool或vectorchar存标记vectorbool是位压缩版本内存能省 8 倍但有代理对象的坑取地址会出问题一般场景直接用没关系。6.2 gcd、快速幂与模运算辗转相除法求最大公约数是最古老的算法之一几行就能写完long long gcd(long long a, long long b) { return b 0 ? a : gcd(b, a % b); } long long lcm(long long a, long long b) { return a / gcd(a, b) * b; }lcm要先除后乘防止中间结果溢出。这个顺序问题在数据接近 int 上限时是致命的。C17 之后标准库自带了std::gcd和std::lcm在numeric里直接用即可。快速幂用来算 a^b mod m把指数按二进制拆开复杂度从 O(b) 降到 O(log b)。写的时候要注意底数先取模以及乘法可能溢出时改用__int128或者龟速乘。6.3 位运算的几个实用技巧位运算在状态压缩和底层优化里用得多。几个我常用的x 1判奇偶比x % 2快但负数取模会出问题位运算不会。x (x - 1)消掉最低位的 1可以用来统计二进制中 1 的个数也能判断是不是 2 的幂结果是 0 就是。x -x取出最低位的 1树状数组里天天用。x 1是乘 2x 1是除 2 向下取整对负数不是除以 2 的语义要注意。__builtin_popcount(x)直接数 1 的个数__builtin_clz数前导零GCC 和 Clang 都支持遇到不支持的编译器可以用std::bitset或者手写查表。状态压缩 DP 是位运算的重灾区用二进制位表示集合的选取状态dp[mask]里的 mask 从 0 遍历到(1n)-1。n 通常在 20 以内因为状态数是指数级的。7. 把算法落到 C 工程里7.1 STL algorithm 里已经有的别重造我见过太多人自己手写快排然后比std::sort慢原因在于标准库用了内省排序——快排递归到一定深度会切换到堆排序防止退化小区间会切换到插入排序降低常数。这些工程细节不是随手能写出来的。常用的几个函数值得记住函数用途复杂度std::sort全排序不稳定O(n log n)std::stable_sort全排序稳定O(n log n)可能 O(n log²n)std::partial_sort前 k 个有序O(n log k)std::nth_element第 k 个就位其余不保证平均 O(n)std::lower_bound第一个 的位置O(log n)std::unique去重需先排序O(n)std::next_permutation下一个排列O(n)std::accumulate求和可自定义操作O(n)std::unique有个大坑它只是把重复元素移到末尾并返回新的逻辑结尾并不会真的删除元素。标准用法是a.erase(std::unique(a.begin(), a.end()), a.end())而且必须先排序因为它只处理相邻的重复。7.2 数据规模决定算法选择这张表是我做题和写业务时都会对照的速查表用 1e8 次操作约 1 秒的粗略基准估算数据规模 n可接受的复杂度典型算法n ≤ 20O(2^n)、O(n!)状压 DP、全排列搜索n ≤ 100O(n³)Floyd、区间 DPn ≤ 5000O(n²)朴素 DP、选择排序n ≤ 1e6O(n log n)快排、堆、Dijkstran ≤ 1e8O(n)双指针、前缀和、筛法n 1e8O(log n)、O(1)二分、公式推导按这个表估一遍能提前筛掉大量注定超时的方案省下的时间够你多做好几道题。7.3 环境与工具链的准备工作写 C 最劝退的环节往往不是算法本身而是环境。几个高频问题提前说清楚。第一用 VS Code 写 C 需要三样东西编译器Linux 用 gWindows 用 MinGW-w64 或 MSVC、tasks.json定义怎么编译、launch.json定义怎么调试。这两份配置文件最容易出错的地方是路径用了相对路径导致换目录就找不到源文件。我的习惯是统一用${file}和${fileDirname}这些内置变量。第二tasks.json里建议加-stdc17 -Wall -Wextra -O2-Wall打开警告能帮你提前发现未使用变量、隐式转换这类问题-O2保证测的是优化后的性能。调试时把-O2换成-g -O0否则断点和单步会错乱。第三安装某些依赖 C/C 扩展的程序时可能遇到提示缺少编译工具链的信息这本质上是环境里没有可用的 C 编译器。正规处理方式是安装官方提供的构建工具链或者改用已经提供预编译包的安装方式不要把时间浪费在到处找来历不明的安装包上。8. 常见问题与排查实录8.1 编译期问题的排查顺序编译报错时我的一般排查顺序是先看第一条错误不要看后面那一堆通常是连锁反应如果是模板相关的长篇报错从最后一行的“required from here”往上找如果是链接错误undefined reference检查函数声明和定义的参数列表是否完全一致尤其是const和引用符号。一个高频场景是模板声明和定义分离到 .h 和 .cpp 两个文件然后链接报错。原因是模板实例化发生在使用处编译器看不到定义就没法生成代码。解法是把定义也放到头文件里或者显式实例化。8.2 运行期问题的常见成因现象可能原因排查手段段错误数组越界、空指针解引用用-fsanitizeaddress编译死循环循环变量未更新、浮点比较打印循环变量观察结果错误但不崩下标从 0 还是 1 开始搞混打断点看首轮状态大数答案错误int 溢出换long long超时复杂度估错、常数太大计时 复杂度重估输出乱码编码不一致统一 UTF-8-fsanitizeaddress是我最推荐的排错工具编译时加上它越界访问会在第一次发生时就报出精确的文件行号比事后加打印快十倍。同样是内存问题-fsanitizeundefined能抓出整数溢出和有符号移位这类未定义行为。8.3 几个我踩过的具体坑第一个坑是整数溢出。写最大子段和的时候用 int 存结果数组长度 1e5、元素 1e9总和能到 1e14直接溢出。这种时候答案会变成一个莫名其妙的小数或者负数。养成习惯只要涉及求和先估一下上界超过 2e9 就用long long。第二个坑是递归爆栈。默认栈空间在 Windows 上通常只有 1 MB 左右深搜 1e5 层必崩。解法有两种把递归改成显式栈的迭代写法或者在图论题里把递归改成手动维护队列的 BFS。竞赛里常用#pragma comment(linker, /STACK:...)来扩栈但工程代码里不推荐这么干。第三个坑是浮点精度。二分答案时如果写成while (r - l 1e-6)循环次数可能因为浮点误差变得不可控。更稳的做法是直接固定循环 100 次二分精度足够而且次数确定。比较浮点数相等时用fabs(a - b) eps别用。第四个坑是**unordered_map的遍历顺序**。标准不保证任何顺序我当时写了个依赖遍历顺序做输出的功能本地跑没问题换台机器结果就乱了。需要有序遍历就用std::map或者把 key 取出来排个序。8.4 调试小技巧合集先说一个最朴素的临时把cin换成scanf或者加ios::sync_with_stdio(false)在输入量百万级时能快好几倍。cin.tie(nullptr)也要一起加上否则cout会在每次cin前自动刷新缓冲。再说一个容易被忽略的assert在 Release 编译下会被NDEBUG宏直接去掉所以别把有副作用的代码塞进assert里。想让它生效就用-UNDEBUG或者自己写个检查宏。最后一个是计时。测算法性能时用std::chrono::steady_clock别用clock()后者测的是 CPU 时间多线程下会失真auto t0 std::chrono::steady_clock::now(); // ... 被测代码 ... auto ms std::chrono::duration_caststd::chrono::milliseconds( std::chrono::steady_clock::now() - t0).count();8.5 算法选型的最后几条经验从我自己这几年的实际使用来看几个判断可以省下很多纠结。第一先在纸上把数据规模写下来套上面那张复杂度表方案自然就收窄了。第二能排序就别用复杂数据结构排序是常数最小、最不容易出错的预处理手段。第三能二分就别用三分能贪心就别上 DP能 DP 就别写搜索。第四写完先测三组数据最小规模、最大规模、全相等或全逆序的边界情况这三组能打掉八成的低级错误。至于学习路径我建议先把 STL 的容器和算法用熟再回头手写排序和查找最后啃图论和 DP。反过来先啃 DP 的话很容易卡在“状态想不出来”上挫败感很强。真正把复杂度分析的直觉练出来是在你写下每一行循环时都下意识知道它会被执行多少次——到那一步算法就不再是需要背的东西了。