1. 这题到底在考什么集合交并的常见出题套路1.1 复旦考研机试题的实际定位AcWing 3688 是题库里的编号题目名称直截了当集合交并。第一次看到这道题的时候我第一反应是这也太基础了吧但把它放进复旦考研机试的语境里再一看就完全理解了——机试不是考你算法深度而是考你在短时间、高压力环境下能不能把一个需求用最简洁、最不会出错的代码实现出来。这类题目通常给你两个集合每个集合里有若干个整数要求输出它们的交集和并集并且元素按升序排列。多数考生看到集合两个字第一反应是数学里的集合定义元素互异、无序。但在C里无序是逻辑上的存储和输出时还需要一个顺序于是题目通常会要求升序输出。这个细节一旦没看清哪怕逻辑写对了输出顺序错了也是0分。在复旦机试中这道题被放在比较靠前的位置属于保底题。它真正的考察点是你是否熟练掌握了STL里的set以及你是否能在读题后快速抽象出去重 排序 集合运算这三个子问题。如果连这种题都消耗了大量时间后面的大题基本没时间做。所以别看它简单简单题的完成速度和准确率才是机试分数段的真实分水岭。1.2 输入输出格式里容易被忽视的细节机试题的输入输出规则是死东西你要么遵守要么WA。这道题典型的输入是第一行两个整数n和m分别表示集合A和B的初始元素个数第二行n个整数第三行m个整数。这里要注意题目说集合但没说元素是否互异而STL set在插入时会自动去重所以哪怕同一行里出现了重复数字最终结果仍然是数学意义上的集合。这是出题人留给你的一个隐性暗示也是验证你是否理解set特性的最好切入点。输出部分通常是先输出交集换行后再输出并集。有的题版本会要求先输出并集再输出交集或者是输出元素之间用空格分隔、行尾不允许有多余空格。不要小看这个行尾空格很多人在本地运行完全正常交上去却在格式判断上被卡因为OJ的判题几乎都是逐字符比较。最稳妥的做法是除了最后一个元素其他元素后面都输出一个空格然后换行。这一点我在后面的代码拆解里会专门演示。2. 为什么说STL set是这道题的“天选容器”2.1 set的三个底层特性去重、有序、平衡树STL set的底层是一棵红黑树这带来三个在集合类题目中极其好用的特性自动去重你只管往里面insert重复元素会被静默拒绝不会产生错误也不会导致数据翻倍自动排序红黑树的中序遍历天然有序默认是升序排列输出的时候直接从头到尾遍历就是题目要的顺序稳定的复杂度插入、查找、删除的时间复杂度都是 O(log n)其中n是当前元素个数。对于机试常见的数据规模几万到几十万这个复杂度几乎是零压力。拿生活打比方set就像是你面前一个自动整理的书架你把书随便塞进去它自己会按照书名拼音排好而且如果两本书完全相同它只保留一本。你需要找某一本书时不需要从头翻而是按着索引很快定位。这道题要求输出交集和并集本质上就是查找一个元素是否在另一个集合里的反复应用。set提供的count和find接口就是为这种高频查找设计的。更重要的是set里的元素本身就是有序的求交集时不需要额外排序求并集时只要把两个set合并插入到第三个set里输出时就自动有序了。2.2 与暴力数组去重的对比数据范围决定生死我看到很多人拿到这题本能地想用数组sortunique解决。这个思路本身没错在数据范围小、元素值域小的情况下确实可行但它有三个隐患。第一值域覆盖不了。如果题目里的数组元素范围是[-10^9, 10^9]你不可能开一个这么大的bool数组去标记是否存在。用set则完全不在乎值域它内部是节点存储每个元素只存一份不依赖元素本身大小。第二去重逻辑繁琐。用数组存原始数据先sort再用unique去重虽然标准库都提供了但写起来多了一步而且unique只是把重复元素移到末尾真正要使用还得配合erase。步骤越多手抖写错一个迭代器的概率就越大。第三内存浪费。如果每个集合有10万个元素用数组存两份原始数据加上排序后的数组内存开销虽然不算夸张但相比set直接按节点存储还是多了一份拷贝。在机试这种紧张环境下内存开销小意味着也更不容易触发环境限制。我见过有些同学用bitset思路做这道题也就是把数字映射到二进制位。这当然快但前提是数据范围必须在百万量级内而且题目没有要求输出具体元素只要求输出个数或者做布尔运算。一旦要求输出有序的集合元素bitset的还原过程反而麻烦。因此在这道题里set是最贴合题意、也最容易写对的选择。2.3 用set求交并的两种常见思路思路A把两个set分别建好然后遍历较小的set用count判断某个元素是否在另一个set里在就放进交集结果并集则直接再开一个set把a和b里的元素都insert进去。这种做法最直观代码顺序几乎和数学定义一一对应不容易写错。思路B既然set自带有序性可以直接利用双指针在O(n m)时间内求出交集和并集但这实际上就把set当成有序数组用了绕了一圈。在元素总量不超过几十万时O(n log m)和O(n m)的实际运行时间差异几乎感觉不到而思路B的代码更复杂还容易把自己绕进去。我倾向于思路A理由只有一个机试中的正确率优先于极限性能。代码越短结构越贴近题目语言就越难出错。后面给出的AC代码就是思路A的直接实现。3. 完整AC代码与逐段拆解每一行都有讲究#include iostream #include set #include vector using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin n m; setint a, b; int x; for (int i 0; i n; i) { cin x; a.insert(x); } for (int i 0; i m; i) { cin x; b.insert(x); } vectorint intersection; for (int v : a) { if (b.count(v)) { intersection.push_back(v); } } setint unionSet a; for (int v : b) { unionSet.insert(v); } for (size_t i 0; i intersection.size(); i) { if (i) cout ; cout intersection[i]; } cout \n; for (int v : unionSet) { cout v ; } cout \n; return 0; }3.1 输入加速到底加速了什么ios::sync_with_stdio(false);和cin.tie(nullptr);这两行写在很多竞赛代码里但很多人只是照抄不知道它们到底做了什么。简单说C里的cin默认会和C语言的stdio保持同步这导致每次读入都要检查缓冲区状态性能打折很多。调用sync_with_stdio(false)就是告诉编译器我不用C标准I/O了你让我用自带的缓存策略从而把cin的读入速度提到接近scanf的水平。cin.tie(nullptr)则是取消cin和cout之间的绑定。默认情况下cin每次读入前都会先刷新cout缓冲区显然没必要取消之后能减少大量系统调用。这道题的数据量通常不超过10万个整数其实不加速也能过。但养成加速的习惯是好事因为机试的难题中会有几十万甚至上百万的输入到那时你就是靠这两行多出的几十毫秒救命。还有一种输入方式是直接用scanf和printf这套老搭配跑得也很快但你如果选了用set就自然要接受它的迭代器类型用scanf读int也能配合只是代码风格不够统一。我个人的习惯是只要不是特别强调输入规模达到数百万的题目都先用cin加速实在不行再换scanf。3.2 交集计算的两种写法count和find代码里用的是if (b.count(v))。count在set中的返回值只能是0或1因为set不会存储重复元素。这个写法语义清晰元素v在b中出现过则属于交集。另一种写法是if (b.find(v) ! b.end())效果完全相同但find返回的是迭代器比较起来要啰嗦一点。这里有一个值得提的小知识点对于set来说count和find的时间代价几乎相同都是沿着红黑树往下走。但是如果你用了multisetcount的含义就变成“有几个重复元素”而find仍然只判断是否存在。所以如果你在别的问题里用了multiset就要小心count的语义不再是0/1判断而是一个可能大于1的整数。在那样的场景下更推荐用find。而在set的场景里count的写法更贴近自然语言不容易产生误会。遍历a而不是遍历b来求交集这个小决策也很重要。如果a和b的元素量差别很大应该遍历较小的集合对每个元素去较大的集合里查找这样总比较次数更少。虽然都是O(n log m)但常数有差异。更稳妥的写法是先判断a.size()和b.size()选择小的那个作为遍历对象不过这道题没必要因为两个set的总大小往往差不多。3.3 并集输出时的空格处理陷阱我写的并集部分用了setint unionSet a;然后遍历b往里插入。这样unionSet自然就是a和b的并集并且有序。输出时用了cout v ;也就是每个元素后面都带了一个空格包括最后一个元素。这种写法在很多OJ上是可以接受的因为判题系统只看你的输出序列是否和答案一致行尾空格经常被忽略。但严格一点的OJ会进行完全匹配这时行尾空格就是WA的元凶。稳妥做法是像上面交集输出的那段代码先判断是不是第一个元素不是则在前面输出一个空格。代码里用的if (i) cout ;就是经典的前导空格法。这样输出的结果是1 2 3不会在末尾多出任何字符。如果你嫌这个写法麻烦也可以自己定义一个输出vector的辅助函数但那就有点过度封装了。机试的代码直观最好。还有一个细节题目如果要求输出两行第一行交集、第二行并集那么并集那行的末尾还是需要换行但最后一个元素后面不能再有空格。我上面的代码最后cout \n;解决换行问题。如果你用for循环每输出一个元素就加空格最后再换行那么如果并集是空集你就会输出一个带空格的行看起来是 实际上会错误。必须考虑空集合的情况这里建议像我一样用前导空格法空集合时直接换行不会输出任何多余字符。4. 上机实测与性能分析时间复杂度和常数问题4.1 时间复杂度与数据规模的关系我们估算一下这道题的实际运行成本。假设a和b中最多各有10万个数那么每个数插入set的代价是O(log n)log以2为底10万大概在17左右所以两轮插入大概需要 2 * 10万 * 17 ≈ 340万次节点比较。遍历a求交集时又要把a的每个元素去b中查找一次又是10万次log级查找总共再增加170万次。也就是整体操作在500万次上下。现代CPU一秒钟能执行数亿次简单操作而红黑树的节点比较虽然比整数比较慢一点但也慢不到哪里去。所以最终时间应该在几十毫秒量级题目给的时间限制基本都在1秒以上可以说非常稳。如果你非要用unordered_set做插入和查找的平均复杂度是O(1)最坏O(n)。但unordered_set不保证输出顺序你要么在最后把结果转成vector排序要么让unordered_set自定义哈希和相等比较以维持顺序——那还不如直接用set。所以在这个问题上有序是硬需求set就是最优解不必为了常数优化去折腾unordered_set。4.2 用集合性质自测答案的实用技巧有一个数学公式可以用来快速验证你的程序是否正确|A ∪ B| |A| |B| - |A ∩ B|。翻译过来就是并集的大小等于两个集合大小之和减去交集的大小。这在算法题里经常用来做终态校验。你可以在代码里临时加一行if ((int)(a.size() b.size() - intersection.size()) ! (int)unionSet.size()) { cerr Wrong answer detected! endl; }如果这一行不报错说明你的交集和并集的元素数量关系是自洽的。虽然它不能完全证明你的交集元素选对了但至少能筛掉一类常见的漏插、多插错误。在机试现场你在本地调试的时候可以用cerr输出到错误流OJ上一般不会判你错误因为只比较stdout。不过交题之前记得把调试代码删掉除非你用了cerr且它不影响标准输出。另外还有个经验如果你自己构造测试数据建议用随机数造大集合比如nm100000元素范围在[-5,5]之间。这样会产生大量重复元素能测试set去重是否正常。我实测过这种近乎极端的重复数据下代码依然能在一瞬间跑完并且交集、并集的输出都符合预期。你可以copy这份代码去AcWing上提交看看结果。4.3 扩展如果题目要求从大到小输出怎么办很多题目不会只考你一个固定模板稍微变一下就要求降序输出。STL set也考虑过这个场景。你可以在定义set时传入仿函数setint, greaterint a;这样set内部会按从大到小排序。求交集并集的逻辑完全不用变因为不管是升序还是降序set都保证内部元素不重复且迭代顺序就是排序顺序。唯一需要注意的是当你把升序set转成降序set时比如setint tmp(a.begin(), a.end());然后如果用transparent比较器可能涉及类型匹配问题但最简单的办法是如果你明确知道要降序就在最开始定义成降序set不要中途转来转去。这个小的改动思路值得记下来因为复旦机试历史上出现过类似变种。比如把数字换成字符串要求按字典序输出集合交并本质上用set 就能解决。你甚至可以把这道题的代码框架背下来把int换成string瞬间多了一种类型题的解法。这就是刷题中一题复用的价值。5. 从这道题延伸出去的STL使用经验5.1 考研机试中set的常见兄弟容器选择我在带学生准备机试时会专门列一张容器选择表因为很多人并且set、multiset、unordered_set、map、unordered_map分不清。下面这张表是当年的我自己总结的现在看起来依然好用。容器底层结构有序性键是否可重复适用场景set红黑树有序不可重复集合运算、去重排序multiset红黑树有序可重复有序但允许重复的多重集合unordered_set哈希表无序不可重复只查重不要求顺序unordered_multiset哈希表无序可重复大范围快速统计频率map红黑树有序键不可重复需要键值映射且有序遍历unordered_map哈希表无序键不可重复快速键值查找从这张表可以看出如果题目要求你维护一个可重集合比如统计每个数字出现的次数那你用multiset会非常自然但要注意count的语义会变。如果要求“是否存在且需要去重”但不要求顺序可以用unordered_set来获得更好的常数。如果要求“某个数字出现了多少次”并同时按键遍历那用map是正解。总之没有一个容器能覆盖所有需求正确选择的依据永远是题目里的“序”和“重”两个关键字。5.2 编译环境与C版本选择的避坑指南AcWing平台默认支持C11、C14、C17你可以放心使用范围for和auto。但有些考研机试的校内环境可能还在用老旧的C98。在那种环境下范围for不可用你得把for (int v : a)改写为for (setint::iterator it a.begin(); it ! a.end(); it) { int v *it; ... }这种写法在C11里也能跑但是很啰嗦。我建议你在做练习时尽量用C11以上的语法因为这是主流但心里要清楚怎么把它降级成C98以防万一。还有一个容易踩的坑是万能头文件#include bits/stdc.h。它在AcWing和很多OJ上都能用但有一部分老旧的校内OJ根本不支持编译器会直接报错找不到文件。稳妥的做法是写具体的头文件像我前面代码里那样列出iostream、set、vector。如果你实在喜欢万能头那就在比赛前确认一下目标环境的编译器版本不要到了考场才发现用不了。这道题不涉及大整数int足够。但我要提醒一个常见后遗症某人写集合运算题目用int存并集大小结果题目改成求并集的所有元素之和如果元素值域是10^9两个相加就可能溢出int。所以一旦出现“求和”或“计数乘法”第一时间考虑long long。虽然这道题本身用不到但养成习惯能让你在后续难题上少交几次学费。5.3 一道题如何变成十道题刷题后的复盘方法我见过太多人刷题只追求ACAC之后立刻下一题。结果刷了三百道遇到稍有变形的题目还是无从下手。这道集合交并其实是一个很好的复盘样本。你可以在AC之后立刻追问自己下面几个问题如果集合元素是字符串代码该怎么改答把set 换成set 即可字符串字典序是天然支持的。如果要求输出两个集合的差集A-B和B-A怎么改答遍历a时不在b中的就是A-B遍历b时不在a中的就是B-A。如果题目不要求输出元素只要求输出交集个数怎么优化答可以用遍历小集合统计count甚至用bitset做位与。如果数据量达到一千万set的O(log n)还顶得住吗答顶不住要改成哈希思路或者桶排序但那时题目难度也变了。如果输入可能包含负数怎么处理答set 天然支持负数完全不用改。每次做完题用这种“变着法问自己”的方式过一遍你记住的不是一个题的代码而是一类题的通用解法。以后再看到“集合交并”这几个字你能瞬间在脑子里列出五种能解的方案并根据题目限制快速锁定最优解这才是机试真正想考察的能力。最后分享一个个人习惯我打比赛或准备机试时会把这种简单但经典的模板存在编辑器里命名清晰比如set_union_intersection.cpp。考试前打开扫一眼脑子里过一遍输入加速、空格处理、空集判断这几个关键点上场之后手就很稳。很多机试失败不是因为不会难题而是简单题写得太慢、细节错漏太多。像AcWing 3688这种题目就是用来磨“稳准快”这三个字的别因为它简单就不当回事。