提示：该文章is for studying OI

集合

集合：一般地，我们把研究对象统称为元素，把一组元素组成的总体叫做集合（简称为集）。

如果a是集合A中的元素，就说a属于集合A,记作 $a \in A$ 。

如果a不是集合A中的元素，就说a不属于集合A,记作 $a \not\in A$ 。

按元素属性分类
分为数集，点集，其他集合。

例： $\{11,45,14\}$ 是数集， $\{(1,1),(4,5),(1,4)\}$ 和 $\{(x,y)|y=2x\}$ 是点集。
按元素多少分类

分为有限集和无限集。

例： $\{114,514\}是有限集，\mathbb{N}是无限集$

确定性、互异性、无序性。

确定性

对于任意一个元素，要么它属于某个指定集合，要么就不属于。

例：A = $\{11,45,14\}$ ，则 $11 \in A$ ， $114514 \not\in A$
互异性

同一个集合中的元素是互不相同的，相同的元素在一个集合中最多出现一次。

例： $\{114514,114514\}$ 的表示是错误的
无序性

集合中的元素没有先后顺序。

例： $\{114,514\}$ 和 $\{514,114\}$ 是同一个集合。

通常用大写拉丁字母A,B,C…来表示集合，用小写拉丁字母a,b,c…来表示元素。

列举法

把集合打元素一个个列举出来，用花括号 $\{\}$ 括起来。

例： $\{1,14,514\}$
描述法

把集合所含元素的共同特征表示集合。基本形式为 $\{x \in A|p(x)\}$ 。x是集合中的代表元素，集合A是集合中的取值/变化范围，p(x)是集合中元素所具有的共同特征。

例：
- 不等式 $x+114>514$ 的解： $\{x|x>400\}$
- 函数 $y=11x+4514$ 的图像： $\{(x,y)|y=2x-1\}$
图示法

常用Venn图法和数轴法表示集合。形象直观但只能辅助解题和理解。

全体非负整数组成的集合称为非负整数集（或自然数集），记作 $\mathbb{N}$ 。{0,1,2,3…}

全体正整数组成的集合称为正整数集，记作 $\mathbb{N}^{*}$ 或 $\mathbb{N}_{+}$ 。{1,2,3…}

全体整数组成的集合称为整数集，记作 $\mathbb{Z}$ 。

全体有理数组成的集合称为整数集，记作 $\mathbb{Q}$ 。

全体实数组成的集合称为整数集，记作 $\mathbb{R}$ 。

全体复数组成的集合称为整数集，记作 $\mathbb{C}$ 。

子集

如果集合A中任何一个元素都能在集合B中找到，则集合A和B中有包含关系，称集合A是集合B的子集，记作 $A \subseteq B$ （或 $B \supseteq A$ ）。
- 任何一个集合是它自身的子集，即 $A \subseteq A$ 。
- 如果 $A \subseteq B$ ， $B \subseteq C$ ，则 $A \subseteq C$ 。
真子集
如果集合A是集合B的子集，且集合B中至少存在一个元素不是集合A中的元素，则称集合A是集合B的真子集，记作 $A \nsubseteqq B$ （或 $B \supsetneqq A$ ）。
- 若 $A \subseteq B$ ， $A \not= B$ ，则 $A \nsubseteqq B$ 。
- 如果 $A \nsubseteq B$ ， $B \nsubseteq C$ ，则 $A \nsubseteq C$ 。

如果 $A \subseteq B$ ， $B \subseteq A$ ，则集合A和集合B相等，记作 $A=B$ 。

一般地，把不含任何元素的集合叫做空集，记作 $\emptyset$ 。

空集是任何集合的子集，空集是任何非空集合的真子集。

由所有属于集合A或属于集合B的元素组成的集合称为集合A与集合B的并集，记作 $A \cup B$ 。

$A \cup B = {x|x\in A或x\in B}$

例： $\{1,2,3,4\} \cup \{2,3,4,5\} = \{1,2,3,4,5\}$

并集有以下性质：

交换律： $A \cup B = B \cup A$

结合律： $A \cup (B \cup C) = (A \cup B) \cup C$

$A \cup \emptyset = A$

$A \cup A = A$

$A \subseteq (A \cup B),B \subseteq (A \cup B)$

