从刚入门C刷题那会儿我最大的感受就是“那些AC的题解怎么都用上了我没见过的API”。同样的逻辑有人用三行STL搞定有人却要手写十行还容易出错。C算法题里最值钱的不是语法本身而是标准库那些被反复验证过的“轮子”。这篇我就把刷题两年多来真正高频、真正救过命的C算法常用API理一遍包括输入输出优化、容器选型、排序二分、字符串处理、位运算、图论写法再附上我踩过的坑。全文适合正在刷leetcode、蓝桥杯、ACM校赛或者准备算法面试的朋友C基础要有一点但不用深。1. 输入输出别让性能瓶颈卡在第一步1.1 同步开关与快速读写模板算法题里最容易让人忽略的是cin和cout的默认行为。C的iostream为了和C标准库兼容默认会和stdio保持同步这意味着每次cin都会做额外的同步检查数据量一大效率差距非常明显。我见过不少新手在10^5级数据下用cin超时换了scanf立刻过。但这不是说必须放弃cin而是要先做两件事ios::sync_with_stdio(false);和cin.tie(nullptr);。第一句切断与stdio的同步让cin只走自己的缓冲区第二句解绑cin和cout的绑定关系。默认情况下每次输出都会先刷新输入缓冲区解绑之后速度能再上一个台阶。我个人的习惯模板是这样#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; for (int i 0; i n; i) { int x; cin x; cout x \n; } return 0; }注意输出尽量用\n而不是endl。endl会在换行的同时强制刷新输出缓冲区刷题场景完全没必要白白损失性能。这个细节在输出量大的题里特别致命我有一次就是全用endl超时改成换行符直接快了一倍。1.2 格式化输出与浮点精度控制算法题常遇到要求输出固定小数位数的场景比如“保留两位小数”。纯用cout的话要记得加fixed setprecision(n)cout fixed setprecision(2) ans \n;fixed表示以定点形式输出不写的话setprecision(2)是对总有效位数生效结果很可能和预期完全不一样。我试过不少次忘记加fixed输出9.9的地方变成了9.8999排查半天才发现是格式问题。读取字符串时还要注意一个细节cin s遇到空格会停止而很多题面的整行输入会包含空格这时候需要用getline(cin, str)。但getline有一个经典大坑如果前面用过cin 输入流里会残留一个换行符getline会直接读到空串。解决方法很简单在getline之前加一句cin.ignore();把残留的换行吞掉。这个坑几乎每个刷题的人都踩过。2. 容器选型用对容器等于省一半时间2.1 vector 与 string默认选择背后的扩容逻辑vector和string是刷题时最高频的两个连续容器绝大多数情况它们是默认选择。vector的底层是动态数组支持随机访问尾部插入删除是O(1)均摊中间插入删除是O(n)。很多人不知道的是vector扩容不是每次加一个元素就重新分配一次内存而是按比例扩容常见编译器是1.5倍或2倍均摊复杂度才是O(1)。但扩容有一个隐藏代价元素移动。如果元素是自定义结构体且比较重扩容时会触发大量拷贝影响性能。如果事先知道数据规模直接vectorint v(n);预留空间避免中途扩容。另一个细节是v.reserve(n)只预留容量不改变大小v.resize(n)会改变大小并构造元素两者用途完全不同别搞混。string本质上也是动态数组但多了字符串专用操作。刷题时经常有人纠结用char[]还是string我的建议是无脑string。它管理内存、支持直接拼接、有丰富的成员函数关键是写起来快不容易出现数组越界或者忘记\0这样的低级问题。2.2 map 与 unordered_map有序与哈希怎么选说到键值对很多人第一反应是map然后发现运行时间不好看换成unordered_map又经常担心哈希冲突。我用这两个容器的经验可以总结成几句话。map底层是红黑树保证键有序所有操作O(log n)这个复杂度非常稳定不管数据怎么构造都不会退化。需要按键排序输出、找大于某个键的第一个元素、求前驱后继时map是无脑选择。unordered_map底层是哈希表均摊O(1)听起来快得多。但哈希表存在几个隐患第一是哈希冲突极端构造的数据能让冲突急剧增加退化到O(n)这在算法竞赛里是可以被卡死的点第二是unordered_map的内存占用普遍比map大第三就是自定义类型需要自己提供哈希函数比较繁琐。我的选型原则是需要有序性选map纯查询、数据随机、键类型是int/string等内置类型时优先unordered_map。但如果你不确定数据会不会被针对性构造老老实实用map最安全。这个“安全第一”的思路在ACM区域赛级别的题里尤其重要。2.3 queue、stack、deque与priority_queue的适用场景队列、栈、双端队列、优先队列四兄弟各自有非常明确的适用场景。queue就是BFS的标配FIFO顺序没有任何取巧空间直接用。stack常用于DFS的迭代实现、括号匹配、表达式求值这类题目。deque是双端队列两端插入删除都是O(1)滑动窗口问题里特别好用因为它支持从头和尾部同时操作。priority_queue是算法题里最被低估的容器它是堆结构底层默认是大根堆也就是队头元素最大。需要小根堆时要么声明时多写两个参数要么直接存负数。最省事的写法是priority_queueint, vectorint, greaterint pq; // 小根堆图论里的Dijkstra、贪心里的“每次取最小值”、合并果子这类经典题全都要靠它。用过之后你会发现手写堆的场景在刷题阶段基本消失了priority_queue就是帮你把堆封装好的那个轮子。3. 常用算法API刷题时的“军火库”3.1 sort、stable_sort与自定义比较排序是算法题里最基础的技能C的sort是内省排序平均情况O(n log n)最坏情况下也能保证O(n log n)实际上用的是一种结合快排、堆排、插入排序的混合策略。直接对vector排序sort(v.begin(), v.end()); // 升序 sort(v.rbegin(), v.rend()); // 降序反向迭代器rbegin和rend估计是很多人会忽略的高级用法它比sort(v.begin(), v.end(), greaterint())写起来更短。自定义排序也是刷题高频需求比如按结构体某个字段排序。核心写法是用lambda表达式作为比较器sort(v.begin(), v.end(), [](const Node a, const Node b) { return a.val b.val; // 按val降序 });stable_sort的区别在于它是稳定的相同关键字的元素不改变相对顺序。大多数排序题用sort就够了如果需要同时按多个字段排序并且要求主关键字相同时保持输入顺序那就必须用stable_sort或者在比较器里对次关键字也做判断。3.2 lower_bound与upper_bound二分边界不再手写手写二分是大忌不是不能写是太容易在处理边界时翻车。C标准库的lower_bound和upper_bound是刷题党的救星两者都要求序列已经有序。lower_bound(begin, end, x)返回第一个大于等于x的迭代器upper_bound(begin, end, x)返回第一个大于x的迭代器它们在二分查找、判断元素是否存在、统计某个值的出现次数、插入位置确定等场景里无所不能。配合vector使用int pos lower_bound(v.begin(), v.end(), x) - v.begin(); bool exists binary_search(v.begin(), v.end(), x);binary_search只返回是否存在不返回位置所以实际刷题中lower_bound的后两个兄弟用处更大。还有一个绝妙的组合用lower_bound在二分答案里配合前缀和做区间计数这个技巧在二维前缀和、树状数组问题里反复出现。equal_range是我后来才发现的一个宝贝它一次性返回等于某值的区间范围相当于同时调用lower_bound和upper_bound。返回pair可以直接用来统计某个值在有序数组里出现的区间起点和终点。3.3 accumulate、minmax_element与iota的妙用这三个函数虽然不那么显眼但关键时刻非常省事。accumulate用来求和int sum accumulate(v.begin(), v.end(), 0); long long sum accumulate(v.begin(), v.end(), 0LL);注意第三个参数是初始值类型决定了整个累加的类型。如果容器里存的是int直接传0求和结果会被截断成int。涉及大数时后面一定加0LL这个细节坑了不少人包括我。minmax_element一趟遍历同时拿到最小值和最大值比单独调两次min_element和max_element效率更高auto [minIt, maxIt] minmax_element(v.begin(), v.end());iota的作用是把区间依次填充为递增的值比如把一个数组初始化为1,2,3,...再配上一个按照某种规则排序的lambda可以实现“把下标按对应值的大小排序”这类需求。这种“间接排序”的高频技巧配合iota能写得非常优雅。3.4 next_permutation全排列问题的最短解全排列问题几乎是入门必刷的题如果每次都手写回溯费时又容易错。标准库的next_permutation(begin, end)直接给出字典序的下一排列配合do-while循环可以枚举所有排列sort(a.begin(), a.end()); // 必须先排序才能从最小排列开始 do { // 处理当前排列 } while (next_permutation(a.begin(), a.end()));类似的还有prev_permutation生成上一排列实际用得少但偶尔需要从某个已知排列开始逆序枚举时很有用。这一个API足以应付入门阶段几乎所有的全排列枚举题不需要手写递归。4. 字符串与数值转换一头一尾的高频操作4.1 字符串与数字互转的几种方式算法题里字符串与数字的互相转换出现频率极高。C提供的最简方法是int x stoi(s); // string转int遇到非法字符会抛异常 long long y stoll(s); // string转long long string t to_string(x); // 数字转stringstoi系列还能指定起始位置和进制stoi(s, nullptr, 16)表示按16进制解析。但要注意它的抛异常行为如果在刷题的环境里输入一定合法可以放心用如果输入可能包含非数字字符需要考虑捕获std::invalid_argument异常或者用stringstreamstringstream ss(s); int x; ss x;stringstream的缺点是慢在循环里大量做转换时性能拉胯。我通常只在需要复杂解析比如同时包含字母和数字需要多次抽取时才用它。遇到超大的数字比如10^18以上long long也装不下可以考虑直接用字符串处理或者用__int128这在GCC下可用但要注意它不能直接通过iostream输入输出需要自己写转换。4.2 substr、find和split的常见姿势刷题时对字符串的处理主要集中在截取、查找、分割三类需求。substr截取子串string sub s.substr(pos, len); // 从pos开始取len个字符第二个参数不写则一直取到末尾。这个函数很好用但耗时是O(len)如果你反复截取一个长字符串的多个子串再做处理性能会翻车。更优的做法是用下标直接访问原字符串避免拷贝。find查找某个子串或字符的位置size_t pos s.find(abc); // 找不到时返回string::npos判断等用if (pos ! string::npos)这个习惯要刻进肌肉记忆因为string::npos的实际值是最大size_t直接当真值判断容易踩坑。split在C里没有现成API这是许多转Python选手最不适应的点。最常用的替代姿势是配合getline用分隔符切割stringstream ss(s); string token; while (getline(ss, token, ,)) { // 按逗号切割 }要注意的是这种方式会吞掉空字符串某些场景需要保留空token时得自己写手动扫描。4.3 前缀和与哈希的API配合前缀和本身不算API但在算法题里应用范围极广。它解决的问题是“区间和”的高频查询做法是先预处理数组vectorlong long pre(n 1, 0); for (int i 0; i n; i) { pre[i 1] pre[i] a[i]; } // 区间[l, r]的和 pre[r 1] - pre[l]有了前缀和后如果还需要快速判断某个区间内某个字符/数字出现的次数可以扩展成“前缀计数数组”每类字符维护一个前缀和。另外遇到字符串匹配的题KMP是经典解法。标准库没有提供KMP但大多数刷题平台支持C17的std::search或std::string::find它们的实现通常足够快适合数据规模不大的题。数据量大或者需要严格复杂度时还是要手写next数组实现KMP。这个差距在特定题里非常明显比如1010个长度级别的字符串匹配find在极端情况下退化会超时。5. 位运算与图论场景的API速查5.1 __builtin系列一个循环都不写位运算是很多竞赛题的隐藏考点。GCC系编译器的__builtin系列函数是刷题党爱不释手的武器int cnt __builtin_popcount(x); // 统计二进制中1的个数 int cnt __builtin_popcountll(x); // long long版本 int low __builtin_ctz(x); // 末尾0的个数即lowbit对应的是2^ctz int high __builtin_clz(x); // 前导0的个数其中__builtin_ctz和(x -x)结合使用可以直接拿到最低位的1对应的值这在树状数组、枚举子集时非常关键。比如循环枚举一个集合的子集可以用这个技巧for (int sub mask; sub; sub (sub - 1) mask) { // 子集sub }配合popcount做剪枝也极其常见比如判断一个数是不是2的幂__builtin_popcount(x) 1。5.2 邻接表与pair的组合使用图论题的存图方式邻接表是默认选择。相比直接用vectorvectorint graph带权图更常用的是vectorpairint, int第一个int存邻居节点第二个int存边权vectorvectorpairint, int graph(n); graph[u].push_back({v, w});C11以后花括号初始化pair非常方便直接{v, w}就能构造。访问的时候用for (auto [v, w] : graph[u]) { // 处理边u-v权值为w }结构绑定语法让遍历看起来非常清爽这也是我现在写图的固定姿势。相比定义结构体Edge再重载操作符pair方案在写法上短了一截逻辑也更直接。5.3 Dijkstra中的优先队列写法最短路里的Dijkstra是优先队列的经典应用。算法思路是每次从未确定最短路的节点中取出距离最小的节点进行松弛这个“取出最小”由priority_queue完成。常见的写法const long long INF 0x3f3f3f3f3f3f3f3fLL; vectorlong long dist(n, INF); priority_queuepairlong long, int, vectorpairlong long, int, greaterpairlong long, int pq; 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] : graph[u]) { if (dist[v] dist[u] w) { dist[v] dist[u] w; pq.push({dist[v], v}); } } }这里优先队列存的是pair距离, 节点号默认排序先比较第一维再比较第二维刚好满足“按距离取最小”的需求。小根堆用greater参数声明注意头文件是queue和functional不过用bits/stdc.h的话都一起带进来了。“跳过过期元素”那行continue必须有否则同一个节点可能被重复松弛多次复杂度会退化。6. 避坑指南这些坑我踩过你直接避开6.1 迭代器失效与删除时的循环写法用vector和string时插入和删除操作会导致迭代器失效这是入门者最容易翻车的点之一。比如在for循环里直接erase某个元素然后继续对同一个迭代器操作轻则逻辑错误重则崩溃。删除满足条件的元素最健壮的方式是配合remove-erase惯用法v.erase(remove_if(v.begin(), v.end(), [](int x) { return x % 2 0; }), v.end());remove_if把不删除的元素挪到前面返回新的逻辑尾部erase再把后面的残留删掉。这一套组合不仅代码短而且是O(n)比循环erase高效得多。如果一定要在遍历中删除必须用迭代器返回值的惯用法for (auto it v.begin(); it ! v.end(); ) { if (*it % 2 0) it v.erase(it); else it; }这里erase返回下一个有效迭代器相当于每次删除后更新it。这个细节记不住的话用remove-erase是最省心的。6.2 比较函数与严格弱序自定义比较器翻车多半是因为没有遵循“严格弱序”的规则。简单说就是比较器的结果必须像小于号那样满足不对称、可传递、每个元素与自身不成立这三个要求。最容易出的错误是写反了等号或者把、写进去。sort(v.begin(), v.end(), [](int a, int b) { return a b; // 错误 });用违反严格弱序会让sort的底层逻辑无法正确处理相等元素可能导致排序结果完全乱掉甚至越界崩溃。正确写法是return a b;。同理多字段比较时要小心对每个字段都使用严格的或者不要在某个地方写成。这个坑排查起来特别费劲因为程序没有明显报错但结果就是不对劲。6.3 unordered_map的哈希冲突与自定义哈希unordered_map虽然平均O(1)但哈希函数被专门构造的攻击数据卡死时复杂度会退化。某些刷题平台上有专门卡unordered_mapstring, int的测试点特别是当键是自己构造的结构体或者长字符串时冲突概率更高。一个实用的改善方法是给unordered_map指定自定义哈希struct CustomHash { static uint64_t splitmix64(uint64_t x) { x 0x9e3779b97f4a7c15ULL; x (x ^ (x 30)) * 0xbf58476d1ce4e5b9ULL; x (x ^ (x 27)) * 0x94d049bb133111ebULL; 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_maplong long, int, CustomHash mp;这样即使键是连续增长的数值也不会因为默认哈希的规律性导致大量碰撞。不过话说回来题目没有明确针对哈希容器构造数据时默认的unordered_map完全够用不要过早优化先跑一遍再考虑替换。6.4 暴力枚举与剪枝的心态问题最后聊点非API层面的心得。很多新手面对暴力枚举题第一反应是“这题没技术含量”但实际上暴力剪枝往往是一道题从TLE到AC的关键。所谓剪枝就是在枚举的过程中提前排除不可能产生答案的分支。比如排列组合类问题可以先判断当前部分前缀已经超过目标值就直接return不再继续深入。配合C的API剪枝实现的常见手法是先排序再枚举方便提前判断或者在回溯函数里用参数传递当前累积值避免重复计算。如果一道题的数据范围在20左右二进制枚举子集加popcount判断往往比复杂的动态规划还快代码量也小。暴力枚举不是丢人的解法能在限定范围内跑出正确答案就是好解法等遇到数据规模推不动了再去想优化策略。我见过不少选手一上来就写高级数据结构结果代码半天调不通反而是先暴力后剪枝的版本秒过这种“从暴力出发向优化演进”的节奏才是刷题最稳的路径。要说还有什么亲身体会就是刷题时别急着背API列表更重要的记住了功能和适用场景用错了容器再漂亮的API也会变成性能杀手。我自己曾经在优先队列里用过默认的大根堆做Dijkstra样例全过大数据TLE查了一个下午才发现问题。现在我的习惯是每次提交前都快速检查一遍容器选型对不对、比较器是不是严格弱序、输出有没有多余刷新、数据类型有没有溢出。这套检查和上面的API清单一起陪我打了不少比赛也推荐你从现在开始就养成同样的习惯。