C++set集合与并查集map映射，哈希表应用实例B3632 集合运算 1P1918 保龄球

集合的性质

• 无序性
• 互异性
• 确定性

B3632 集合运算 1

题面

题目背景

集合是数学中的一个概念，用通俗的话来讲就是：一大堆数在一起就构成了集合。

集合有如下的特性：

• 无序性：任一个集合中，每个元素的地位都是相同的，元素之间是无序的。

• 互异性：一个集合中，任何两个元素都认为是不相同的，即每个元素只能出现一次。

• 确定性：给定一个集合，任给一个元素，该元素或者属于或者不属于该集合，二者必居其一，不允许有模棱两可的情况出现。

元素 a 属于集合 A 记作 a∈A，反之则记作 a∈/A。

若一个集合中不存在任何元素，则称该集合为空集，记作 ∅。空集是所有集合的子集。

一个集合内的元素个数称为该集合的大小。A 集合的大小可记作 ∣A∣。

集合 C 是集合 A 与 B 的交集，当且仅当对于任何元素 a∈C，有 a∈A 且 a∈B，并且对于任何元素 b∈/C，有 b∈/A 或 b∈/B。记作 A∩B。

简单地说，交集是由所有同时属于两个集合的元素所构成的，就像两个集合相交；而并集是由所有属于其中任意一个集合的元素所构成的，就像两个集合合并。

特别地，对于形如 {x∣a≤x≤b} 的集合，可以记作 [a,b]。其中，如果左侧符号改为小于号，则左侧中括号改为小括号。右侧同理。

题目描述

现在给予两个集合 A 和 B，均由 00 到 6363 之间的整数组成。

请依次求出：

• ∣A∣
• A∩B
• A∪B

输入格式

输入四行。

第一行一个整数 x(0≤x≤63)，表示集合 A 的元素个数。

第二行 x 个整数 a1​,...ax​，表示集合 A 的各个元素，保证不重复。如果 A 是空集，则这一行没有数字。

第三行一个整数  y(0≤y≤63)，表示集合 B 的元素个数。

第四行 y 个整数 b1​,...bx​，表示集合 B 的各个元素，保证不重复。如果 B 是空集，则这一行没有数字。

输出格式

输出三行。

第一行输出一个整数，表示 ∣A∣。

第二行输出若干个整数，表示 A∩B 中对应元素，从小到大输出，用空格隔开。如果是空集，则这一行什么也不输出，保留换行。

第三行输出若干个整数，表示 A∪B 中对应元素，从小到大输出，用空格隔开。如果是空集，则这一行什么也不输出，保留换行。

输入输出样例

输入 #1

4
1 3 5 8
3
3 6 8

输出 #1

4
3 8
1 3 5 6 8

输入 #2

04
1 2 3 4

输出 #2

01 2 3 4

题解

使用set的方法有很多种，根据这道题目的要求可以做出以下输出

循环，如果读到了一个数，就将 a 数组对应的元素标记为 1

循环，如果读到了一个数，就将 b 数组对应的元素标记为 1

循环，i 从 0 到 63，输出 A 和 B 的交集

如果 i 同时在集合 A 和 B 中，说明它是 A∩B 的元素。

循环，i 从 0 到 63，输出 A 和 B 的并集

如果 i 在集合 A 或 B 至少一个集合，说明它是 A∪B 的元素。

代码

#include<iostream>
using namespace std;
int a[65], b[65], x, y, tmp;
int main() {// 读入 xcin >> x;for (int i = 0; i < x; i++) {cin >> tmp;a[tmp] = 1; // 将集合 A 对应的元素标记为 1}int sizeA = 0; // 集合 A 的大小// 循环，i 从 0 到 64，计算集合 A 的大小for (int i = 0; i < 65; i++) {if (a[i] == 1) {sizeA++;}}cout<<sizeA<<endl;// 读入 ycin >> y;for (int i = 0; i < y; i++) {cin >> tmp;b[tmp] = 1; // 将集合 B 对应的元素标记为 1}// 循环，i 从 0 到 63，输出 A 和 B 的交集for (int i = 0; i < 63; i++) {if (a[i] == 1 && b[i] == 1) {cout << i << " "; // 输出交集元素}}cout << endl;// 循环，i 从 0 到 63，输出 A 和 B 的并集for (int i = 0; i < 63; i++) {if (a[i] == 1 || b[i] == 1) {cout << i << " "; // 输出并集元素}}return 0;
}