集合覆盖问题
网格行唯一性
题目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})$。
题目3：给定一个$n$行$m$列的01网格。现在网格中一些数被设置为未知数。定义网格的权重为不同的行数。现在要求替换所有未知数为01，使得网格权重最大。找到最大权重网格的任意方案。其中$1\leq n,m\leq 500$。
提供一道题目。
首先如果一行中有达到$T=\lceil \log_2 n \rceil$个未知数，那么仅该行我们可以得到至少$n$种不同的选择，即我们可以保证一定能为他选择一个和其它所有行都不同的结果，无论其它行怎么选择。因此我们可以将每一行超过$T$的多余的未知数任意赋值。
现在我们发现每一行都只有最多$T$个未知数，换言之最多$n$种可能的选项。而考虑所有行，可能的行结果有$n^2$种。
我们可以建立一个二分图，左边为每一行，右边为每一行可能的值。这样的二分图仅有$n^2$条边和$n^2$个顶点，且最大匹配不超过$n$，因此可以用很多匹配算法做到$O(n^3)$的时间复杂度求最大匹配。
这里顺带一提所有行结果比较大，我们可以用bitset来表示行，这样可以将枚举行的时间复杂度和空间复杂度优化到$O(n^2m/32)$。
最小集合覆盖问题
最小集合覆盖是指给定一个包含$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)$。