D. Maximum AND（位运算/bfs/双指针/贪心）

题目

题意

给定两个长度为n的数组a,b。 定义c[i] = a[i] ^ b[i] 令f = c[1] & c[2] & … & c[n]

这里^, &分别代表异或运算， 与运算。

允许重新排列b数组。

求f的最大值。

思路

对于这种位运算求最大值的题目，考虑从高位到低位去确定答案。

对于c数组的第i位，如果它能取1，说明c[i]在第i位都是1（与运算的性质），说明a[i]在第i位上0的个数和b[i]在第i位上1的个数相等（异或运算的性质）。

我们从高位到低位去做分层。

• 如果当前第i位可以取1，则继续划分区间，判断下一位。
• 如果当前第i位不可以取1，则保留当前的区间划分。

详见代码

代码

#include
using namespace std;
const int maxn = 200010;

int n, m;
vector a, b;

int res;
void solve() {
	scanf("%d", &n);
	a.resize(n);
	b.resize(n);
	for (int i = 0; i