Educational Codeforces Round 134 (Rated for Div. 2) D. Maximum AND

Codeforces Round 134 (Rated for Div. 2) D. Maximum AND"/>

Educational Codeforces Round 134 (Rated for Div. 2) D. Maximum AND

• 给你两个数组a和b，随意安排b的顺序，问最后 c [ i ] = a [ i ] & b [ i ] c[i]=a[i]\&b[i] c[i]=a[i]&b[i]所有的c的与值的最大值是多少
• c的每一位如果想为1，那么必须a中这一位1的个数等于b中这一位0的个数，或者a中这一位0的个数等于b中这一位1的个数，这个不难想到，但是接下来会发现这样考虑的话，对于已经分好的块，必须要向下递归处理子块使得其满足同样性质，也就是一共31层，不好处理
• 这种问题的套路有几个，第一是贪心，高位比低位更优；第二是可选的位一定是满足当前位的同时满足更高的位这样的位置，所以我们可以假定某一位答案是1，然后我们看更高的位能不能满足，如果能够满足就说明这一位可以是1，否则不可以
• 根据上面的想法，可以把每次的答案与a数组中的每个数做一次与运算，要求每个数在b数组经过某种运算之后，都能找到，否则说明这一位不可选，因为是贪心，所以一定是最优的。那么b中的运算应该是什么呢？因为a中是1，b中是0，所以对b取个反即可

#include <iostream>
#include <cstdio>
#include <map>
#include <cmath>
#include <vector>
#include <set>
#include <algorithm>
#include <functional>using namespace std;typedef long long ll;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];}int ans = 0;for(int i=30;i>=0;i--) {vector<int> va, vb;ans |= (1 << i);for(int j=0;j<n;j++) {va.push_back(ans & a[j]);}for(int j=0;j<n;j++) {vb.push_back(ans & ~b[j]);}sort(va.begin(), va.end());sort(vb.begin(), vb.end());if(va != vb) {ans ^= (1 << i);}}cout << ans << '\n';}return 0;
}