BitwiseAnd

作者：马龙 徐明宽

关键词：位运算 贪心 字典序

题目简述

给定一个正整数集合$S$与正整数$n$，你要构造出一个包含$n$个元素的新正整数集合$S'$，使其包含该给定的集合$S$为子集，每个元素均不超过$2^{60}-1$，且满足下列条件：

• 对于集合中的任意两个不同元素$A$和$B$，$A\&B > 0$；
• 对于集合中的任意三个不同元素$A$、$B$和$C$，$A\&B\&C = 0$。

其中，$\&$是二进制下的按位与运算。假如满足要求的集合不存在，输出空集；否则，假如有多个解，输出将元素排序后字典序最小的一个。

$3 \leq n \leq 50, 0 \leq |S| \leq n,S$中的元素不超过$2^{60}-1$

分析

我们首先来考虑“字典序最小”这一要求。不难发现，假如我们能最小化所有不在$S$中的元素里的最小值，其次最小化次小值，以此类推，就能得到字典序最小的方案：考虑将这个方案与另外一个比较字典序，与这一最小值相比较的数假如在$S$中，就一定会比它大；假如不在，由于它是最小值，也不会比对方更大，因此是最优的。

通过这一观察，我们发现最优策略应当是每次加入一个最小的可能的元素，重复直到集合大小为$n$。考虑加入的元素应满足什么条件。通过题目中的两个限制，我们不难发现，每个数二进制表示中的每个$1$，都不能在超过两个数字中出现，同时每两个数之间也必须存在至少一个公共位。考虑到“最小”的限制，显然让每两个数之间有且仅有一个公共位是最优的。

算法一

经过上面的分析，算法的框架已经十分清晰了。我们可以检查给定的集合$S$中的元素间是否满足要求，然后去除$S$中的元素间的所有公共位；加入新元素时，先构造该元素与$S$中每个元素间的公共位，并把对应的位在$S$中删除，然后用还未出现过的位构造新元素间的所有公共位。假如在任何一步中找不到任何满足要求的位，那么无解，否则就构造出了字典序最小的方案。

复杂度是$O(n^2*(n + 60))$。

优化

为了方便描述复杂度，记$S'$中元素的最大值的二进制位数为$w$，则有$w \leq 60$。可以发现我们至少需要$n(n-1)/2$个二进制位，所以有$n \leq 11$——换句话说，我们可以用$O(1)$的时间把$n$的规模缩小到$O(\sqrt{w})$。

我们可以花$O({|S|}^2)$的时间计算出$S$中元素间两两的公共位，并把它们或（斜体字均指位运算）起来，则存在$S$中的三个元素的与非0当且仅当在这过程中存在某次或之前两个值的与非0。

接下来，构造新元素与$S$中每个元素间的公共位时可以使用$lowbit(x) = x \& (-x)$在$O(1)$的时间内完成，构造新元素间的所有公共位也可以这样做。这部分的时间复杂度为$O((n-|S|)\cdot n)$。

最后，由于给定的$S$和新构造的元素均有序，可以在$O(n)$的时间复杂度内归并排序。

综上，总时间复杂度为$O(\min(n^2,w))$。