集合覆盖问题

Published: by Creative Commons Licence

  • Tags:

网格行唯一性

题目1:给定一个$n$行$m$列的网格,每个网格存在一个数字。现在要求回答$q$个询问,第$i$个询问要求仅考虑若干列(去除不被考虑的列),将每一行看成一个数值序列,问有多少个序列是唯一的。其中$1\leq n\leq 60$,$1\leq m\leq 20$,网格中数值绝对值不超过$10^9$。

提供一道问题

首先我们可以用哈希+哈希表来做,但是很复杂且常数很大。

我们可以暴力枚举每一行,考虑它在哪些情况下产生贡献。很显然它只在某些列集使得它唯一的前提下产生贡献。

考虑什么时候会唯一。我们维护一个序列$b_1,\ldots,b_m$,其中$b_i$表示哪些行在第$i$个字符与我们第一行不同,我们可以用二进制表示集合。之后我们考虑它什么时候唯一,很显然如果列集为$C_1,\ldots,C_k$的时候,它仅在$\left\{2,3,\ldots,n\right\}\subseteq b_{C_1}\lor b_{C_2}\lor \ldots \lor b_{C_k}$的时候会产生一贡献。我们可以通过位压找到所有会使得第一行唯一的列集。时间复杂度为$O(2^m)$。

由于我们会暴力枚举每一行来考虑它的贡献,因此总的时间复杂度为$O(n2^m)$。

题目2:给定一个$n$行$m$列的网格,每个网格存在一个数字。现在要求找出最小的一个列集,在仅考虑这些列的时候,每一行都不同。其中$1\leq n\leq 6$,$1\leq m\leq 100$,网格中数值绝对值不超过$10^9$。

提供一道题目

这道题实际上可以用题目1的方式做,但是这里$m$太大了,所以一定会TLE。

我们可以搞$n\choose 2$个条件集合,记$f(i,j)$表示$i$与$j$行在哪些列下不同,我们可以用状压来记录。

接下来相当于我们有$n$个条件,我们希望找到一个最小的列集,使得列集与每个条件的交集都不空。

我们可以记$dp(i,j)$表示仅考虑前$i$列,已经满足了的条件的集合为$j$,最少使用的列数。很显然状态之间的转移时$O(1)$的,因此总的时间复杂度为$O(m2^{n\choose 2})$。

最小集合覆盖问题

最小集合覆盖是指给定一个包含$n$个元素的全集$S$,以及$m$个$S$的子集$A_1,\ldots,A_m$,且它们的并集为$S$。要求从其中选择数目最少的子集,记作$B_1,\ldots,B_k$,满足$\bigcup_{i=1}^kB_i=S$。

最小集合覆盖是NP完全问题,因此不需要考虑多项式时间的解法。

题目1:给定$S=\left\{1,2,\ldots,n\right\}$,以及$S$的$m$个子集$A_1,\ldots,A_m$,保证它们的并集为$S$。之后要求找到最小的集合覆盖。其中$1\leq n\leq \sum_{i=1}^m |A_i|\leq 10^6$,$1\leq m\leq 20$。

提供一道题目

首先对$x\in S$,我们记$f(x)$表示有哪些子集包含$x$,这里我们用二进制来表示。可以发现一个子集族$t$满足条件,当且仅当$\forall x\in S(t\cap f(x)\neq \varnothing)$。

要找最小的子集族$t$比较麻烦,但是我们可以逆向思维,要找最小的$t$,等价于找最大的集合$v$,满足$\forall x\in S(f(x)\not \subseteq v)$。此时$t=\left\{1,2,\ldots,m\right\}-v$。

新的问题很好解决,记$g(i)$表示有多少$f(x)$等于$i$,如果$g(i)=0$,那么$i$就可以作为$v$的候选,我们在所有候选中选择最大的那个就可以了。

这里我们可以用FWT来计算$g$,时间复杂度为$O(n+\sum_{i=1}^m |A_i|+m2^m)$。

题目2:给定$S=\left\{1,2,\ldots,n\right\}$,以及$S$的$m$个子集$A_1,\ldots,A_m$,保证它们的并集为$S$。之后要求找到最小的集合覆盖。其中$1\leq \sum_{i=1}^m |A_i|\leq 10^6$,$1\leq n\leq 10$,$1\leq m\leq 10^5$。

这题类似题目1,只不过$n$很小,$m$很大。我们可以记$dp(i,j)$表示仅考虑前$i$个子集,其并集为$j$最少需要合并多少个子集。其计算量仅为$O(m2^n)$。