Maximum AND

Created by LXC on Fri Oct 20 01:47:17 2023

https://codeforces.com/problemset/problem/1721/D

ranting: 1800

tag: bitmasks, dfs and similar, divide and conquer, greedy, sortings

problem

给出两个长度都为n的数组a和数组b。现在你可以重排b数组的元素。

并得到一个新数组$c$，其中$c_i = a_i \oplus b_i$

并使得$c_1 \mathbin{&} c_2 \mathbin{&} \cdots \mathbin{&} c_n$最大

solution

让与和最大，那应该贪心，尽量选择高位全为1.

如果第x位与和为1，那么a中第x位1的数目和b中第x位1的数目之和恰好为n，否则会存在异或为0的情况。我们找到所有满足的x，设有k个，从高位到低位分别为$x_1,x_2, \cdots, x_k$

设$a_i$为a的第i个元素，$a_{i,j}$为a的第i个元素的低位第j位。

然后自定义一种排序比较器，对a数组中任意两个元素$a_i$和$a_j$只有字典序$a_{i,x_1}a_{i,x_2}\cdots a_{i,x_k} < a_{j,x_1}a_{j,x_2}\cdots a_{j,x_k}$则$a_i$排在前面。对b数组中任意两个元素$b_i$和$b_j$只有字典序$b_{i,x_1}b_{i,x_2}\cdots b_{i,x_k} > b_{j,x_1}b_{j,x_2}\cdots b_{j,x_k}$则$b_i$排在前面。

对a和b数组排序后，得到他们的异或与和s。如果$s \ne \sum 2^{x_i}$，遍历$x_1,x_2, \cdots, x_k$找到第一个$x_i$删除掉，其中s的第$x_i$位为0。

然后继续排序，计算异或与和s。直到$s = \sum 2^{x_i}$，便找到了答案。

code

#include <bits/stdc++.h>
// #define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 500005
#define MOD 998244353
using namespace std;


void sol() {
    int n;
    cin >> n;
    vector<int> a(n), b(n);
    for (auto& i:a) cin >> i;
    for (auto& i:b) cin >> i;
    vector<int> d;
    for (int x=30; x>=0; x--) {
        int a1=0, b1=0;
        for (int i=0; i<n; i++) {
            a1 += a[i]>>x&1;
            b1 += b[i]>>x&1;
        }
        if (a1 + b1 == n) d.push_back(x);
    }
    int ans = 0;
    while (1) {
        sort(a.begin(), a.end(), [&](auto x, auto y) {
            for (int i:d) {
                if ((x>>i&1) != (y>>i&1)) {
                    return (x>>i&1) < (y>>i&1);
                }
            }
            return false;
        });
        sort(b.begin(), b.end(), [&](auto x, auto y) {
            for (int i:d) {
                if ((x>>i&1) != (y>>i&1)) {
                    return (x>>i&1) > (y>>i&1);
                }
            }
            return false;
        });
        ans = a[0]^b[0];
        for (int i=1; i<n; i++) {
            ans &= a[i]^b[i];
        }
        int ok = 1;
        for (int i=0; i<d.size(); i++) {
            if (ans>>d[i]&1) continue;
            d.erase(d.begin()+i);
            ok = 0;
            break;
        }
        if (ok) break;
    }
    cout << ans << "\n";
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    // if (t == 10000)
    // for (int i=1; i<=t; i++) {
    //     int n;
    //     cin >> n;
    //     vector<int> a(n), b(n);
    //     for (auto& i:a) cin >> i;
    //     for (auto& i:b) cin >> i;
    //     if (13 == i) {
    //         cout << n << endl;
    //         for (auto i:a) cout << i << " "; cout << endl;
    //         for (auto i:b) cout << i << " "; cout << endl;
    //     }
    // }
    // else 
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}