我的算法书 - 集合基础

一句话算法

集合就是“只关心元素在不在里面”的对象；做计数、去重、分类讨论时，先把方案看成集合，再考虑集合之间的关系。

问题模型

集合是若干对象组成的整体。对象叫做元素，集合通常用大写字母表示：

A,B,C,\cdots

元素通常用小写字母表示：

a,b,c,\cdots

如果 $a$ 是集合 $A$ 的元素，记作：

a\in A

如果 $a$ 不是集合 $A$ 的元素，记作：

a\notin A

常见数集：

记号	含义
$\mathbb{N}$	自然数集
$\mathbb{Z}$	整数集
$\mathbb{N_+}$	正整数集
$\mathbb{Q}$	有理数集
$\mathbb{R}$	实数集

核心直觉

集合不是队列，也不是数组。它有三个关键特性：

确定性：一个对象要么属于集合，要么不属于集合。
互异性：同一个元素在集合里只算一次。
无序性：元素的排列顺序不影响集合本身。

例如：

\{1,2,3\}=\{3,2,1\}=\{1,1,2,3\}

最后一个写法虽然重复写了 $1$ ，但作为集合时仍然只包含一个 $1$ 。

这就是集合在算法里常用于“去重”和“分类”的原因。

集合表示法

列举法

直接把元素列出来：

A=\{0,1,2,3,4,5,6,7,8,9\}

它表示小于 $10$ 的所有自然数组成的集合。

描述法

用条件描述集合：

B=\{x\in\mathbb{R}\mid x-7<3\}

读作：所有满足 $x-7<3$ 的实数 $x$ 构成的集合。

算法题中经常用描述法定义方案集合，例如：

S=\{(i,j)\mid 1\le i<j\le n,\ a_i+a_j=k\}

这表示所有下标对 $(i,j)$ ，并且它们对应的数之和等于 $k$ 。

集合关系

相等

如果两个集合包含完全相同的元素，则它们相等：

A=B

判断集合相等时，不看顺序，也不看重复写法，只看元素是否相同。

子集

如果 $A$ 中的每个元素都属于 $B$ ，则称 $A$ 是 $B$ 的子集：

A\subseteq B

也可以写作：

B\supseteq A

直觉上， $A$ 被完整地包含在 $B$ 里。

真子集

如果 $A\subseteq B$ ，并且 $A\ne B$ ，则称 $A$ 是 $B$ 的真子集：

A\subset B

等价地说：

A\subseteq B,\quad \exists x\in B,\ x\notin A

也就是 $B$ 至少比 $A$ 多一个元素。

空集

没有任何元素的集合叫空集：

\varnothing

空集是任意集合的子集：

\varnothing\subseteq A

集合大小

集合 $A$ 中元素的个数记作：

|A|

在算法计数题中，很多问题的答案本质上就是某个集合的大小。

集合操作

设 $A$ 、 $B$ 是全集 $U$ 的两个子集。

并集

属于 $A$ 或属于 $B$ 的元素组成的集合：

A\cup B=\{x\mid x\in A\text{ or }x\in B\}

直觉：两个集合合在一起。

交集

同时属于 $A$ 和 $B$ 的元素组成的集合：

A\cap B=\{x\mid x\in A\text{ and }x\in B\}

直觉：两个集合重叠的部分。

差集

属于 $A$ 但不属于 $B$ 的元素组成的集合：

A-B=\{x\mid x\in A,\ x\notin B\}

直觉：从 $A$ 里删掉属于 $B$ 的部分。

补集

在全集 $U$ 中，不属于 $A$ 的元素组成的集合：

\overline{A}=U-A

也常写成：

\sim A

对称差

属于 $A$ 或 $B$ ，但不同时属于二者的元素组成的集合：

A\triangle B=(A-B)\cup(B-A)

在位运算里，它对应异或 xor 的思想：相同抵消，不同保留。

算法步骤

集合不是一个单独的竞赛算法，但它是很多算法证明和计数建模的底层语言。遇到计数、去重、分类问题时，可以按下面步骤建模：

定义全集：所有可能对象是什么。
定义目标集合：哪些对象是答案。
定义条件集合：每个限制条件对应哪个集合。
选择集合操作：是取交集、并集、差集，还是补集。
检查不重不漏：分类后的集合之间是否相交，是否覆盖全部目标。
计算大小：把问题转成求 $|S|$ 。

例如，统计满足两个条件之一的对象个数：

|A\cup B|

如果直接算 $|A|+|B|$ ，交集 $A\cap B$ 会被算两次，所以要减掉一次：

|A\cup B|=|A|+|B|-|A\cap B|

这就是容斥原理的最小模型。

算法证明

