CF 1721D Maximum AND

標籤： cf

给定序列 $a$，$b$，$b$ 可以任意排列。令 $c_i = a_i \oplus b_i$，则价值则为 $c_1 \& c_2 \& c_3 \& \cdots \& c_n$，求价值最大值。

如果答案的某一位是 $1$，则 $a$ 该位的 $0$ 和 $1$ 数量必然和 $b$ 该位的 $1$ 和 $0$ 数量分别相同。同样的，如果答案 $ans$ 可行，则 $a_i \& ans$ 得到的所有值的数量与 $\neg b_i \& ans$ 得到的所有值的数量相同（$\neg$ 当作取反符号）。从高位到低位，判断 $ans$ 当前位为 $1$ 是否可行，可行则或上。

void solve()
{
    int n;
    std::cin >> n;
    std::vector<unsigned int> a(n), b(n);
    for (auto &i : a) std::cin >> i;
    for (auto &i : b) std::cin >> i;
    auto check = [&a, &b](unsigned int ans) {
        std::map<unsigned int, int> cnt;
        for (auto i : a) cnt[i & ans]++;
        for (auto i : b) cnt[~i & ans]--;
        for (auto i : cnt) {
            if (i.second != 0) return false;
        }
        return true;
    };

    unsigned int ans = 0;
    for (int i = 31; i >= 0; i--) {
        if (check(ans | (1 << i))) {
            ans |= (1 << i);
        }
    }
    std::cout << ans << std::endl;
}