集合
第1题 集合基本概念
1、集合与元素
集合：由一个或多个确定的元素所构成的整体，是指具有某种特定性质的具体的或抽象的对象汇总而成的集体。
元素：构成集合的这些对象则称为该集合的元素。
例如，全中国人的集合，它的元素就是每一个中国人。
例如，{1,3,5}是一个集合，3是该集合的元素。
2、空集
有一类特殊的集合，它不包含任何元素，称之为空集，记为∅。
3、全集
一般的，如果一个集合含有我们所研究问题中涉及的所有元素，那么就称这个集合为全集，通常记作U。
4、集合中元素的特性
(1)确定性
给定一个集合，任给一个元素，该元素或者属于或者不属于该集合，二者必居其一，不允许有模棱两可的情况出现。
(2)互异性
一个集合中，任何两个元素都认为是不相同的，即每个元素只能出现一次。有时需要对同一元素出现多次的情形进行刻画，可以使用多重集，其中的元素允许出现多次。
(3)无序性
一个集合中，每个元素的地位都是相同的，元素之间是无序的。集合上可以定义序关系，定义了序关系后，元素之间就可以按照序关系排序。但就集合本身的特性而言，元素之间没有必然的序。
5、元素与集合的关系
(1)属于
如果元素a在集合A中，就说a属于A，记作a∈A。例如：3∈{1,3,5}。
(2)不属于
如果元素a不在集合A中，就说a不属于A，记作a∉A。例如：2∉{1,3,5}。
6、集合间的基本关系
(1)子集与真子集
设S，T是两个集合，如果S的所有元素都属于T ，即x∈S ⇒x∈T，则称S是T的子集，记为 S⊆T（读作S含于T)。
显然，对任何集合S，都有S⊆S,∅⊆S。 其中，符号⊆读作包含于，表示该符号左边的集合中的元素全部是该符号右边集合的元素。
如果S是T的一个子集，即S⊆T ，但在T中存在一个元素x不属于S ，则称S是T的一个真子集。
空集∅是任意一个非空集合的真子集，空集是任何一个集合的子集。
(2)交集
交集由属于A且属于B的相同元素组成的集合，记作A∩B（或B∩A），读作“A交B”（或“B交A”），即A∩B={x|x∈A,且x∈B}。
例如：A={1,3,5},B={2,3,6},则A∩B = {3}。
(3)并集
并集由所有属于集合A或属于集合B的元素所组成的集合，记作A∪B（或B∪A），读作“A并B”（或“B并A”），即A∪B={x|x∈A,或x∈B}。
例如：A={1,3,5},B={2,3,6},则A∪B = {1,2,3,5,6}。
(4) 补集
补集又可分为相对补集和绝对补集。
相对补集定义：由属于A而不属于B的元素组成的集合，称为B关于A的相对补集，记作A-B或A\B，即A-B={x|x∈A，且x∉B}。
填空题
1、若A={3,2,1}, 则集合A的不同的子集有:Φ,{1},{2},,{1,2},{1,3},{2,3},{1,2,3} 。
2、若A={10,9,8,7,6,5,4,3,2,1}, 则集合A的有个不同的子集。
3、若A={1,2,3,4}，B={2,4,6,1}, 则A∩B = 【说明：为了方便测评，元素从小到大，不出现空格】
4、若A={1,2,3,4}，B={2,4,6,1}, 则AUB = 【说明：为了方便测评，元素从小到大，不出现空格】
5、若A={4,3,2,1,0}, B={3,1}, 则A-B= 【说明：为了方便测评，元素从小到大，不出现空格】
6、有A，B，C三个集合，若A⊆B，且B⊆C,则A⊆C。 【说明：填对或错】
7、若C=A∩B, D=A∪B, 则C⊆D。 【说明：填对或错】
8、若A⊆B, C=B-A, 则C⊆B。【说明：填对或错】
答案
1.{3} 2.1024 3,{1,2,4} 4.{1,2,3,4,6} 5.{0,2,4} 6.对 7.对 8.对
第2题 二进制位运算
1、按位与运算符（&）
参加运算的两个数，按二进制位进行“与”运算。
运算规则：只有两个数的二进制同时为1，结果才为1，否则为0。（负数按补码形式参加按位与运算）
即 0 & 0= 0 ，0 & 1= 0，1 & 0= 0， 1 & 1= 1。
例：3 &5 即 00000011 & 00000101 = 00000001 ，所以 3 & 5的值为1。
2、按位或运算符（|）
参加运算的两个数，按二进制位进行“或”运算。
运算规则：参加运算的两个数只要两个数中的一个为1，结果就为1。
即 0 | 0= 0 , 1 | 0= 1 ， 0 | 1= 1 , 1 | 1= 1 。
例：2 | 4 即 00000010 | 00000100 = 00000110 ，所以2 | 4的值为 6 。
3、异或运算符（^）
参加运算的两个数，按二进制位进行“异或”运算。
运算规则：参加运算的两个数，如果两个相应位为“异”（值不同），则该位结果为1，否则为0。
即 0 ^ 0=0 ， 0 ^ 1= 1 ， 1 ^ 0= 1 ， 1 ^ 1= 0 。
例： 2 ^ 4 即 00000010 ^ 00000100 =00000110 ，所以 2 ^ 4 的值为6 。
4、左移( << )
将6左移2位：6<<2
0000 0110 十进制6
0001 1000 左移2位后，低位补0，换算成十进制为24
可以发现把一个数a左移1位相当于a=a*2，把一个数b左移3位相当于b=b*2^3=b*8。
5、右移( >> )
将6右移2位：6>>2
0000 0110 十进制6
0000 0001 右移2位后，高位补0，换算成十进制为1
可以发现把一个数a右移1位相当于a=a/2，把一个数b右移3位相当于b=b/2^3=b/8。
6、非( ~ ) 非是一元操作符
操作数的每一位1变为0，0变为1
将6非运算：~6
0000 0110
1111 1001 换算成十进制为-7
填空题：
13 & 6 =
5 | 6 =
7 ^ 6 =
1<<3 =
1<<4 =
10<<2 =
15>>2 =
答案 4 7 1 8 16 40 3
第3题 集合的二进制表示（程序填空）
我们可以使用一个01串A来表示一个集合。对于数x(x≥0)，用A[x]=0表示它不在该集合中，用A[x]=1表示它在该集合中。
将01串A看作是一个二进制数，我们把它转换为十进制，就可以使用一个十进制整数来表示一个实际使用二进制方式表示的集合。
这样，我们可以使用位运算方便地处理集合的操作。
现在考虑总共有5个数构成的全集A={5,4,3,2,1}，请观察它们的一一对应关系：
|
集合 |
01二进制数 |
十进制数 |
|
{5,4,3,2,1} |
11111 |
31 |
|
{5,4,3,1} |
11101 |
29 |
|
{4,2,1} |
01011 |
11 |
有n个学生，学号1至n，学号构成的集合A={n,n-1,n-2,...3,2,1}。
由于最近流感比较严重，有一些学生请假了，于是老师开始点名。
最后只有k个学生回答报到，第i个回答报到的学生的学号是s[i]。
显然，根据上面题目的描述，可以把n个学生的考勤表看成01二进制数串，
缺席的学生对应的学号的二进制位设置为0，报到的学生对应的二进制位设置位1。
请输出考勤表二进制数串所对应的十进制数。
输入格式
第一行，两个整数:n和k。1<=k<=n<=10。
第二行，k个整数，第i个整数是s[i]，1<=s[i]<=n,且s[i]互不相同。
输出格式
一个整数。
输入/输出例子1
输入：
5 3
4 1 2
输出：
11
样例解释
有3个学生，学号是1，2，4的学生到了，说明学号是5和3的学生缺席了，
因此考勤表的01二进制串是: 01011, 这个二进制串对应的十进制数是11 。
学号是4的学生对应的二进制数是：01000
学号是1的学生对应的二进制数是：00001
学号是2的学生对应的二进制数是：00010
我们只需要把二进制数（01000） + （00001） + （00010） = 8 + 1 + 2 = 11即可。
#include<bits/stdc++.h>
using namespace std;
int n, k;
int main()
{
cin>>n>>k;
int ans = 0;
for(int i = 0; i < k; i++){
int si;
cin>>si;
int bi = 1<<( ); //学号是si的学生报到
ans = ans + bi;
}
cout<<ans<<endl;
return 0;
}
答案 si-1
第4题 集合的交和二进制的与（程序填空）
两个集合A和B的交集，即为两个集合公有元素的集合。
这等价于两个原始集合对应的二进制整数的某一位同时为1，则所求集合该位为1。
用位运算描述，集合交集实质上就是二进制与运算，即A ∩ B = A & B。
现在考虑总共有5个数构成的全集：{5,4,3,2,1}，请观察对应关系
|
集合A和B |
集合A∩B对应的二进制数 |
集合A∩B对应的十进制数 |
|
A={5,3,2,1},B={4,3,1} |
A∩B=10111&01101=00101 |
A∩B=23&13=5 |
|
A={4,3,2,1}, B={4,2} |
A∩B=1111&1010=1010 |
A∩B=15&10 = 10 |
有n个学生，学号1至n，他们的学号构成集合U={n,n-1,n-2,...2,1}。
有s个学生喜欢打篮球，第i个喜欢打篮球的学生的学号是x[i]。
有t个学生喜欢踢足球，第i个喜欢踢足球的学生的学号是y[i]。
把n个学生看成一个01二进制串，如果第i个学生同时喜欢打蓝球和踢足球，
那么学号i对应的二进制位设置位1，否则设置为0。
输出该01二进制串所对应的十进制数。
输入格式
第一行，三个整数：n,s,t。1<=n<=10, 1<=s<=n, 1<=t<=n。
第二行，s个整数，第i个整数是x[i]。
第三行，t个整数，第i个整数是y[i]。
输出格式
一个整数。
输入/输出例子1
输入：
6 3 4
5 2 4
2 5 1 6
输出：
18
样例解释
篮球对应的二进制串：011010，因为第2，4，5，共三学生喜欢打篮球，所以对应的位设置1，其余为0。
足球对应的二进制串：110011，因为第1，2，5，6，共四学生喜欢踢足球，所以对应的位设置1，其余为0。
同时喜欢打篮球和踢足球的学生的集合对应的二进制数 = 011010 & 110011 = 010010，
而二进制数010010对应的十进制数是18。
|
篮球A和足球B |
A∩B对应的二进制数 |
A∩B对应的十进制数 |
|
A={5,2,4}, B={2,5,1，6} |
A∩B=011010&110011=010010 |
A∩B=26&51=18 |
↑↓?
1
#include<bits/stdc++.h>
using namespace std;
int n, s, t;
int main()
{
cin>>n>>s>>t;
int sum1 = 0; //喜欢篮球的学生的学号构成的集合A，所对应的二进制数，的十进制数。
int sum2 = 0; //喜欢足球的学生的学号构成的集合B，所对应的二进制数，的十进制数。
for(int i = 0; i < s; i++){
int a;
cin>>a;
sum1 += (1<<(a-1));
}
for(int i = 0; i < t; i++){
int b;
cin>>b;
sum2 += (1<<(b-1));
}
int ans = ;
cout<<ans<<endl;
return 0;
}
答案 sum1&sum2
第5题 集合的并和二进制的或（程序填空）
两个集合A和B的并集，即为两个集合所有元素的集合。
这等价于两个原始集合对应的二进制整数的某一位只要有一个为1，则所求集合该位为1。
用位运算描述，并集运算实质上就是或运算，即A∪B=A|B。
现在考虑总共有5个数构成的全集：{5,4,3,2,1}，请观察对应关系
| 集合A和B | 集合A∪B对应的二进制数 | 集合A∪B对应的十进制数 |
| A={5,3,1}, B={4,3,1} | A∪B = 10101 | 01101 = 11101 | A∪B = 21 | 13 =29 |
有n个学生，学号1至n，他们的学号构成集合U={n,n-1,n-2,...2,1}。
有s个学生喜欢打篮球，第i个喜欢打篮球的学生的学号是x[i]。
有t个学生喜欢踢足球，第i个喜欢踢足球的学生的学号是y[i]。
把n个学生看成一个01二进制串，如果第i个学生喜欢打蓝球或者踢足球，
那么学号i对应的二进制位设置位1，否则设置为0。
输出该01二进制串所对应的十进制数。
输入格式
第一行，三个整数：n,s,t。1<=n<=10, 1<=s<=n, 1<=t<=n。
第二行，s个整数，第i个整数是x[i]。
第三行，t个整数，第i个整数是y[i]。
输出格式
一个整数。
输入/输出例子1
输入：
6 3 4
5 2 4
2 5 1 6
输出：
59
样例解释
篮球对应的二进制串：011010，因为第2，4，5，共三学生喜欢打篮球，所以对应的位设置1，其余为0。
足球对应的二进制串：110011，因为第1，2，5，6，共四学生喜欢踢足球，所以对应的位设置1，其余为0。
喜欢打篮球或者踢足球的学生的集合对应的二进制数 = 011010 | 110011 = 111011，
而二进制数111011对应的十进制数是59。
| 篮球A和足球B | A∪B对应的二进制数 | A∪B对应的十进制数 |
|
A={5,2,4}, B={2,5,1，6} |
A ∪ B = 011010 | 110011 = 111011 |
A ∪ B = 26 | 51 = 59 |
#include<bits/stdc++.h>
using namespace std;
int n, s, t;
int main()
{
cin>>n>>s>>t;
int sum1 = 0; //喜欢篮球的学生的学号构成的集合A，所对应的二进制数，的十进制数。
int sum2 = 0; //喜欢足球的学生的学号构成的集合B，所对应的二进制数，的十进制数。
for(int i = 0; i < s; i++){
int a;
cin>>a;
sum1 += (1<<(a-1));
}
for(int i = 0; i < t; i++){
int b;
cin>>b;
sum2 += ( );
}
int ans = ;
cout<<ans<<endl;
return 0;
}
答案
| 第1空 | 1<<(b-1) |
| 第2空 | sum1|sum2 |
第6题 判断包含关系（程序填空）
如果集合A是集合B的子集，那么集合A的每一个元素都属于集合B。
那么，集合A与集合B的交集即为集合A，而它们的并集即为集合B。
用位运算描述，若(A&B)==A，则A∈B; 若(A|B)==B，则A∈B。
在C++中，只需判断：
if( (A&B)==A ) 则集合A是集合B的子集
else 则集合A不是集合B的子集
或者在C++中判断：
if( (A|B)==B ) 则集合A是集合B的子集
else 则集合A不是集合B的子集
考虑总共有5个元素构成的全集U={5,4,3,2,1}，他们表示5个学生的学号。
若知道喜欢踢足球的学生的学号对应的二进制数写成十进制数后是10，
也知道喜欢打篮球的学生的学号对应的二进制数写成十进制数后是14，
问喜欢踢足球的学生是不是喜欢打篮球的学生的子集？
根据上面的判断方法，设a=10, b=14,
if( (a&b) == a) 则喜欢踢足球的是喜欢打篮球的子集
else 则喜欢踢足球的不是喜欢打篮球的子集
现在有n个学生，他们的学号构成全集U={n,n-1,...2,1}。
喜欢踢足球的学生，他们的学号对应的二进制数写成十进制数之后是a。
喜欢打篮球的学生，他们的学号对应的二进制数写成十进制数之后是b。
若喜欢踢足球的学生是喜欢打篮球的学生的子集，输出yes，否则输出no
输入格式
第一行，3个整数: n,a,b。 1<=n<=10, 0<=a,b<1024。
输出格式
yes或no
输入/输出例子1
输入：
5 10 14
输出：
yes
样例解释
无
答案
标签：学号,二进制,压缩,十进制,学生,集合,动态,规划,对应 From： https://www.cnblogs.com/didiao233/p/18034133