这里证明两个最常用的恒等式。

并集计数公式

要证明：

|A\cup B|=|A|+|B|-|A\cap B|

直觉模型：把 $A$ 和 $B$ 的人数相加时，站在重叠区域的人被数了两次。

属于 $A-B$ 的元素，只在 $|A|$ 中出现一次。
属于 $B-A$ 的元素，只在 $|B|$ 中出现一次。
属于 $A\cap B$ 的元素，在 $|A|$ 和 $|B|$ 中各出现一次，一共被算两次。
减去 $|A\cap B|$ 后，重叠区域每个元素只剩一次。

所以公式成立。

德摩根律

要证明：

\overline{A\cup B}=\overline{A}\cap\overline{B}

对任意元素 $x$ ：

x\in\overline{A\cup B}

等价于：

x\notin A\cup B

等价于：

x\notin A\quad\text{and}\quad x\notin B

等价于：

x\in\overline{A}\cap\overline{B}

两边包含完全相同的元素，因此集合相等。

复杂度分析

数学集合本身没有固定复杂度。落到程序实现时，复杂度取决于数据结构：

实现方式	查询元素是否存在	插入	常见用途
有序数组	$O(\log n)$	$O(n)$	静态查找、二分
`set`	$O(\log n)$	$O(\log n)$	有序集合、前驱后继
`unordered_set`	平均 $O(1)$	平均 $O(1)$	去重、存在性判断
bitset / 状态压缩	$O(1)$	$O(1)$	小全集、子集枚举

算法题里不要只说“用集合”，还要说明集合如何实现。

测试用例

设：

A=\{1,2,3,4\},\quad B=\{3,4,5\}

则：

A ∪ B = {1,2,3,4,5}
A ∩ B = {3,4}
A - B = {1,2}
B - A = {5}

并集大小公式：

|A\cup B|=4+3-2=5

和直接列举结果一致。

常见恒等式

幂等律

A\cup A=A,\quad A\cap A=A

交换律

A\cup B=B\cup A,\quad A\cap B=B\cap A

结合律

(A\cup B)\cup C=A\cup(B\cup C)

(A\cap B)\cap C=A\cap(B\cap C)

分配律

A\cup(B\cap C)=(A\cup B)\cap(A\cup C)

A\cap(B\cup C)=(A\cap B)\cup(A\cap C)

德摩根律

\overline{B\cup C}=\overline{B}\cap\overline{C}

\overline{B\cap C}=\overline{B}\cup\overline{C}

吸收律

A\cup(A\cap B)=A

A\cap(A\cup B)=A

差集转换

A-B=A\cap\overline{B}

应用分类详解

集合的本质是“用属于或不属于来描述对象”。算法题中，它最常出现在计数、去重、状态表示和证明中。

一、去重与存在性判断

典型模式： 输入很多对象，需要判断某个对象是否出现过。

识别信号： 出现“不同的”“是否存在”“重复元素只算一次”。

核心建模： 已出现对象组成集合 $S$ ，每次查询 $x\in S$ 。

二、方案集合计数

典型模式： 题目问“多少种方案”，需要避免重复和遗漏。

识别信号： 出现“方案数”“不重不漏”“顺序是否影响答案”。

核心建模： 先定义所有合法方案的集合 $S$ ，答案是 $|S|$ 。

三、容斥原理

典型模式： 统计满足至少一个条件的对象个数。

识别信号： 出现“至少满足一个”“不能被某些数整除”“多个条件并起来”。

核心建模： 把每个条件定义成集合，使用交并补计算大小。

四、状态压缩

典型模式： 元素个数很小，每个元素只有选或不选两种状态。

识别信号： $n\le 20$ 左右，出现“子集”“选若干个”“访问过哪些点”。

核心建模： 用二进制位表示集合，1 表示元素在集合中，0 表示不在集合中。

经典例题

1. 两数之和

维护已经出现过的数字集合 $S$ 。枚举当前数字 $x$ 时，只要判断 $k-x\in S$ ，就能知道是否存在一对数和为 $k$ 。

2. 不同元素个数

把所有输入元素插入集合，最后答案就是集合大小 $|S|$ 。

3. 容斥计数

统计 $1..n$ 中能被 $2$ 或 $3$ 整除的数，可以定义：

A=\{x\mid 2\mid x\},\quad B=\{x\mid 3\mid x\}

答案：

|A\cup B|=|A|+|B|-|A\cap B|

4. 状态压缩 DP

旅行商、Hamilton 路径等问题中，mask 表示已经访问过的点集。转移时本质是在集合中加入一个新元素。

参考

本书容斥原理：math/inclusion-exclusion/index.md
本书状态压缩 DP：dynamic_programming/binary_state/index.md