妙啊!

什么是二进制枚举子集

我们手上有n个可以选取的元素,我们要选择其中m个,那么每一个元素都有选或不选2种可能,正好对应着二进制中的0或者1
来看例子
1 2 3 4 5 五个元素
假如我们都不选
0 0 0 0 0 对应到10进制=0
我们只选4
0 0 0 1 0 对应到10进制=2
我们选2,5
0 1 0 0 1 对应到10进制=9
我们都选
1 1 1 1 1 对应到10进制=$2^5-1$=31
于是我们发现当有n个元素的时候,一共有$2^n$种方案,可以使用十进制下的0到$2^n-1$来表示
所以枚举子集的时候可以从0枚举到$2^n-1$

枚举时的常见操作

首先是集合之间的关系

  • 包含与不包含

假如说集合a包含集合b
那么集合b的所有元素在集合a中都有出现
那么集合ab的交集就是集合b,集合ab的并集就是集合a
如果同时满足这两个关系,那么集合a就包含集合b,集合b是a的子集
否则集合a不包含集合b
其次就是集合与集合的运算

  • 并集

只要两个集合中有一个含有,那么就在他们的并集里
我们可以使用位运算符|
只要有任意一项为真,就0返回真

  • 交集

只要两个集合中都含有,那么就在他们的交集里
所以位运算符&
必须两个都是真,才返回真

  • 补集

全集中不包含在这个集合的元素就在这个集合的补集中
有一个位运算符叫做异或^
只有两个不同才返回真,否则返回假
那么我们用全集^这个集合
由于全集都是1
所得出来的就是这个集合没有的也就是0的
其实就是一些简单的位运算啦

update

发现一个比较有意思的:字典序枚举子集
发现按照老代码写出来
并不是字典序
但是我们发现,如果把这个序列倒过来(指每一串
那么就是一个字典序了
所以我们可以想到可以通过倒序来进行枚举
然后用1来表示0,0来表示1
完结。

Last modification:April 12th, 2020 at 07:37 am
如果觉得我的文章对你有用,请随意赞赏