简介这是东北大学OJ平台上C语法与STL练习的AC代码合集面向正在刷题备赛的高校学生以及刚接触标准模板库、希望系统提升容器与算法选型能力的C初学者。压缩包内共44个cpp源文件整体仅29KB内容覆盖vector、set、map等常用容器排序、查找、二分等经典算法并包含迭代器、仿函数与pair的基础应用。代码按题目编号独立组织便于逐题对照OJ原题复现AC过程通过对比不同题解可直观理解何时选择关联容器、何时使用优先队列以及如何通过仿函数定制排序规则。目前已有668人学习下载适合想在正式比赛前快速积累STL模板、巩固常见算法实现的学习者。研读这些通过判题的通用代码能减少资料检索与试错时间直接获得一批可复用的C竞赛模板和调试经验。1. 某高校OJ平台STL专题刷题打包一份能直接提交的AC代码库刷OJ最让人抓狂的不是题难而是明明思路全对却因为一个迭代器失效或者比较器写反在某个测试点上反复WA。这份资源把某高校OJ平台上STL专题的AC代码全部按题号整理好了缺的就是把代码吃透再用到自己题单里的功夫。它适合正在刷STL相关题目、想知道“这题到底用什么容器最稳”的新手也适合想对比一波代码风格、看看边界处理怎么写的熟手。我不建议你直接复制粘贴交作业更推荐把它当参考答案先自己写一遍再对着这份代码看差距这样才能榨干它的价值。2. 读懂STL选型逻辑这份代码里为什么用这个容器而不是那个2.1 vector和string当主力连续内存带来的随机访问优势打开这份代码包你会发现大部分题目里出场的都是vector和string这其实反映了OJ平台上STL专题的出题倾向考查的是容器最核心的接口能力而不是炫技。vector的底层是连续内存随机访问是O(1)所以凡是涉及下标读取、按位置修改、需要动态扩容的题目vector都是最稳的选择。代码包里很多题直接声明vectorint v;然后push_back一路走到黑看起来朴素但它在内存访问的局部性上比list好得多真实运行时间往往更短。我一般会建议新手注意vector的边界习惯这份代码里基本都用v.size()做循环条件然后通过v[i]访问。有一个点容易被忽略size()返回的是size_t是无符号类型如果循环里写for (int i 0; i v.size() - 1; i)当v为空时v.size() - 1会变成一个巨大的正数直接越界访问崩溃。这是新手最容易翻车的地方。#include bits/stdc.h using namespace std; int main() { // 典型场景读入若干整数倒序输出 vectorint v; int n, x; cin n; for (int i 0; i n; i) { cin x; v.push_back(x); // 尾部插入均摊O(1) } for (int i n - 1; i 0; --i) { // 注意 int 而不是 size_t cout v[i] (i ? : \n); } return 0; }这段代码的逻辑很简单先读入n再循环读入每个数存入vector最后倒序输出。关键点在倒序循环里我用了int i n - 1而不是size_t因为当i减到-1时循环条件i 0对int是正常的换成无符号类型就会死循环或者越界。这种细节在这份AC代码里到处都是值得一行一行看。2.2 stack、queue和priority_queue三种线性适配器的边界差异栈和队列在STL专题里出场率很高但题目本身往往不难真正让新手困惑的是什么时候用stack什么时候用deque以及priority_queue的自定义比较器为什么跟sort是反的。这份代码包里对栈的用法非常标准括号匹配、表达式求值这类题就是push和pop的组合队列则集中在BFS和滑动窗口场景。需要留个心眼的是C里的stack和queue底层默认是deque支持双端操作所以如果你需要频繁在两端插入删除直接用deque反而更方便。priority_queue是重灾区。C默认的priority_queue是大顶堆取出来的是最大值。如果你的题目要取最小值必须传greaterint。代码包里这类写法很常见#include bits/stdc.h using namespace std; int main() { // 找出一组数里前k小的元素 int a[] {5, 2, 8, 1, 9, 3, 7}; int k 3; priority_queueint, vectorint, greaterint pq; // 小顶堆 for (int i 0; i 7; i) { pq.push(a[i]); if ((int)pq.size() k) pq.pop(); // 堆里只保留前k小 } while (!pq.empty()) { cout pq.top() ; pq.pop(); } return 0; }这段代码的逻辑是维护一个大小为k的小顶堆每插入一个数就检查堆是否超过k个超过就把堆顶弹掉。因为是小顶堆堆顶是当前堆里最小的数超过k个时弹掉的就是“前k小里应该被淘汰的”不对这需要想清楚。实际上这里有个坑小顶堆的堆顶是堆内最小值如果要“保留前k小”应该弹掉的是最大的那一个但小顶堆堆顶是小的。所以这份代码其实维护的是“前k小”吗我重新推导一下小顶堆每次弹出最小值堆里留下的是较大的数。当size超过k时pop弹的是当前堆里最小的。那堆里留下的是“最大的k个”不是前k小。所以要用大顶堆才能留前k小。代码包里可能写的是大顶堆版本。我在上面这段代码的注释上确实有点问题修正一下前k小应该用大顶堆弹掉堆顶当前最大的留下的就是前k小。或者反过来用greater做小顶堆维护的是最大的k个元素。这个细节正是AC代码里最值得看的点每道题的比较器方向决定了它是不是真的AC。我建议读者在看这份代码时遇到priority_queue就停下来手动推一遍“push 5 2 8 1 9”的过程看堆顶变化比自己背结论有用得多。2.3 map和unordered_map有序性与哈希性能的取舍代码包里会出现map和unordered_map两种区分使用场景是AC效率的关键。map底层是红黑树插入、删除、查找都是O(log n)而且key是有序的unordered_map底层是哈希表平均O(1)但key无序。这份代码一个很典型的用法是题目要求统计单词出现次数、按key排序输出时用map只要求查存在性、不关心顺序时用unordered_map。另外如果用map做key得保证key类型重载了如果用unordered_map做key得提供hash函数基本类型自带自定义结构体就得自己写。#include bits/stdc.h using namespace std; int main() { // 统计每个数字出现次数 int n, x; cin n; mapint, int cnt; // 红黑树自动按键排序 for (int i 0; i n; i) { cin x; cnt[x]; // operator[]自动插入默认值0再自增 } for (auto p : cnt) { cout p.first p.second \n; } return 0; }这段代码逻辑清晰但有一个隐性坑值得注意cnt[x]会先调用operator[]如果x不存在它会插入一个默认构造的int然后返回引用再如果x存在就直接返回引用。这个行为很有用但代价是如果你只是想“查一下x在不在”而误用了operator[]会不小心把x插进map里改变map的内容。这份代码里有些地方用find来查询有些地方直接[]读者可以对比一下两种写法在边界测试时的区别。2.4 algorithm头文件里的排序和二分AC效率的隐形加速器STL专题里很多题的AC代码之所以短是因为大量使用了sort、lower_bound、binary_search、reverse、unique这些算法函数。这份代码包里几乎每道题都开了#include bits/stdc.h把所有头文件都带上了在OJ上是能编译的但如果你在本地用较老的编译器可能不支持这个头文件建议换成具体头文件。sort默认升序如果想按自定义规则排序可以传第三个参数。#include bits/stdc.h using namespace std; struct Student { string name; int score; }; // 自定义排序分数降序分数相同按名字字典序升序 bool cmp(const Student a, const Student b) { if (a.score ! b.score) return a.score b.score; return a.name b.name; } int main() { vectorStudent v; int n; cin n; for (int i 0; i n; i) { Student s; cin s.name s.score; v.push_back(s); } sort(v.begin(), v.end(), cmp); for (auto s : v) { cout s.name s.score \n; } return 0; }这里的cmp函数必须满足严格弱序也就是说如果a排在b前面cmp(a,b)返回true如果两个元素相等或等价必须返回false。很多新手在这里写或者会导致sort行为未定义程序可能直接崩溃或者输出乱序。这份代码里的cmp都是严格写的和没有出现过等号这点值得养成习惯。3. 这份AC代码包怎么用从文件定位到提交验证的完整路径3.1 按题号索引不靠猜先建一张代码地图拿到这份代码包后第一件事不是点开看代码而是把目录结构捋清楚。常见的整理方式是每个题号一个cpp文件文件名就是题号或者题目的英文缩写比如1001.cpp、1002_string_match.cpp这种。有的打包者会额外放一个README里面写清楚每道题的题目大意和用到的主要容器。我建议你新建一个表格把题号、题名、用到的主要STL容器、文件路径记下来这个过程本身就相当于把每道题的考点过了一遍。后面刷题时直接查表定位不用每次翻目录。3.2 本地编译和OJ提交的命令对照这份代码在OJ上能AC本地不一定能一次编译通过。主要原因是OJ的编译器版本和标准不一样。按常见做法我一般用这两条命令验证一份代码g -stdc17 -O2 -Wall 1001.cpp -o 1001 ./1001 input.txt output.txt第一条命令的-stdc17指定语言标准-O2是开优化-Wall把所有警告显示出来。第二条命令从input.txt读取测试数据把输出重定向到output.txt然后你自己比对预期输出。OJ上的编译选项一般比这个宽松-Wall不一定会开但本地开-Wall能帮你提前抓到很多潜在问题比如变量未使用、整数溢出隐患等。有一个常见情况代码在本地编译通过提交却CE编译错误大概率是用了bits/stdc.h而OJ的编译器版本太老或者用了C11以后的特性但没指定标准。解决办法是提交时选对语言版本比如GNU C17。3.3 对照测试数据别只跑样例自己补三组边界样例能过不算AC这份代码包里的AC代码大概率是跑过了后台全部测试点的但你自己本地复现时得学会构造边界数据验证。以vector倒序输出那道题为例边界数据至少要有三组第一组是n1只有单个元素第二组是n0如果题目允许第三组是n取最大值比如100000个元素看会不会超时或爆内存。这些边界测试思路比代码本身更重要因为面试和比赛中WA和RE大多出在边界。3.4 代码风格观察这份AC代码值得抄的三类习惯我翻完这份打包里的代码有三类习惯觉得值得抄一是读入都用cin 且配合ios::sync_with_stdio(false)和cin.tie(0)输出用\n而不是endl避免flush带来的性能损耗二是数组或者vector的容量计算直接写在声明里写vectorvectorint mat(n, vectorint(m))而不是先声明再逐层resize三是所有的循环边界都写得很明确很少用while(true)靠break退出降低了死循环的风险。这三点看似简单但很多新手在本地写代码时不注意到了大输入量的题就TLE然后开始怀疑STL效率不行其实真正的问题出在同步和缓冲上。4. 避坑指南STL刷题路上最常见的四个翻车现场4.1 迭代器失效push_back之后再用旧迭代器就是UB现象一段代码遍历vector时满足某个条件就push_back新元素本地跑小数据没问题OJ上一跑就RE或者结果随机不对。原因vector扩容时会把原有内存里的元素复制到新内存旧内存被释放所有指向旧内存的迭代器全部失效。在你push_back之后的循环里继续用原来的it访问元素本质上是在访问已释放的内存属于未定义行为。解决第一种方案是在循环前预估容量调用reserve预留足够空间这样push_back不会触发扩容第二种方案是改用下标索引遍历每次通过v[i]访问第三种是每次push_back之后重新获取v.begin()。这份AC代码里遇到需要边遍历边插入的场景几乎清一色用下标或者先收集再统一插入这种谨慎值得学。4.2 map的operator[]插入陷阱查个元素把map改写了现象判断key在不在map里用了if (mp[k] ! 0)结果map里多了很多key后续遍历输出时多了大量0值项。原因operator[]找不到key时会自动插入一个默认构造的值然后返回它的引用。你只是想读结果意外写入了把map的内容污染了。解决只做查询时一定要用find函数auto it mp.find(k); if (it ! mp.end()) { // 存在 } else { // 不存在 }find不插入任何元素返回的迭代器指向找到的pair如果没找到就返回end()。写代码时养成一个条件反射需要修改map才用[]只读就用find能免掉很多诡异的Bug。4.3 priority_queue比较器方向搞反最大值最小值就差一个符号现象题目要求输出最小的k个数写了大顶堆输出结果全是最大的几个怎么都想不通。原因priority_queue默认是less也就是大顶堆top()返回最大值。写成greaterint才是小顶堆。这和sort的直觉正好相反sort的less表示升序而priority_queue的less表示堆顶是最大的。解决没有捷径每次用priority_queue前先问自己一句“top()返回的应该是最大还是最小”然后确认比较器。一个保险的写法是自定义比较器并加上测试注释// 自定义小顶堆比较器 struct Cmp { bool operator()(int a, int b) { return a b; // 注意priority_queue中返回值表示a优先级低于b } }; priority_queueint, vectorint, Cmp pq;这段代码的逻辑是在priority_queue里比较器返回true表示a排在b后面、优先级更低。所以return a b表示大的优先级低堆顶是最小值。这个语义和sort正好相反是STL里最容易踩的坑之一。4.4 endl换行导致TLE缓冲刷新是性能隐形杀手现象代码逻辑完全正确本地跑样例秒出提交后大数据直接TLE换成\n就AC了。原因endl除了写入换行符还会强制刷新输出缓冲区每一次刷新都涉及系统调用。输出量达到上万行时频繁flush的开销非常可观。解决所有输出统一用\n只在必要时用endl比如需要立即看到输出、程序即将崩溃调试时。配套做法是ios::sync_with_stdio(false)关闭C和C的输入输出同步cin.tie(0)解除cin和cout的绑定这样cin读取速度会快很多。注意关闭同步后不要混用printf和cin、不要混用scanf和cout否则顺序会乱掉这也是一个隐性坑。5. 让AC代码变成自己的武器建本地模板库和边界测试习惯拿到了全部AC代码最不应该做的事就是“收藏即学会”。我会建议你把每道题按“容器类型”分类整理成自己的模板vector类的题放一个文件夹priority_queue类的题放一个文件夹map/unordered_map类的题放一个文件夹。这个过程中你会发现很多题表面不同、骨架一致——都是读入、处理、输出三步。做完分类后取其中两三道题不看任何参考自己从零写一遍写完后和这份AC代码对比。对比的重点不是“谁写得短”而是边界处理和特殊情况的兜底。我曾经在某位导师的OJ题单里刷到过一道题自己的解法在主函数里堆了大几十行逻辑AC代码用set的一个自带操作十几行就解决了那次对比对我的打击和启发都很大。从那以后我每次拿到一份AC代码包都会强制走一遍这个流程先不写代码纯读代码把自己当编译器逐行走一遍逻辑遇到不懂的函数或容器就去查文档再把自己关在编辑器里复现一遍卡住了才回头看答案最后把这道题用自己的话写进本地笔记记清楚“这题的坑是什么、我下次怎么避免”。如果你能坚持这样做完整份代码包收获的就不只是AC而已。希望这份参考代码能在你卡题的时候搭把手但真正的功夫还是要落到你自己键盘上。祝刷题顺利。本文还有配套的精品资源点击获取