解题思路
此题考查对于按位或运算的理解,以及一个处理状态压缩 问题时的常用技巧,子集枚举。 根据按位或运算的性质,不难发现 当且仅当 的二进制中 的位置, 相对应的位置必须也是 , 是 的位置, 对应的位置可以为 也可以为 ,首先最直观的一个想法就是暴力枚举比 小的所有值去判断,但是这样我们会进行很多次无效的枚举,然后根据上述性质可以在枚举的过程中进行优化,接下来介绍子集枚举。
降序遍历 的所有子集的代码(不会得到 ,对于某些题目 可能也是合法的子集,需要特殊判断)
for (int i = m; i; i = (i - 1) & m)
证明为什么是降序遍历到所有子集
假设一个当前子集是 ,并且要访问下一个比 小的子集, 代表的是,将 的二进制中最右边的一个 变成 ,并且将这个 右边的所有 全部变为 (比如 的二进制是 , 的二进制是 ),为了使变成新的子集,需要将 某些位的二进制是 ,在 中相对应的位置是 的去掉(这部操作可以通过 实现),这个操作等价于切割 ,以确定算术上可以取到的最大值,即按降序排列的 之后的下一个子集。
遍历大小为 的集合的每个子集的子集
for (int i = 0; i < (1 << n); ++i)
for (int j = m; j; j = (j - 1) & i)
证明时间复杂度,n为二进制中1的个数
考虑在第 位,有三种情况:
(1)在 中为 ,那么在子集 中也为 。
(2)在 中为 ,在子集 中也为 。
(3)在 中为 ,但是在子集中为 。
总共有 位,因此有种组合。