题解(本题原题数据范围太大疑似出错，原本1e3的数据范围为np问题，现修改至20的数据范围)

题面描述

给定 $n$ 个测试用例和 $m$ 个代码模块，测试用例的覆盖情况用一个二维数组 $cases$ 表示，其中 $cases[i][j]$ 为 $1$ 表示第 $i$ 个测试用例覆盖了第 $j$ 个模块，为 $0$ 表示未覆盖。要求找出一个最小的测试用例集合，使得该集合覆盖所有模块，即所有模块至少被一个测试用例覆盖。如果不存在这样一个集合，则返回 $-1$。

思路

1. 使用位掩码表示测试用例覆盖情况
   将每个测试用例的覆盖情况转化为一个二进制数（位掩码）。其中，第 $j$ 位为 $1$ 表示该测试用例覆盖第 $j$ 个模块。这样每个测试用例可以表示为一个整数 $mask$。

2. 确定目标覆盖状态
   设所有模块都被覆盖的目标状态为 $target$，其表示为 $target = (1 << m) - 1$，即二进制中低 $m$ 位全为 $1$。

3. 暴力枚举所有测试用例的子集
   对于 $n$ 个测试用例，总共有 $2^n$ 个子集。对于每个子集，将选中的测试用例的掩码通过按位或 $|$ 合并成一个联合掩码 $union\_mask$。同时计算该子集包含的测试用例数 $cnt$。

4. 判断是否覆盖所有模块
   如果 $union\_mask$ 等于 $target$，说明该子集覆盖了所有模块。记录满足条件的测试用例个数 $cnt$ 中的最小值。

5. 返回结果
   如果存在满足条件的子集，输出最小测试用例数，否则输出 $-1$。

cpp

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int main(){
    int n, m;
    cin >> n >> m;  // n: 用例总数, m: 模块总数
    
    vector<int> tests(n, 0);
    // 将每个用例读入并转换为位掩码表示
    for (int i = 0; i < n; i++){
        int mask = 0;
        for (int j = 0; j < m; j++){
            int x;
            cin >> x;
            if(x == 1){
                mask |= (1 << j);
            }
        }
        tests[i] = mask;
    }
    
    // 目标掩码：所有模块都被覆盖
    int target = (1 << m) - 1;
    int ans = INT_MAX;
    
    // 枚举所有可能的用例集合（子集）
    for(int s = 0; s < (1 << n); s++){
        int unionMask = 0;
        int cnt = 0;
        // 对于子集中的每个用例，将其覆盖集合合并
        for(int i = 0; i < n; i++){
            if(s & (1 << i)){
                unionMask |= tests[i];
                cnt++;
            }
        }
        // 若当前子集能够覆盖所有模块，则更新答案
        if(unionMask == target){
            ans = min(ans, cnt);
        }
    }
    
    // 如果没有满足覆盖所有模块的子集，则返回-1
    cout << (ans == INT_MAX ? -1 : ans) << endl;
    
    return 0;
}

python

def main():
    import sys
    data = sys.stdin.read().strip().split()
    if not data:
        return
    # 读取测试用例总数 n 和模块总数 m
    n, m = map(int, data[:2])
    tests = []
    index = 2
    # 将每个测试用例的覆盖情况转换成位掩码表示
    for i in range(n):
        mask = 0
        for j in range(m):
            x = int(data[index])
            index += 1
            if x == 1:
                mask |= (1 << j)
        tests.append(mask)
    
    # 目标掩码：所有模块都被覆盖（低 m 位全为 1）
    target = (1 << m) - 1
    ans = float('inf')
    
    # 枚举所有可能的测试用例子集（采用二进制枚举）
    for s in range(1 << n):
        union_mask = 0
        cnt = 0
        # 对于子集中每个选中的测试用例，将其覆盖情况合并
        for i in range(n):
            if s & (1 << i):
                union_mask |= tests[i]
                cnt += 1
        # 如果当前子集能够覆盖所有模块，则更新答案
        if union_mask == target:
            ans = min(ans, cnt)
    
    # 如果没有满足条件的子集，输出 -1
    print(-1 if ans == float('inf') else ans)

if __name__ == '__main__':
    main()

java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // 读取测试用例总数 n 和模块总数 m
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[] tests = new int[n];
        
        // 将每个测试用例转换为位掩码表示
        for (int i = 0; i < n; i++) {
            int mask = 0;
            for (int j = 0; j < m; j++) {
                int x = sc.nextInt();
                if (x == 1) {
                    mask |= (1 << j);
                }
            }
            tests[i] = mask;
        }
        
        // 目标掩码：所有模块都被覆盖（低 m 位全为 1）
        int target = (1 << m) - 1;
        int ans = Integer.MAX_VALUE;
        
        // 枚举所有可能的测试用例子集（采用二进制枚举）
        for (int s = 0; s < (1 << n); s++) {
            int unionMask = 0;
            int cnt = 0;
            // 遍历子集中的每个测试用例，将其覆盖情况合并
            for (int i = 0; i < n; i++) {
                if ((s & (1 << i)) != 0) {
                    unionMask |= tests[i];
                    cnt++;
                }
            }
            // 如果当前子集能够覆盖所有模块，则更新答案
            if (unionMask == target) {
                ans = Math.min(ans, cnt);
            }
        }
        
        // 如果没有满足要求的子集，输出 -1；否则输出最小用例数
        System.out.println(ans == Integer.MAX_VALUE ? -1 : ans);
        sc.close();
    }
}

题目内容

假设我们有一系列测试用例，每个测试用例会覆盖测试若干个代码模块。

我们用一个二维数组$cases$来表示这些测试用例的覆盖情况，其中$cases[i][j]$为$1$表示第$i$个测试用例覆盖了第$j$个模块，为$0$则表示未覆盖

求一个最小的测试用例集合，使得该集合能够覆盖所有代码模块。返回最小集合的大小，如果不存在能够覆盖所有代码模块的测试用例集合，则返回$-1$

输入描述

第一行输入是两个整数，分别代表用例总数$i$和代码模块总数$j$

从第二行开始的i行,每一行有$j$个整数($0$或$1$)，每个整数之间用空格分隔；每一行代表一个用例对代码模块的覆盖情况

参数取值范围

• $cases[i].length=j$
• $cases[i][j]=0或1$
• $1<=i<=20$
• $1<=j<=20$

输出描述

覆盖所有代码模块使用的最小用例集合的大小$(int)$，如果不存在能够覆盖所有模块的测试用例集合则返回$-1$

样例1

输入

3 2
1 0
1 0
1 0

输出

-1

说明

该输入代表有$3$个测试用例，有$2$个代码模块，第一个测试用例[1,0]可以覆盖第$1$个代码模块，第$2、3$个测试用例相同。

该输入不存在用例集合可以覆盖所有的程序，所以返回$-1$。

样例2

输入

4 4
1 0 1 0
0 1 0 1
1 1 0 0
0 0 1 1

输出

2

说明

输入代表有$4$个测试用例，有$4$个代码模块，针对该输入，可以使用用例$cases[0]$和用例$cases[1]$覆盖所有模块，也可以选择使用用例$cases[2]$和用例$cases[3]$覆盖所有模块，均满足最小用例数要求，所以返回$2$。

样例3

输入

3 2
1 0
0 1
1 1

输出

1

说明

输入代表有$4$个测试用例，有$2$个代码模块，针对该输入，可以使用用例$cases[2]$即可覆盖所有模块，满足最小用例数要求，所以返回$1$。