在AcWing上刷考研机试题的时候这道编号3688的“集合交并”很容易被当成一道普通的数组排序题一带而过。但只要你静下心多看一眼就会发现它几乎是STL set最典型的“考点浓缩包”——题目本身不绕却稳稳地考察了容器的选择、集合概念的把握和代码速度三项基本功。复旦大学考研机试的出题风格一直是这种“短平快”路数题面越短背后越看你对STL到底熟不熟能不能在几分钟内写对、写稳、写到不回头检查。这篇文章我会从考点拆解开始把STL set的底层机制、完整代码、易错点和同类题型的应对策略一次性讲透适合正在准备考研机试、或者刚开始接触STL想系统过一遍set用法的朋友。1. 这道题到底在考什么1.1 复旦机试的风格题目越短越考基本功“集合交并”这种题目放在很多OJ上可能只是入门题但放在复旦考研机试里意义就不同了。机试的时间有限题目本身通常不会故意给你设什么数学陷阱数据范围也在合理范围内它真正想看到的是你有没有在读完题后立刻想到正确的容器能不能用最少的代码量完成最稳定的实现。如果你只会用数组硬做当然也能做出来排序、去重、双指针求交集、再开一个数组存并集。过程不复杂但代码量会膨胀中间要维护的指针和状态一多考场上就很容易出错。而用set做这道题代码量能砍掉一半以上核心逻辑只剩下“插入”和“查找”两个动作。这道题与其说是在考“集合交并”的数学定义不如说是在考“你愿不愿意信任STL让容器替你处理去重和有序”。1.2 先想想为什么会有人想用数组硬做我见过不少同学第一反应就是排序数组理由是“排序后双指针求交并的时间复杂度也不差”。确实排序是O(n log n)双指针扫描是O(n)整体复杂度并不比set方案差。但这个方案有两个隐藏成本。第一去重逻辑要自己写。输入里如果有重复元素你要决定怎么跳过去重后还要同步修改数组长度这里非常容易出现下标越界或者漏判断。第二输出并集时你还得考虑两个数组合并后的重复问题。换句话说你用数组硬做等于自己重新实现了一遍“有序集合”的维护逻辑而set把这些事情全部封装好了。机试里最简单的稳定得分方式就是让标准库替你干活而不是自己造轮子。1.3 题面背后的三个核心考察点这道题表面上简单但细分下来至少考察了三个点读题能力集合的定义是不允许重复元素的你要能意识到输入中可能出现的重复值应该被“吞掉”容器选择能力知道什么时候用set什么时候不能用vector、multiset、unordered_set复杂度预估能力知道set插入和查找都是O(log n)能根据数据规模判断这个方案是否可行。这三个能力恰好就是机试评判的一个缩影。所以这篇文章我会围绕三个问题展开set为什么适合这题、代码怎么写最稳、以及出问题时怎么快速排查。2. 先把STL set的脾气摸清楚2.1 set的底层是一棵红黑树不是哈希表很多人一听到“去重查找”就想到unordered_set但set和unordered_set本质上是两套不同的底层结构。set内部是红黑树也就是一种平衡二叉搜索树所有元素按key从小到大自动排序。插入、删除、查找都是O(log n)。红黑树听起来玄学你可以把它理解为一个会自动保持平衡的“有序书架”每次塞进去一本新书它都会自动放到正确的位置同时通过左旋右旋来保证书架不会歪掉这样查找时就能用二分的方式快速定位。之所以不用哈希表是因为哈希表的元素是无序的如果你后面要升序输出交集或并集unordered_set反而多一步排序。标题里直接点名STL set就是在暗示这一层“有序”的价值。2.2 这道题用到的几个set操作set的常用操作不多但每个都很关键我一个个说。insert(x)插入元素自动去重并排序。返回值是pairiterator, bool其中bool表示这次插入是否真的新增了元素。find(x)查找元素返回迭代器。如果没找到返回end()。count(x)在set里恒为0或1因为集合中不会存储重复元素。size()返回元素个数注意返回值是size_t类型。begin() / end()迭代器遍历的起点和终点。在这道题里find是最核心的操作。求交集的基本动作就是拿一个集合里的元素去另一个集合里find一下找到了就说明它属于交。如果输入数据中有重复元素insert会在第一轮就帮你去重所以后续的find结果完全符合数学上“集合”的定义。2.3 为什么不能选multiset或vector这是很多初学者容易混的地方。multiset同样基于红黑树但它允许重复元素存在。如果你拿multiset来存集合输入中出现的重复元素会被原样保留交集和并集的结果就会莫名其妙地变大直接WA。vector更不用说它既不自动去重也不自动排序需要你额外做一堆准备工作。我用一个表格把这几个容器的差异拉通对比一下这样每次遇到“集合类”题目的时候你可以快速对照容器是否有序是否自动去重查找复杂度适用场景set有序升序是O(log n)需要有序去重集合unordered_set无序是O(1)平均只关注存在性不关注顺序multiset有序否O(log n)需要保存重复元素vector无序否O(n)普通数组无特殊需求从这个表可以看出来当题目里出现“集合”两个字默认就要求“无序且不重复”但set把“有序列出”也一并给你了这是它在机试中最好用的一点。2.4 set的迭代器不能随机访问set的迭代器属于双向迭代器不支持it 5这种随机访问只能通过或--移动。这样的设计是因为底层红黑树节点在内存中并不是连续存放的没有“第k个元素”的概念。遍历set最稳妥的写法是for (setint::iterator it s.begin(); it ! s.end(); it) { // 使用 *it }如果你用的编译环境支持C11也可以写成for (auto x : s)输出有序非常方便。顺便说一个习惯问题遍历时写it而不是it可以避免一次不必要的临时对象构造。对于int这种类型区别不大但对于迭代器养成这个习惯没坏处。3. 读题之后先把思路设计好3.1 输入输出假设我没有完全照搬任何一个OJ版本的习惯所以先把最典型的题面版本固定下来第一行输入两个整数n和m分别表示两个集合A和B的元素个数第二行n个数第三行m个数。输出两行第一行是交集元素个数第二行是并集元素个数。如果你拿到的是“输出交集和并集两个集合”的版本我会在后面的代码部分给出对应的写法逻辑完全同构只是输出格式不同。数据范围方面考研机试常见的规模是元素个数在10^5级别最多到10^6。set的方案在10^5级别下非常轻松10^6级别也完全能跑只要不是10^7以上且对时间卡得非常狠都不需要担心。3.2 求交集遍历小集合去大集合里查求交集最朴素的想法是把A里的每个元素都拿到B里查一遍存在就统计。这个做法的时间复杂度是O(|A| log |B|)。真正到了代码层面有一个常常被忽略的小优化遍历的时候应该选size较小的那个集合去当“外循环”到另一个更大的集合里查询。这样做的理由是查找次数和遍历的集合大小成正比遍历小集合能明显减少find的调用次数。最坏情况下如果A比B小一个数量级这个优化就能省掉不少时间。int inter 0; if (A.size() B.size()) { for (setint::iterator it A.begin(); it ! A.end(); it) { if (B.find(*it) ! B.end()) inter; } } else { for (setint::iterator it B.begin(); it ! B.end(); it) { if (A.find(*it) ! A.end()) inter; } }这里用find而不是count原因只有一个find的语义是“查找并定位”count的语义是“统计出现次数”。在set里二者时间复杂度一样结果也能互相转换但find的表达更接近我们脑子里“这个元素在不在另一个集合中”这个问题代码可读性更好。3.3 求并集别真的去合并一遍用容斥求并集最简单粗暴的思路是把B的所有元素插入A然后输出A.size()。这个思路没问题但如果你手头已经有交集的大小完全用不到这个操作。数学上有一个容斥原理两个集合的并集大小等于两个集合大小之和减去交集大小。也就是说|A ∪ B| |A| |B| - |A ∩ B|所以只要算出了交集并集就是一行公式的事。这个技巧在考场上特别实用它让你少做一次完整的插入操作也避免了修改原集合可能带来的副作用。以后你碰到类似“求交并”的题目先想想有没有数学公式可以复用再决定要不要“硬算”。3.4 整体复杂度推演建set的过程把n个元素插入AO(n log n)把m个元素插入BO(m log m)。求交集遍历较小的集合假设是min(n, m)个元素每次find是O(log max(n, m))所以总复杂度是O(min(n, m) log max(n, m))。整体来看这套方案的最坏时间复杂度大约是O((n m) log max(n, m))。在10^5的数据量下log项大约是17完全不用担心超时。这也是为什么set能成为这类题目的首选复杂度足够低代码又短。4. 完整代码实现与逐行拆解4.1 版本一只输出交集和并集的大小这是最经典的版本我建议你把这版代码背到肌肉记忆因为它的结构非常稳定#include cstdio #include set using namespace std; int main() { int n, m; scanf(%d %d, n, m); setint A, B; int x; for (int i 0; i n; i) { scanf(%d, x); A.insert(x); } for (int i 0; i m; i) { scanf(%d, x); B.insert(x); } int inter 0; if (A.size() B.size()) { for (setint::iterator it A.begin(); it ! A.end(); it) { if (B.find(*it) ! B.end()) { inter; } } } else { for (setint::iterator it B.begin(); it ! B.end(); it) { if (A.find(*it) ! A.end()) { inter; } } } int uni A.size() B.size() - inter; printf(%d\n%d\n, inter, uni); return 0; }这段代码里前两个循环的唯一任务就是读入并插入。这里要注意即使题目输入中有重复元素insert的内部逻辑也会自动把重复值挡在门外。set的这个特性决定了A.size()和B.size()永远等于“去重后的集合大小”而不是输入行的元素个数。后面的交集统计我特意加了“遍历小集合”的判断。刚开始练习时哪怕你只遍历A绝大多数测试点也都能过但这是一道10^5规模的题养成遍历小集合的习惯后面遇到更大数据时你不会吃亏。4.2 版本二需要输出具体元素时怎么改有些题面不会只要个数而是要求把交集和并集两个集合的元素都打印出来通常按升序。由于set本身就是有序的所以输出部分直接遍历即可。但需要注意控制空格和换行防止输出格式出错#include cstdio #include set using namespace std; int main() { int n, m; scanf(%d %d, n, m); setint A, B; int x; for (int i 0; i n; i) { scanf(%d, x); A.insert(x); } for (int i 0; i m; i) { scanf(%d, x); B.insert(x); } // 输出交集升序 bool first true; for (setint::iterator it A.begin(); it ! A.end(); it) { if (B.find(*it) ! B.end()) { if (!first) printf( ); printf(%d, *it); first false; } } printf(\n); // 输出并集先输出A的全部再输出B中不在A中的部分 first true; for (setint::iterator it A.begin(); it ! A.end(); it) { if (!first) printf( ); printf(%d, *it); first false; } for (setint::iterator it B.begin(); it ! B.end(); it) { if (A.find(*it) A.end()) { if (!first) printf( ); printf(%d, *it); first false; } } printf(\n); return 0; }这里有个隐藏细节输出并集时我先遍历A输出所有元素再遍历B但只在元素“不属于A”的情况下输出。这正好利用了set自动去重的性质不需要额外开一个合并数组也不会重复。4.3 读入性能scanf还是cin很多人纠结要不要用cin加ios::sync_with_stdio(false)。我的建议是机试环境下直接用scanf和printf最稳。理由有两点。第一scanf/printf不需要考虑同步问题无论在哪个OJ上都表现稳定第二cin即使关了同步某些环境下的性能依然不如scanf稳定。这道题数据规模不大其实用什么都无所谓但习惯一旦养成遇到10^6数据时你就省心了。有一点必须提醒千万不要cin和scanf混用。如果你前面用了cin后面又突然用scanf二者共用同一个输入缓冲区会出各种奇怪问题。选定一套就用到底。4.4 关于int的范围的提醒集合元素的个数n、m本身不会超过int范围因为输入数量不可能达到21亿。但要注意A.size()的返回值类型是size_t也就是无符号整型。如果你直接拿它和一个负数int比较会发生类型转换问题。好在这道题不会出现负数不过如果你将来写类似代码建议统一用int接收或显式转换避免无符号数比较踩坑。5. 实战踩坑与调试心得5.1 常见错误速查表刷题踩坑是难免的我把这道题最常出现的问题整理成一张速查表你写错的时候可以直接对照现象典型原因正确做法编译报错auto不认识评测环境是C98改用set ::iterator或确认编译标准输出数量比答案大并集直接把两个集合都输出了一遍遍历B时跳过已经在A中的元素结果重复用了multiset没有自动去重换回set让insert帮你过滤结果比答案小用输入时的n和m算总数没算去重后的size用A.size()和B.size()不要用输入的n和mTLE使用了cin且没关同步或者遍历了超大集合用scanf/printf或遍历size较小的集合输出格式错行尾多空格或漏换行用first标记法控制空格结尾输出\n其中“用输入时的n和m算总数”是很多人会掉进去的坑。题面的n表示原始输入有多少个数但set会自动去重去重后的集合大小可能远小于n。如果你拿n去算并集答案一定错。记住一句话容器替你维护了去重你就别再用原始输入长度掺和计算一切以size()为准。5.2 空集的边界处理如果交集恰好为空版本一的inter就是0代码会正常输出0没问题。版本二如果交集为空循环一次都不会执行直接就输出一个空行。有些OJ对空行的处理比较严格如果你不确定可以在输出集合前判断一下或者接受题目本身对空集的约定。最好的办法还是把这些边界情况在本地预先跑一下别把第一次测试的机会留在评测机上。5.3 机试时的做题顺序和心态机试和平时刷题最大的区别是每一分钟都在“烧钱”。拿到一道简单题我个人的策略是先把输入输出格式看明白再想复杂度再选容器。像集合交并这类题只要读题时看到“集合”两个字就应该条件反射地想到set。不要浪费时间去实现排序去重更不要一上来就用哈希表然后发现输出无序又要排序。稳定得分比炫技重要得多。复旦机试一般是在Linux环境下的OJ上评测很多学校的评测机默认支持C11但为了保险我建议提交代码时明确指定编译器版本或者在本地用相近标准测试一遍。如果你的代码用了bits/stdc.h注意确认评测环境是否支持不行就老老实实写出需要的头文件我上面的示例都只包含最基础的cstdio和set在任何环境下都能编译。5.4 set插入不会让你现有的迭代器失效这一点在做其他STL容器时很容易被忽视。vector在插入元素后已有迭代器可能全部失效但set不同红黑树的插入操作只会修改节点指针不会让其他元素的迭代器失效。所以在set的遍历过程中如果你不小心做了插入操作也不会导致iterator崩溃。虽然我们不鼓励在遍历时修改容器但知道这个特性能让你在调试时不至于被“迭代器失效”问题吓到。6. 从集合交并延伸出去的同类题6.1 变形一换成字符串集合如果题目把整数换成字符串代码结构完全不变只需要把set 改成set 。要注意的是读入方式如果你想用cin读string记得关闭同步如果你坚持用scanf就要先给字符串分配足够大的char数组。判断交集、输出并集的逻辑和数字版本完全一致。字符串在set中默认按字典序排列这正好满足很多输出要求。6.2 变形二求差集和对称差差集是指属于A但不属于B的元素对称差是指恰好只属于其中一个集合的元素。逻辑上都是对“存在性判断”的组合差集遍历A如果B中不存在则输出对称差先遍历A输出不属于B的再遍历B输出不属于A的。代码只需要把版本二中的if条件改一下。这类题的核心模式都是“一个集合作为基准另一个集合作为查询表”你只要把set的find用熟练所有变形都能在几分钟内搞定。6.3 变形三自定义结构体的集合如果题目元素不是简单的int而是一个二元组比如点的坐标(x, y)你需要定义结构体并给set提供一个比较规则。set内部依赖“严格弱序”来维护红黑树结构所以你的自定义类型必须实现operator或者提供比较器。如果是pairint, intset本身就自带字典序比较直接用就好很多需要做点去重的题就会用到这种写法。举个例子如果需要维护两个整数的有序且去重的组合setpairint, int points; points.insert(make_pair(3, 4));这时候集合的元素按第一维、第二维依次比较求交集的方式和int版本一模一样。掌握了这个写法你在面对“坐标去重”“区间合并”之类的题目时也能更快联动起来。6.4 变形四大数据量场景下的进阶选择如果数据量猛增到10^7set的O(log n)可能会成为性能瓶颈。这时候你可以考虑unordered_set但要注意它没有顺序如果题目要求输出有序结果最后还要额外排序。另一种做法是先用vector把输入全部读进来排序后unique去重再通过二分查找求交集。这种方案在极端数据下更快但代码量明显更大。对考研机试来说set通常已经足够真正需要优化到unordered_set的场合并不多。我个人的建议是基础方案先用set写对如果你确实清楚性能瓶颈在哪里再针对性地换容器。不要一开始就过度设计。我在实际踩过几次坑之后最大的感受是用set做集合题最大的收获不是少写那几行代码而是你可以真正把思考重心放到“集合语义”本身上而不是一遍遍去处理去重和有序这些琐碎工作。面对机试你不需要什么奇技淫巧它考的就是你能不能在最紧张的时间里选中最合适的工具然后用最稳健的方式拿到分。这道集合交并题值得你花一下午把它吃透。