wordpress电影站模版,网页设计市场价,网站兼容哪些浏览器,wordpress qq主题下载集合枚举的意思是从一个集合中找出它的所有子集。集合中每个元素都可以被选或不选#xff0c;含有n个元素的集合总共有个子集#xff08;包括全集和空集#xff09;
例如考虑集合和它的4个子集、、、#xff0c;按照某个顺序#xff0c;把全集A中的每个元素在每个子集中的…集合枚举的意思是从一个集合中找出它的所有子集。集合中每个元素都可以被选或不选含有n个元素的集合总共有个子集包括全集和空集
例如考虑集合和它的4个子集、、、按照某个顺序把全集A中的每个元素在每个子集中的出现状况用0没出现和1出现了表示出来。
A中元素12345二进制对应十进制在A1中的出现情况1011111101a129在A2中的出现情况1001110011a225在A3中的出现情况0010000100a34在A4中的出现情况0110000110a46
通过上面的表格就可以发现A的子集A1可以表示为一个二进制数11101对应十进制变量a129反之这个数字也可以表示子集A1。注意这边的集合是大写字母集合对应的数字是小写字母。同理A2可以表示为二进制数11001。此时找到了一种让子集对应于二进制数的很直观的方法
本例一共有5个元素表示仅包含第i个元素的集合的数字可以使用位移运算构造写成1(i-1)即例如要找仅包含第3个元素的集合那么找a1(3-1)也就是4此时对应的二进制数为00100也就是集合{3}。而包含所有元素的全集可以表示成a(1n)-1空集表示为0。
一些常用的集合关系
1并集从元素选择角度来说就是A2、A3包含的元素合并起来能够得到A1。可以发现A1的每一位都等于A2 or A3的结果。变成验证可得a1a2|a3。只需要把表示两个子集的二进制数进行或运算即可得到两个子集的并集。
2交集是指两个集合中同时存在的元素组成的集合。类似前面的并集运算当需要两个子集的交集时可以把表示两个子集的二进制数进行与运算即a3a1a4。
3包含集合A2的所有元素都在A1中出现说明A1包含A2。易知A1并A2是A1同时A1交A2是A2也就是判断A1是否包含A2可以写成(a1|a2a1)(a1a2a2)
4属于是指某个元素在集合中是包含的一种特殊情况--只需检查单独某项元素构成的集合是否是另一个集合的子集。一般地可以使用户左移运算构造出那个仅含一项的集合然后再和原集合取交若不为空集则命题为真。如果要判断第3个元素是否属于A1可以写成1(3-1)a1
5补集是指全集去除了某个集合后剩下元素组成的集合。可以使用异或运算来表示集合对全集的补集例如A2对于全集的补集就是A3。A2的补集可以表示为a^a2。 注意枚举子集的时间复杂度是一般情况下1秒钟可以枚举包含20-30个元素的集合的子集。
具体的例题运用可以参照此专栏的题解。
P1036 [NOIP2002 普及组] 选数题解-CSDN博客
P1157 组合的输出题解-CSDN博客
