Question answer: CF2077B Finding OR Sum

Ideas

Regarding this question, we first answer\(n | x\)Change the shape,\(n | x = n + (x \& \sim n)\), that is,\(n\)and\(x\)At the same time\(1\)The position is in\(x\)If you delete it, then\(1\)or\(n\), or\(x\), so we can come up with\((x \& \sim n) + (y \& \sim n) = (n | x) + (n | y) - 2 \times n\)。
We want to get\((m | x) + (m | y)\)The value of only each bit needs to be put on\(x\)and\(y\)of\(1\)Find out the number of occurrences and then follow\(m\)Every one of\(1\)still\(0\)Just simulate or calculate and bit operations.
So how do we put each person in the case of two inquiries\(1\)Find out the number of appearances?
We noticed that in the case of binary bits, the current bit is\(i\)If the\(i + 1\)bit and\(i - 1\)All\(0\), then the second number of the two numbers\(i\)There are only two types of cases when adding up:

• two\(1\):\(i + 1\)Position is\(1\),\(i\)Position is\(0\)。
• two\(0\):\(i + 1\)bit and\(i\)All positions are\(0\)。
• one\(1\)one\(0\):\(i\)Position is\(1\),\(i + 1\)Position is\(0\)。

Then, we can find that all odd numbers will become\(0\)The sum of two numbers, the even number\(1\)Find the number of occurrences, find that all even digits become\(0\)The sum of two numbers, the odd number\(1\)Find out the number of occurrences.

Then, solve bit by bit according to the following rules:

• if\(m\)The\(i\)Position is\(1\), then this person's contribution to the answer is\(1 \ll (i + 1)\)。
• if\(m\)The\(i\)Position is\(0\), then this person's contribution to the answer depends on\(1\)The number of occurrences, if the occurrences are\(2\), that's\(1 \ll (i + 1)\), if the number of occurrences is\(1\), that's\(1 \ll i\)。

AC CODE

#include <bits/stdc++.h>
#define inf 2e18
#define int long long

const int N = 2e5 + 9;

int ask(int x) {
    std::cout << x << std::endl;
    int op;std::cin >> op;
    return op;
}

void solve()
{
    std::vector<int> a(30);

    int tmp = 0;
    for(int i = 0;i < 30;i += 2) {
        tmp |= (1ll << i);
    }
    
    int res1 = ask(tmp) - tmp * 2;
    for(int i = 1;i < 30;i += 2) {
        if(res1 & (1ll << (i + 1))) {
            a[i] = 2;
        } else if(res1 & (1ll << i)) {
            a[i] = 1;
        } else {
            a[i] = 0;
        }
    }

    tmp = 0;
    for(int i = 1;i < 30;i += 2) {
        tmp |= (1ll << i);
    }

    int res2 = ask(tmp) - tmp * 2;
    for(int i = 0;i < 30;i += 2) {
        if(res2 & (1ll << (i + 1))) {
            a[i] = 2;
        } else if(res2 & (1ll << i)) {
            a[i] = 1;
        } else {
            a[i] = 0;
        }
    }

    std::cout << '!' << std::endl;

    int ck;std::cin >> ck;

    int ans = 0;
    for(int i = 0;i < 30;i ++) {
        if(ck & (1 << i)) {
            ans += (1ll << (i + 1));
        } else if(a[i] == 2) {
            ans += (1ll << (i + 1));
        } else if(a[i] == 1) {
            ans += (1ll << i);
        }
    }

    std::cout << ans << std::endl;
}