Maximum AND
贪心
从高位开始,尽可能地让 \(a\) 中该位为 \(0\) 的 和 \(b\) 中该位为 \(1\) 的配对在一起,换句话说,可以让 \(a\) 由小到大排序,\(b\) 由大到小排序
-
如果当前位最终是 \(1\),则继续该过程
-
如果当前位最终是 \(0\),则说明失配,考虑将这一位全部置为 \(1\) (排除这一位对排序造成的影响),重新排序
整个过程有种递归的感觉
#include <iostream>
#include <cstdio>
#include <vector>
#include <string>
#include <algorithm>
#include <functional>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 10;
bool cmp(int a, int b)
{
return a > b;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while(t--)
{
int n;
cin >> n;
vector<int>a(n), b(n);
for(int i=0; i<n; i++) cin >> a[i];
for(int i=0; i<n; i++) cin >> b[i];
sort(a.begin(), a.end());
sort(b.begin(), b.end(), cmp);
ll ans = 0;
for(int i=30; i>=0; i--)
{
int f = (1 << 31) - 1;
for(int j=0; j<n; j++)
f &= a[j] ^ b[j];
if(f >> i & 1 ^ 1)
{
for(int j=0; j<n; j++)
{
a[j] |= 1 << i;
b[j] |= 1 << i;
}
sort(a.begin(), a.end());
sort(b.begin(), b.end(), cmp);
}
else
ans |= 1 << i;
}
cout << ans << "\n";
}
return 0;
}
标签:Educational,Rated,int,Codeforces,cin,排序,include,Maximum
From: https://www.cnblogs.com/dgsvygd/p/16649762.html