【CF1395C】Boboniu and Bit Operations(贪心、位运算)

发布时间 2023-08-31 13:20:00作者: Alric

题目大意:

数组\(a\)长度为\(n\),数组\(b\)长度为\(m\),构造数组\(c\)满足\(c[i]=a[i]\&b[j]\),求数组\(c\)按位或的和的最小值。


设题目的答案为\(ans\)

由于数组\(a\)\(b\)的元素值小于\(2^{9}\),所以数组\(c\)元素和\(ans\)在二进制表示下最多为\(9\)位。

我们考虑使\(ans\)的第\(9\)位(最高位)最小,然后使第\(8\)位最小,接着使第\(7\)位最小,依次类推。

若要使\(ans\)的第\(pos\)位为\(0\),则需要使数组\(c\)所有元素的第\(pos\)位为\(0\),对于\(c[i]\),我们枚举\(j\)通过\(c[i]=a[i]\&b[j]\)计算得出,如果存在一个\(j\)使得\(c[i]\)\(pos\)位为\(0\),并且该\(c[i]\)在或运算中不会使\(ans\)的后\(pos-1\)位变大,则该\(c[i]\)满足条件。若存在一个\(i\),无法得到满足条件的\(c[i]\),则第\(pos\)位只能为\(1\)

循环进行以上步骤,便可得到\(ans\)的值。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,m,a[200+10],b[200+10];
int main(){
	cin >> n >> m;
	for(ll i=1;i<=n;i++)cin >> a[i];
	for(ll i=1;i<=m;i++)cin >> b[i];
	ll ans=0;
	for(ll pos=8;pos>=0;pos--){
		bool isempty=true;
		for(ll i=1;i<=n;i++){
			bool flag=false;
			for(ll j=1;j<=m;j++){
				if((((a[i]&b[j])>>pos)|(ans>>pos))==(ans>>pos)){
					flag=true;
				}
			}
			if(!flag)isempty=false;
		}
		if(!isempty)ans+=(1<<pos);
	}
	cout << ans;
	return 0;
}