糖果
糖果
糖果店的老板一共有 $M$ 种口味的糖果出售。
为了方便描述，我们将 $M$ 种口味编号 $1 \sim M$。
小明希望能品尝到所有口味的糖果。
遗憾的是老板并不单独出售糖果，而是 $K$ 颗一包整包出售。
幸好糖果包装上注明了其中 $K$ 颗糖果的口味，所以小明可以在买之前就知道每包内的糖果口味。
给定 $N$ 包糖果，请你计算小明最少买几包，就可以品尝到所有口味的糖果。
输入格式
第一行包含三个整数 $N,M,K$。
接下来 $N$ 行每行 $K$ 这整数 $T1,T2, \cdots ,TK$，代表一包糖果的口味。
输出格式
一个整数表示答案。
如果小明无法品尝所有口味，输出 $?1$。
数据范围
$1 \leq N \leq 100$,
$1 \leq M,K \leq 20$,
$1 \leq T_{i} \leq M$
输入样例：
6 5 3 1 1 2 1 2 3 1 1 3 2 3 5 5 4 2 5 1 2
输出样例：
2
解题思路
这是一个重复覆盖问题，一个经典问题。与之相对的还有一个精确覆盖问题。
我们把每一种糖看成一列，一共有$1 \sim m$列，把每一包糖看成一行，一共有$1 \sim n$行。
根据样例，我们画出这个矩阵。其中如果某包糖果有重复的某种糖，我们只记一次。矩阵中的$1$代表这一包糖含有这种糖。
因此问题变成，我们至少选多少行，使得每一列都至少存在一个$1$。
这就是重复覆盖问题。精确覆盖问题就是至少选多少行，使得每列都恰好只有一个$1$。
方法是用dfs。搜索顺序是，每次找一个还未被覆盖的列，然后枚举所有可以覆盖这一列的行，每次枚举都选一行，然后递归到下层继续搜索。
直接这样搜的话会超时，所以需要进行优化。
其中一个优化是迭代加深。就是从小到大枚举答案。我们每次搜索都限制可以搜索到的行数数量。由于我们的答案是选择行数的最小值，因此从$1 \sim m$来枚举每次可以搜索到的行数数量。比如我们看看选一行可不可以覆盖所有的列，如果不可以，就看看选两行可不可以覆盖所有的列......以此类推，直到找到某个值的行数可以覆盖所有的列。
另外一个优化是，由于我们每次搜索都可以选择任意一个未被覆盖的列，那么我们应该在这些未被覆盖的列中，选择包含可选择行数最少的那一列。比如在样例中，第一次搜索应该选择搜第$4$列，因为第$4$列可选择的行数最少。这是因为这样每次都可以搜索分支少的情况，可以提高搜索的效率。
还有一个优化是可行性剪支。每次搜索时，我们都根据当前的状态（已选择的列）估计判断一下至少还需要选择多少行可以覆盖所有列。如果至少选择的行数超过还可以选择的行数，那么就return，不再继续搜下去。估计的方法是，如果某一列没有选，那么我们把所有可以覆盖这一列的行全部选上，但只算一行的数量。然而事实是加上这个剪支后运行的时间反而变久。
最后还可以对每一包糖果进行状态压缩，用二进制来表示每包糖果包含哪种糖。如果第$i$位为$1$表示这包糖含有第$i$种糖。同时每次搜索的当前状态也进行状态压缩，如果如果第$i$位为$1$表示第$i$列已经被覆盖了，$0$的话表示第$i$列还没被覆盖。
AC代码如下：
1 #include2 #include 3 #include 4 using namespace std; 5 6 const int N = 110, M = 1 << 20; 7 8 int n, m, k; 9 vector<int> col[N]; 10 int lg2[M]; 11 12 int lowbit(int x) { 13 return x & -x; 14 } 15 16 int get(int state) { 17 int ret = 0; 18 for (int i = (1 << m) - 1 - state; i; i -= lowbit(i)) { 19 ret++; // 不论选多少行，都记为一行 20 int c = lg2[lowbit(i)]; 21 22 // 更新状态，更新已选择的列 23 for (auto &it : col[c]) { 24 i &= (1 << m) - 1 - it; 25 } 26 } 27 28 return ret; 29 } 30 31 bool dfs(int dep, int state) { 32 // 可选择的行数为0，并且或者至少选择的行数超过可选择的行数，则放回当前状态是否以选择所有的列 33 if (dep == 0 || get(state) > dep) return state == (1 << m) - 1; 34 35 // 找到包含可选择行数最少的那一列 36 int c = -1; 37 38 // 这里进行按位取反，原本1表示这列以选，取反后1表示这列未选 39 for (int i = (1 << m) - 1 - state; i; i -= lowbit(i)) { 40 int t = lg2[lowbit(i)]; 41 if (c == -1 || col[c].size() > col[t].size()) c = t; 42 } 43 44 // 搜索每一个可选的行 45 for (auto &it : col[c]) { 46 if (dfs(dep - 1, state | it)) return true; 47 } 48 49 return false; 50 } 51 52 int main() { 53 scanf("%d %d %d", &n, &m, &k); 54 55 // 预处理log(2^i) 56 for (int i = 0; i < m; i++) { 57 lg2[1 << i] = i; 58 } 59 60 for (int i = 0; i < n; i++) { 61 int state = 0; 62 for (int j = 0; j < k; j++) { 63 int x; 64 scanf("%d", &x); 65 state |= 1 << x - 1; // 映射到0~m-1列，第x-1位变为1，表示这行可以覆盖第x-1列 66 } 67 68 for (int j = 0; j < m; j++) { 69 if (state >> j & 1) col[j].push_back(state); // 如果第j位为1，说明第j列可以被这一行覆盖，把这一整行放入 70 } 71 } 72 73 int dep = 1; // 迭代加深，从1开始枚举 74 while (dep <= m && !dfs(dep, 0)) { // 最多可以搜m行，超过m行说明不可以覆盖所有列。如果还没有覆盖所有列，继续搜索 75 dep++; 76 } 77 printf("%d", dep > m ? -1 : dep); 78 79 return 0; 80 }
可以把h函数去掉，运行时间会更短（至少这题是这样）。还可以把迭代加深的枚举改为二分。
AC代码如下：
1 #include2 #include 3 #include 4 using namespace std; 5 6 const int N = 110, M = 1 << 20; 7 8 int n, m, k; 9 vector<int> col[N]; 10 int lg2[M]; 11 12 int lowbit(int x) { 13 return x & -x; 14 } 15 16 bool dfs(int dep, int state) { 17 if (state == (1 << m) - 1) return true; 18 if (dep == 0) return false; 19 20 int c = -1; 21 for (int i = (1 << m) - 1 - state; i; i -= lowbit(i)) { 22 int t = lg2[lowbit(i)]; 23 if (c == -1 || col[c].size() > col[t].size()) c = t; 24 } 25 26 for (auto &it : col[c]) { 27 if (dfs(dep - 1, state | it)) return true; 28 } 29 30 return false; 31 } 32 33 int main() { 34 scanf("%d %d %d", &n, &m, &k); 35 36 for (int i = 0; i < m; i++) { 37 lg2[1 << i] = i; 38 } 39 40 for (int i = 0; i < n; i++) { 41 int state = 0; 42 for (int j = 0; j < k; j++) { 43 int x; 44 scanf("%d", &x); 45 state |= 1 << x - 1; 46 } 47 48 for (int j = 0; j < m; j++) { 49 if (state >> j & 1) col[j].push_back(state); 50 } 51 } 52 53 int left = 1, right = m + 1; 54 while (left < right) { 55 int mid = left + right >> 1; 56 if (dfs(mid, 0)) right = mid; 57 else left = mid + 1; 58 } 59 printf("%d", left > m ? -1 : left); 60 61 return 0; 62 }
另外再给出一种dfs的实现方式，这种方式的效率没有前面的效率高，但可以过。
1 #include2 #include 3 #include 4 using namespace std; 5 6 const int N = 110, M = 1 << 20; 7 8 int n, m, k; 9 vector<int> col[N]; 10 int lg2[M]; 11 int ans = N; 12 13 int lowbit(int x) { 14 return x & -x; 15 } 16 17 void dfs(int cnt, int state) { 18 if (cnt >= ans) return; // 优化剪支 19 if (state == (1 << m) - 1) { 20 ans = cnt; 21 return; 22 } 23 24 int c = -1; 25 for (int i = (1 << m) - 1 - state; i; i -= lowbit(i)) { 26 int t = lg2[lowbit(i)]; 27 if (c == -1 || col[c].size() > col[t].size()) c = t; 28 } 29 30 if (col[c].empty()) ans = -1; // 如果某列未选择，并且不存在可以覆盖这一列的行，说明不存在覆盖所有列的方案 31 for (auto &it : col[c]) { 32 dfs(cnt + 1, state | it); 33 } 34 } 35 36 int main() { 37 scanf("%d %d %d", &n, &m, &k); 38 39 for (int i = 0; i < m; i++) { 40 lg2[1 << i] = i; 41 } 42 43 for (int i = 0; i < n; i++) { 44 int state = 0; 45 for (int j = 0; j < k; j++) { 46 int x; 47 scanf("%d", &x); 48 state |= 1 << x - 1; 49 } 50 51 for (int j = 0; j < m; j++) { 52 if (state >> j & 1) col[j].push_back(state); 53 } 54 } 55 56 dfs(0, 0); 57 printf("%d", ans); 58 59 return 0; 60 }
参考资料
AcWing 1243. 糖果（蓝桥杯C++ AB组辅导课）：https://www.acwing.com/video/769/