Educational Codeforces Round 134 (Div.2) D 题解

题目链接

D. Maximum AND

题目大意

给定两组序列 \(a\) \(b\),长度为 \(n\) ,现有一新序列 \(c\),长度也为 \(n\)
其中,\(c_i = a_i \oplus b_i\)
定义 \(f(a,b) = c_1\&c_2\&……\&c_n\)
现在你可以随意编排 \(b\) 序列的顺序,求 \(f(a,b)\) 的最大值。

思路

以下位运算均是二进制。

由于按位与的运算结果是越来越小的,考虑从高位往低位贪心。
将结果的其中一位定为1之后,有一些序列 \(b\) 中的元素的位置就被定下来了。
所以我们要从高位往低位贪心,有一位可以置为1,就把它置为1.

具体做法:暴力枚举,时间复杂度\(O(nlognlogA)\),其中 \(A\) 是输入序列的最大值。

void solve() {

	cin >> n;

	a = vector<int> (n);
	b = vector<int> (n);

	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}

	for (int i = 0; i < n; ++i) {
		cin >> b[i];
	}
	
	auto check = [&](int ans){
		//ans是一个2的整次幂
		map<int,int> cnt;
		//下面两个for是 判断该位上、a序列的1和b序列的0的个数是否相等。
		for(auto x:a) cnt[x & ans] += 1;
		for(auto x:b) cnt[~x & ans] -= 1;
		bool ok = true;
		//如果有1,证明不等,ok置为false
		for(auto [u,v] : cnt){
			ok &= v == 0;
		}
		return ok;
	};
	
	int ans = 0;
	for(int j = 30; j >= 0; --j){
		//从高位向低位检查。
		//写博客的时候的思考:如何把之前的已经确定了的1保存下来
		//答:其实就保存在ans中。
		if(check(ans | (1ll << j))){
			ans |= 1 << j;
		}
	}

	cout << ans << '\n';
}

热门相关:高人竟在我身边   高人竟在我身边   高甜预警:我家影后超猛的   法医萌妻,撩上瘾!   法医萌妻,撩上瘾!