CF1395C Boboniu and Bit Operations

Boboniu and Bit Operations

题目大意：有两个非负整数序列$a_1,a_2...a_n$，$b_1,b_2...b_m$，对于每个$i(1\le i\le n)$,你可以选择一个$j(1\le j\le m)$,并使得$c_i=a_i\&b_j$ 求出$c_1|c_2|...|c_n$的最小值
$(0\le a_i,b_i\lt 2^9,1\le n,m\le200)$

思路：首先观察一下数据范围$a_i,b_i\lt 2^9$,或运算之后最终结果肯定也小于512，并且$1\le n,m\le200$，那我们可以直接暴力枚举$0\le ans\le 512$，那么在枚举每个$ans$的情况下，只要满足$a_i\&b_j|ans=ans$，对于每个$a_i$都找到一个$b_j$符合即可，有一个$a_i$不符合就不成立，枚举下一个$ans$...直到找到第一个满足的$ans$即为答案

Code:

#include <bits/stdc++.h>
using namespace std;
const int N=250,mod=1e9+7;
typedef long long ll;

int n,m,a[N],b[N];
bool check(int x){
	for(int i=1;i<=n;i++){
		bool flag=true;
		for(int j=1;j<=m;j++){
			if(((a[i]&b[j])|x)==x){
				flag=false;
				break;
			} 
		}
		if(flag) return false;
	}
	return true;
}

int main(){

	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=m;i++) cin>>b[i];
	for(int i=0;i<=512;i++){
		if(check(i)){
			cout<<i<<endl;
			break;
		}
	}
	return 0;
}