题意:给你\(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;
}