CF1721D Maximum AND

CF1706D Maximum AND

题目链接

分析

• 第一步是先考虑写一个 check() 函数，验证答案 ans 是否成立。用一个 map，类似找匹配那样暴力求解即可：

  bool check(int ans)
  {
  	map<int, int> rec;
  	for (int i = 0; i<n; i++) {
  		int tmp = b[i] & ans;
  		rec[tmp]++;
  	}
  	for (int i = 0; i<n; i++) {
  		int tmp = (a[i] & ans) ^ ans;
  		if (rec.count(tmp) && rec[tmp]>0) {
  			rec[tmp]--;
  		}
  		else {
  			return false;
  		}
  	}
  	return true;
  }

• 注意，这道题没办法二分。故采取一种贪心的做法：从最高位开始遍历，若目前已知的 ans 加上该位上的值所得到的新 ans 成立，则把这个值加上去。遍历完之后，ans 即为所求的最大值。

代码

#include <bits/stdc++.h>

using namespace std;
const int MAXN = 1e5 + 5;
using LL = long long;

int n;
array<int, MAXN> a, b;
bool check(int ans)
{
	map<int, int> rec;
	for (int i = 0; i<n; i++) {
		int tmp = b[i] & ans;
		rec[tmp]++;
	}
	for (int i = 0; i<n; i++) {
		int tmp = (a[i] & ans) ^ ans;
		if (rec.count(tmp) && rec[tmp]>0) {
			rec[tmp]--;
		}
		else {
			return false;
		}
	}
	return true;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
//    freopen("in.txt", "r", stdin);

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

		int ans = 0;
		for (int i = (1 << 29); i>=1; i /= 2) {
			if (check(ans+i)) {
				ans += i;
			}
		}
		cout << ans << endl;
	}

	return 0;
}