当 $A \cup B = A$ 时， $B \subseteq A$

由属于集合A且属于集合B的所有元素组成的集合称为集合A与集合B的交集，记作 $A \cap B$ 。

$A \cap B=\{x|x\in A,且x\in B\}$

交集有以下性质：

交换律： $A \cap B = B \cap A$

结合律： $A \cap (B \cap C) = (A \cap B) \cap C$

$A \cap \emptyset = \emptyset$

$A \cap A = A$

$A \supseteq (A \cap B),B \supseteq (A \cap B)$

当 $A \cap B = A$ 时， $A \subseteq B$

如果一个集合含有所研究问题涉及的所有元素，则称这个集合为全集，记作 $U$ 。

全集 $U$ 中不属于集合 $A$ 的所有元素组成的集合称为集合A相对于全集U的补集，简称为集合 $A$ 的补集，记作 $\complement_UA$ 。

补集有以下性质：

$A \cup ( \complement_UA ) = U$

$A \cap ( \complement_UA ) = \emptyset$

$\complement_U(\complement_UA) = A$

$\complement_UU = \emptyset$

$\complement_U\emptyset = U$

$当A\subseteq B时，(\complement_UA)\supseteq(\complement_UA)$

$当A=B时，\complement_UA = \complement_UB$

$\complement_U(A \cap B) = (\complement_UA) \cup (\complement_UB)$

A与B的交集的补集是A的补集和B的补集的并集。

$\complement_U(A\cup B) = (\complement_UA) \cap (\complement_UB)$

A与B的并集的补集是A的补集和B的补集的并集。

集合在OI中的运用

STL实现集合和C++17交集和并集

在C++中，可以使用标准模板库来方便地实现集合。

#include<iostream>
#include<set>//记得引入
#include<algorithm>
#include<iterator>
using namespace std;

int main(){
    set<int> mySet;//定义集合
    mySet.insert(114514);
    mySet.insert(114514);//将114514和1919810放到集合里
    mySet.earse(114514);//将114514移出集合
    mySet.clear();//清空集合
    if(mySet.empty()/*是否为空*/)cout<<"集合是空的！";
    cout<<mySet.size();//集合元素个数
    mySet.find(1919810);//返回集合中1919810的迭代器

    set<int> mySet1,mySet2;
    mySet1.insert(11);mySet1.insert(45);mySet1.insert(14);
    mySet2.insert(14);mySet2.insert(19);mySet2.insert(810);
    
    set<int> mySet3/*并集*/,mySet4/*交集*/;
    set_union(mySet1.begin(),mySet1.end(),mySet2.begin(),mySet2.end(),inserter(mySet3,mySet3.begin()));//求出并集
    set_intersection(mySet1.begin(),mySet1.end(),mySet2.begin(),mySet2.end(),inserter(mySet4,mySet4.begin()));//求出交集
}

手动实现合集和并集

STL自带的合集和并集只有在C++17及以后有，在OI比赛时使用的是C++11标准，需要我们自己实现合集和并集。

#include<set>
#include<algorithm>
using namespace std;
typedef set<int> s;
s union_set(s a,s b){//求并集
    s mySet;
    for(s::iterator i=a.begin();i!=a.end();i++)mySet.insert(*i);
    for(s::iterator i=b.begin();i!=b.end();i++)mySet.insert(*i);
    return mySet;
}
s intersection_set(s a,s b){//求交集
    s mySet;
    if(a.size()>b.size())swap(a,b);
    for(s::iterator i=a.begin();i!=a.end();i++)
        if(b.count(*i))
            mySet.insert(*i);
    return mySet;
}

并查集

并查集用于解决一些不交集的查询和合并问题。

经典例题：P1551 亲戚

常用逻辑用语

”若p，则q“是真命题，就说由p可以推出q，记作 $p \Rightarrow q$ ，p是q的充分条件，q是p的必要条件。

”若p，则q“是假命题，就说由p不可以推出q，记作 $p \not\Rightarrow q$ ，p不是q的充分条件，q不是p的必要条件。

若 $p \Rightarrow q$ ，又 $q \Rightarrow p$ ，则p是q的充分必要条件，简称充要条件，记作 $p \Leftrightarrow q$ 。