题意:给你\(m\)个长度为\(n\)的二进制数,求最少选多少个使它们\(|\)运算后所有位置均为\(1\),如果不满足条件,则输出\(-1\).

题解:这题\(n\)的范围很大,所以我们先用\(string\)读,然后再转化为\(bitset\),之后再直接dfs爆搜,对于满足条件的维护一个最小值即可.

代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
#include <map>
#include <set>
#include <bitset>
#include <unordered_set>
#include <unordered_map>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define me memset
const int N = 1e6 + 10;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
using namespace std;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;

int t;
int n,m;
string s;
int ans=INF;
bitset<600> a[N];

void dfs(int x,bitset<600> now,int cnt){
    if(now.count()==n){
        ans=min(ans,cnt);
        return;
    }
    for(int i=x;i<m;++i){
        bitset<600> tnow=now|a[i+1];
        dfs(i+1,tnow,cnt+1);
    }
    return;
}

int main() {
    ios::sync_with_stdio(false);cin.tie(0);
    cin>>t;
     while(t--){
        cin>>n>>m;
        for(int i=1;i<=m;++i){
            cin>>s;
            a[i]=bitset<600>(s);
        }
        ans=INF;
        bitset<600> now(0);
        dfs(0,0,0);
        if(ans==INF) ans=-1;
        cout<<ans<<endl;
     }
return 0;
}