CF 1721D Maximum AND

标签: cf

给定序列 可以任意排列。令 ,则价值则为 ,求价值最大值。

如果答案的某一位是 ,则 该位的 数量必然和 该位的 数量分别相同。同样的,如果答案 可行,则 得到的所有值的数量与 得到的所有值的数量相同( 当作取反符号)。从高位到低位,判断 当前位为 是否可行,可行则或上。

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;
}