企业官网建设流程全解析

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 与暴力数组去重的对比：数据范围决定生死

我看到很多人拿到这题，本能地想用数组+sort+unique解决。这个思路本身没错，在数据范围小、元素值域小的情况下确实可行，但它有三个隐患。

第一，值域覆盖不了。如果题目里的数组元素范围是[-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; set<int> 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); } vector<int> intersection; for (int v : a) { if (b.count(v)) { intersection.push_back(v); } } set<int> 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的时间代价几乎相同，都是沿着红黑树往下走。但是如果你用了multiset，count的含义就变成“有几个重复元素”，而find仍然只判断是否存在。所以如果你在别的问题里用了multiset，就要小心count的语义不再是0/1判断，而是一个可能大于1的整数。在那样的场景下，更推荐用find。而在set的场景里，count的写法更贴近自然语言，不容易产生误会。

遍历a而不是遍历b来求交集，这个小决策也很重要。如果a和b的元素量差别很大，应该遍历较小的集合，对每个元素去较大的集合里查找，这样总比较次数更少。虽然都是O(n log m)，但常数有差异。更稳妥的写法是先判断a.size()和b.size()，选择小的那个作为遍历对象，不过这道题没必要，因为两个set的总大小往往差不多。

3.3 并集输出时的空格处理陷阱

我写的并集部分用了set<int> 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且它不影响标准输出。

另外还有个经验：如果你自己构造测试数据，建议用随机数造大集合，比如n=m=100000，元素范围在[-5,5]之间。这样会产生大量重复元素，能测试set去重是否正常。我实测过，这种近乎极端的重复数据下，代码依然能在一瞬间跑完，并且交集、并集的输出都符合预期。你可以copy这份代码去AcWing上提交，看看结果。

4.3 扩展：如果题目要求从大到小输出怎么办

很多题目不会只考你一个固定模板，稍微变一下就要求降序输出。STL set也考虑过这个场景。你可以在定义set时传入仿函数：

set<int, greater<int>> a;

这样set内部会按从大到小排序。求交集并集的逻辑完全不用变，因为不管是升序还是降序，set都保证内部元素不重复，且迭代顺序就是排序顺序。唯一需要注意的是，当你把升序set转成降序set时，比如set<int> tmp(a.begin(), a.end());，然后如果用transparent比较器，可能涉及类型匹配问题，但最简单的办法是：如果你明确知道要降序，就在最开始定义成降序set，不要中途转来转去。

这个小的改动思路值得记下来，因为复旦机试历史上出现过类似变种。比如把数字换成字符串，要求按字典序输出集合交并，本质上用set 就能解决。你甚至可以把这道题的代码框架背下来，把int换成string，瞬间多了一种类型题的解法。这就是刷题中"一题复用"的价值。

5. 从这道题延伸出去的STL使用经验

5.1 考研机试中set的常见兄弟容器选择

我在带学生准备机试时，会专门列一张容器选择表，因为很多人并且set、multiset、unordered_set、map、unordered_map分不清。下面这张表是当年的我自己总结的，现在看起来依然好用。

从这张表可以看出，如果题目要求你维护一个可重集合，比如统计每个数字出现的次数，那你用multiset会非常自然，但要注意count的语义会变。如果要求“是否存在且需要去重”但不要求顺序，可以用unordered_set来获得更好的常数。如果要求“某个数字出现了多少次”并同时按键遍历，那用map是正解。总之，没有一个容器能覆盖所有需求，正确选择的依据永远是题目里的“序”和“重”两个关键字。

5.2 编译环境与C++版本选择的避坑指南

AcWing平台默认支持C++11、C++14、C++17，你可以放心使用范围for和auto。但有些考研机试的校内环境可能还在用老旧的C++98。在那种环境下，范围for不可用，你得把for (int v : a)改写为：

for (set<int>::iterator it = a.begin(); it != a.end(); ++it) { int v = *it; ... }

这种写法在C++11里也能跑，但是很啰嗦。我建议你在做练习时尽量用C++11以上的语法，因为这是主流，但心里要清楚怎么把它降级成C++98，以防万一。

还有一个容易踩的坑是万能头文件#include <bits/stdc++.h>。它在AcWing和很多OJ上都能用，但有一部分老旧的校内OJ根本不支持，编译器会直接报错找不到文件。稳妥的做法是写具体的头文件，像我前面代码里那样列出<iostream>、<set>、<vector>。如果你实在喜欢万能头，那就在比赛前确认一下目标环境的编译器版本，不要到了考场才发现用不了。

这道题不涉及大整数，int足够。但我要提醒一个常见后遗症：某人写集合运算题目，用int存并集大小，结果题目改成求并集的所有元素之和，如果元素值域是10^9，两个相加就可能溢出int。所以一旦出现“求和”或“计数乘法”，第一时间考虑long long。虽然这道题本身用不到，但养成习惯能让你在后续难题上少交几次学费。

5.3 一道题如何变成十道题：刷题后的复盘方法

我见过太多人刷题只追求AC，AC之后立刻下一题。结果刷了三百道，遇到稍有变形的题目还是无从下手。这道集合交并其实是一个很好的复盘样本。你可以在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这种题目，就是用来磨“稳准快”这三个字的，别因为它简单就不当回事。