这套2019牛客一模的编程题，我印象一直挺深。不是因为题目有多难，而是它把"集合"这个最基础的数据结构从头到尾考了一遍：有递归定义的集合，有藏在数学背景里的自然数集合，还有需要用哈希集合优化暴力的题目。当时在牛客上做完这一套，最大的感受是——真正拉开差距的不是会不会某个经典算法，而是能不能在看懂题目之后，迅速把问题翻译成"集合操作"的思路。
这篇文章不是官方题解，是我自己当年参加一模的复盘。我会把题目形态、解题思路、代码细节和踩过的坑整理出来，尤其会围绕"集合"这条主线展开。如果你正在准备春招秋招，或者想找一套有代表性的编程题检验自己的水平，这套题值得认真做一遍。看完你至少能明白：在线笔试里的集合题，考点到底藏在哪。
1. 试卷整体印象：四道题的难度阶梯和我的时间分配
1.1 题型分布与难度阶梯
2019年牛客一模的编程题，整体排布是比较典型的上阶梯结构。印象里四道题，大体可以分成三个档次。
| 题号 | 题目形态 | 核心考点 | 难度感知 |
|---|---|---|---|
| 第一题 | 签到题，字符串或基础数组操作 | 输入输出、简单模拟 | 热身级别 |
| 第二题 | 数学背景的构造题 | 数论推导、等差数列公式 | 中等偏易 |
| 第三题 | 集合定义类题目 | 递归展开、集合判重、BFS | 中等偏难 |
| 第四题 | 数据结构和算法的综合应用 | 图论或动态规划结合集合去重 | 压轴 |
这个排布非常典型：前面的题保底分，后面的题拉开区分度。不要小看第一题，在线笔试里"签到题"翻车的人每次都有，大部分原因是读题不仔细，把多组输入当成了单组输入。
1.2 我的做题顺序：先吃软柿子，再啃硬骨头
开考之后我先把四道题都扫了一遍，这种做法救了我。第二题和高斯求和有关，一看就是公式题；第三题是递归定义的集合，核心在于建模；第四题明显需要更多的思考时间。我当时定的策略是：第一题十分钟内解决，第二题二十分钟解决，第三题主攻，第四题如果有剩余时间再碰。
整套卷子做完复盘，我发现一个规律：前三题几乎都围绕"集合"这个概念展开。这就引出了一个很重要的问题——为什么一模的编程题集体指向集合？
2. 为什么一模把"集合"当成核心考点
2.1 集合在笔试题里的三种出场方式
刷题多了你会发现，集合在编程题里一般有三种出场方式。
第一种是显式考集合。题目会直接定义一个集合，让你判断某个元素是否属于它、求集合大小、求交集并集。这种题表面上在考数学定义，实际上考的是怎么把定义翻译成代码。
第二种是工具型考集合。题目本身和集合无关，但解法中必须用集合做去重或标记。比如图论里的visited数组、动态规划里的状态判重，本质都是集合思想。
第三种是语言层面考集合。这种更多出现在面试题里，比如Java面试喜欢问HashSet和TreeSet的区别、底层数据结构，C#面试会问怎么创建一个集合并保证不重复。虽然笔试不一定直接考语言API，但你在写代码时选择的集合类型会直接影响复杂度和正确性。
一模这套题，恰好把三种出场方式都覆盖了。所以做完之后你会感觉"集合"这个词无处不在，这不是巧合，是出题人刻意设计的。
2.2 "集合"考的不是API，是建模能力
很多同学看到集合题，第一反应是"我会用set，我会用HashSet，题目稳了"。但这套题告诉你：会用API远远不够。
比如"以a为基的集合Ba"那道题，题目给的是一组递归规则，你看着像数学题，但本质上要你做的，是把一句"若x属于集合，则f(x)也属于集合"翻译成一个可执行的状态扩展过程。这里思路如果没转过来，就会卡在"怎么用集合表示无限元素"这个点上。
再比如高斯自然数集合那道题，看起来是求和，实际上要你意识到"连续正整数集合"的数学结构，再用等差数列公式去优化。这里考察的是从具体例子中抽象出数学模型的能力，这和纯粹的API调用完全是两码事。
所以我把这套题的价值总结成一句话：它逼你把集合从"数据结构"升级成"思维方式"。这才是笔试真正想挑出来的能力。
2.3 在线笔试环境对集合题特别友好
还有一个容易被忽略的因素：在线笔试的判题系统对集合题很友好。因为集合操作的结果是确定的，不涉及浮点数精度、不涉及随机化、不容易产生歧义，非常适合机器判题。
这也解释了一个现象：模考卷子里集合题多，不是偶然，而是出题人为了保证题目质量、控制判题难度，会优先选择这类结果明确的题。
3. Ba集合：递归定义下的集合到底怎么建模
3.1 题目还原：你看到的定义和实际要算的东西
这道题我当时拿到手，题目大概长这样：
对于以a为基的集合Ba，定义如下： （1）a属于Ba； （2）若x属于Ba，则 x+a 和 x*a 也属于Ba； （3）Ba是满足上述条件的最小集合。 给定 a 和 n，判断 n 是否属于Ba；若属于，输出它是由多少步生成的。
第一眼看上去，集合元素是无限多的：a, 2a, a², 3a, a³……越往后膨胀得越厉害。如果没转换思路，很容易陷入"把所有元素都生成出来"的误区。
其实题目真正要你做的，是沿着规则进行状态扩展。这本质上是图的遍历：每个集合元素是一个节点，规则（1）是起点，规则（2）是边的定义，"判断n是否属于Ba"就是在问：从a出发，经过若干次"加a"或"乘a"操作，能不能走到n。
3.2 BFS展开加set判重：最稳的解法
建模思路定了之后，解法就很直接了：从a出发做BFS，每一步生成两个新状态 x+a 和 x*a，用set记录已经访问过的元素，防止重复扩展，扩展过程中如果遇到n就说明n属于集合。如果元素值超过n，就直接剪枝——因为加法和乘法都是递增操作，继续扩展只会更大，不可能回到n。
from collections import deque def can_reach(a, n): if n < a: return False if n == a: return True q = deque([a]) visited = {a} while q: x = q.popleft() for nxt in (x + a, x * a): if nxt == n: return True if nxt < n and nxt not in visited: visited.add(nxt) q.append(nxt) return False这个代码里set承担了两个职责：一是判重，防止同一条路径反复扩展；二是标记，保证算法的复杂度是O(n)级别的，而不是指数级的。
当时我写完之后自己测了几组数据，发现一个关键点：只要n能表示成 a^k 或 某个a的倍数组合的形式，算法就能找到。这让我意识到，集合定义题表面上考规则，实际考的是你有没有想到用BFS去"生成"集合。
3.3 考场上容易翻车的三个细节
第一，乘法的爆炸速度。如果n是10^9级别，x*a可能在一次扩展后就远远超过n。所以扩展时一定要先判断 nxt < n 再入队，否则队列会越积越大，直到内存撑爆。
第二，重复扩展的问题。如果不做visited标记，同一个元素会被多条路径访问到。比如 a=2 时，2+2 和 2×2 都等于4，两条路径都会生成4，第二次生成时如果没有set判重，就会重复入队，指数级膨胀。
第三，递归和BFS的选择。有些同学习惯写DFS递归，但这道题的状态空间可能是环形的——x+a 和 x*a 的结果之间可能互相到达，递归深度不可控，容易栈溢出。BFS配合显示队列更稳。
4. 高斯自然数集合：把求和公式变成解题工具
4.1 题目背景与高斯求和的迁移
看到"高斯"两个字，第一反应应该是1加到100等于5050的故事。这道题也确实用到了等差数列求和公式。
题目大概是说：高斯发现，任意一个正整数都可以拆成若干个连续正整数的和。比如 9 = 2+3+4 = 4+5，而 8 就没有任何连续正整数拆分。给定 n，求有多少种不同的拆分方式。
这里"连续正整数集合"是解题的关键。连续正整数的和从首项a开始、长度为len时，和可以写成：
sum = len × a + len × (len - 1) / 2
这个公式就是高斯求和公式的变形。推导过程很简单：len个连续整数的和是 len × a + (0 + 1 + ... + len-1)，后面的括号里正好是 len×(len-1)/2。
4.2 从暴力到数学优化：枚举长度而不是枚举起点
第一直觉是枚举起点a，然后往里加数，判断和是否等于n。但这么做复杂度是O(n²)，n一大就废了。
换个思路：枚举长度len，通过公式反推起点a是否存在。
根据上面的公式，给定len之后：
a = (n - len × (len - 1) / 2) / len
要让a是正整数，需要满足两个条件：
- n - len×(len-1)/2 必须大于0；
- 这个差值必须能被len整除。
于是我们可以写出完整的代码：
def count_ways(n): ans = 0 len_ = 2 while len_ * (len_ - 1) // 2 < n: remain = n - len_ * (len_ - 1) // 2 if remain > 0 and remain % len_ == 0: ans += 1 len_ += 1 return anslen的最大值范围也很好估算：因为a最小是1，所以 n ≥ len×(len-1)/2，也就是 len 大约在 sqrt(2n) 量级。对于10^9的n，只需要枚举到大约45000个长度，复杂度可以接受。
4.3 边界情况和输出格式的坑
这道题代码写对不难，但边界情况特别容易出错。
当 n=1 时，没有任何长度满足条件，答案是0。当 n=2 时，同样没有满足条件的长度。这个当时很多同学没注意。
还有一点，题目如果要求输出具体的拆分方案，那就不能只计数了。需要在把可行的len筛出来之后，再计算对应的首项a，然后循环输出a到a+len-1的区间。这里要注意输出格式，数字之间用空格分隔、末尾是否允许有多余空格，在线判题对空格非常敏感。
我当年在这题上犯过一个低级错误：输出答案是"0"而不是换行，导致格式错误。所以大家做题时一定要确认，输出的每个数字后面跟的是空格还是换行，最后一组数据后面要不要加换行。
5. 编程语言的集合实现细节：Python/Java/C++横向对比
5.1 Python的set：笔试中最省心的集合
用Python写集合题，体验是最好的。set自带去重、交集、并集、差集操作，写起来几乎就是数学语言，基本不用关心底层实现。
s = {1, 2, 3} t = {3, 4, 5} print(s & t) # 交集 {3} print(s | t) # 并集 {1, 2, 3, 4, 5} print(s - t) # 差集 {1, 2}需要注意的一点是frozenset。Python的set是可变的，不能作为另一个set的元素。如果你想做一个"集合的集合"，必须把内部集合转成frozenset。这个问题在做某些题目时会出现，我当时第一次碰到还愣了一会儿。
元素必须是可哈希的，这意味着list不能放进set。如果需要用list做元素，先转成tuple。这些细节平时写脚本无所谓，笔试的时候一旦踩到就是运行时错误。
5.2 Java和C++：有序集合和无序集合的选择
Java里用HashSet还是TreeSet，C++里用set还是unordered_set，底层机制完全不同。
HashSet和unordered_set底层是哈希表，查找、插入、删除平均O(1)，但元素没有顺序。TreeSet和set底层是红黑树，操作是O(log n)，但元素保持有序。
笔试中如果题目只要求判重，优先用HashSet/unordered_set，因为常数更小。但如果题目要求输出有序的集合结果，比如从小到大输出所有不重复元素，用TreeSet/set会省很多事，省去手动排序。
Java的HashSet里面存放自定义对象时，需要重写hashCode和equals方法，否则集合判重会按对象地址判断，导致两个内容相同的对象都被放进去。笔试里经常有人在这上面翻车，尤其是定义了一个坐标类Point然后想对它去重时。
5.3 "集合输出乱码"这个坑是怎么踩出来的
热词列表里有一条"集合输出是乱码"，我一看就想起来自己确实踩过这个坑，而且不止一次。
第一次是用C++写set的时候，set里存的是char*。这个坑非常隐蔽：C++的set在比较两个char*时比较的是指针地址而不是字符串内容，所以两个内容相同的字符串会被当成不同元素。更离谱的是，如果用printf直接输出set里的char*，遇到中文字符串在某些终端下就会显示乱码。
第二次是Java的System.out.println直接打印HashSet，集合里的中文对象如果没有正确设置编码，Windows控制台上就可能显示为乱码。解决方法是启动参数加-Dfile.encoding=UTF-8，或者干脆用循环逐个输出元素，不要直接println整个集合。
写到这里我想多说一句：笔试环境一般不会让你调试太久，遇到这种"看起来和算法无关"的玄学问题，最稳妥的做法是确保集合的泛型类型是字符串对象而不是字符数组，同时在本地就配置好UTF-8编码。这种细节看着小，但真的能卡掉一大半人。
6. 从模考到面试：集合考点还能怎么延伸
6.1 集合的底层实现和面试追问
一模考完之后，如果只是把题改完就扔一边，那这套题的价值就只发挥了一半。更好的做法是把"集合"这条线延伸成一套完整的面试知识点。
Java面试里关于集合的经典追问包括：HashSet的底层是怎么实现的？为什么用HashMap就能实现HashSet？TreeSet的排序和比较器是怎么回事？ConcurrentHashMap为什么不能存null键值？这些问题看起来是语言问题，其实核心还是"集合如何保证不重复、如何保证有序"这两个基础点。
我后来在准备面试时，把一模的集合题整理成一页纸的笔记：笔试里的set用来判重，面试里的Set用来考哈希原理。两者殊途同归。
6.2 多重集合排列的计数模板
热词里有一条"多重集合排列"，这个知识点也值得一提。
有时候题目会给一个包含重复元素的集合，问这些元素能构成多少种不同的排列。公式是：
n! / (cnt1! × cnt2! × ... × cntk!)
其中cnt1到cntk是每种重复元素的个数。这个公式看起来简单，但配合大数取模时，需要预处理阶乘和逆元。笔试中这种题出现的频率不低，而且经常藏在"字符串重排""字母统计"之类的外壳下面。
更好的消息是，Python的math.comb可以直接做组合数计算，配合循环就能实现多重排列计数，不需要自己写逆元。刷题时合理利用语言特性，能省下不少时间。
6.3 刷完这套题，我建议你顺手做的两件事
第一件事，把每道题的输入输出部分单独提取出来，改造成可以复用的一套模板。比如统一的读取整数、读取一行字符串、输出用空格分隔的数组等函数。在线笔试时间紧张，能少敲几行代码都是好的。
第二件事，把BFS配合set判重的代码背下来。这套模板在集合定义题、状态搜索题、迷宫题、字符串变换题里通用性极强。你只需要做的，是定义清楚状态是什么、规则是什么、terminate条件是什么，剩下的就是套模板。
聊到这儿，"集合"这条主线差不多就串完了。有些人刷题追求数量，一套一套往下刷，但迟迟不见长进。问题往往出在人没有停下来做归纳：同样是集合，递归定义的集合考的是建模，高斯自然数集合考的是数学公式和枚举优化，语言层面的集合考的是底层原理。归纳完之后你会发现，你刷的不是一道一道的题，而是一类一类的解法。
这套2019一模的题目，技巧不算高深，胜在典型。我建议你找一个完整的时间段，按笔试的标准时间把四道题过一遍，然后对照我今天写的思路重新整理自己的解法。尤其是Ba集合那题，真正能把BFS加set玩顺了，再遇到任何"按规则生成集合"的题目，你都会觉得不过如此。
