CF-1451 E Bitwise Queries 异或交互题

E - Bitwise Queries

传送门

题意

有一组序列，长度为 \(n(4\le n \le 2^{16})\)，且 \(n\) 为 2 的整数次幂，序列中数值范围为 [0,n-1], 每次可以发起一次询问，询问分为以下几种：

AND i j
XOR i j
OR i j

即序列中第 i 个数字和第 j 个数字的位运算结果，请你在不超过 n+1 次询问前提下求出这个序列。

此题的简单版本询问次数不超过 n+2 次。

首先要知道这几条规则：

a + b = a ^ b + 2 * (a & b)
a ^ c = (a ^ b) ^ (b ^ c)

所以可以如下操作：

int xorab = a ^ b, xorac = a ^ c, xorbc = xorab ^ xorac;

int andab = a & b, andbc = b & c, andac = a & c;

int ab = xorab + 2 * andab;

int bc = xorbc + 2 * andbc;

int ac = xorac + 2 * andac;

int a = (ab + ac - bc) / 2;

b = a ^ xorab;

c = a ^ xorac;

如上，可以在 5 次询问得到 a, b, c 的值，那么剩余的 n-3 个值，可以在 n-3 次询问得到

#include <bits/stdc++.h>

using namespace std;

const int N = 100010;

int n, xorvals[N], res[N];

int query(string s, int x, int y){

    cout << s << ' ' << x << ' ' << y << endl;

    cout.flush();

    int dest; cin >> dest;

    if(dest == -1) exit(0);

    return dest;

}

int main(){

    cin >> n;

    xorvals[1] = 0;

    for(int i=2;i<=n;i++) {

        xorvals[i] = query("XOR", 1, i);

    }

    int xorab = xorvals[2],  xorac = xorvals[3], xorbc = xorab ^ xorac;

    int andab = query("AND", 1, 2), andbc = query("AND", 2, 3), andac = query("AND", 1, 3);

    int ab = xorab + 2 * andab;

    int bc = xorbc + 2 * andbc;

    int ac = xorac + 2 * andac;

    res[1] = (ab + ac - bc) / 2;

    for(int i=2;i<=n;i++) res[i] = xorvals[i] ^ res[1];

    cout << "! ";

    for(int i=1;i<=n;i++) cout << res[i] << ' ';

    puts("");

    return 0;

}

接下来讨论如何省掉一个询问。

不妨假设一种情况，这 n 个数字中有两个数字是一样的，假设是第 i 个和第 j 个，那么一定有 \(a_1 \land a_i = a_1 \land a_j\), 另外 \(a_i = a_i \& a_j\), 可以通过一组询问 "AND i j" 来得到这两个数值的值，这种情况总共需要 n 次询问。

另外一种情况，将是 [0, n-1] 中的每个数字都会出现恰好一次，这就使得对于每个数字 i，都可以找到一个 j，使得 \(a_i \land a_j = n-1\) ，并且不需要询问就可以知道这两个数字的逻辑且运算结果为 0，即 \(a_i \& a_j = 0\), 这个意味着什么呢？这可以为我们省掉一个 "AND" 询问，对标上面的 n-2 次询问的做法，这里仅需要 n-1 次询问。

#include <bits/stdc++.h>

using namespace std;

const int N = (1 << 16) + 5;

int n, xorvals[N], res[N];

vector<int> pos[N];

int query(string s, int i, int j){

    cout << s << ' ' << i << ' ' << j << endl;

    cout.flush();

    int dest;

    cin >> dest;

    if(dest == -1) exit(0);

    return dest;

}

int main(){

    cin >> n;

    xorvals[1] = 0;

    pos[0].push_back(1);

    for(int i=2;i<=n;i++){

        xorvals[i] = query("XOR", 1, i);

        pos[ xorvals[i] ].push_back(i);

    }

    // same 判断是否存在与 a[1] 异或值一样的数字

    int same = -1, a = 1, b = -1, c = -1;

    for(int i=0;i<n;i++){

        if(pos[i].size() > 1){

            same = 1;

            b = pos[i][0];

            c = pos[i][1];

        }

    }

    if(same == -1) {// 若不存在一样的数字，表示[0,n-1] 中的每个数字都将出现

        for(int i=2;i<=n;i++){

            if(xorvals[i] == n-1){ // 找到与 res[1] 对应的数字，可以省掉一个 “AND” 询问

                b = i;break;

            }

        }

        // 随便找一个第三个数字

        if(b == 2) c = 3;

        else c = 2;

        int xorab = xorvals[b], xorac = xorvals[c], xorbc = xorvals[b] ^ xorvals[c];

        int andab = 0, andbc = query("AND", b, c), andac = query("AND", a, c);

        int ab = xorab + 2 * andab;

        int bc = xorbc + 2 * andbc;

        int ac = xorac + 2 * andac;

        res[1] = (ab + ac - bc) / 2;

    } else { // 若存在，对标第一种情况

        res[b] = query("AND", b, c);

        res[1] = res[b] ^ xorvals[b];

    }

    for(int i=2;i<=n;i++) res[i] = res[1] ^ xorvals[i];

    cout << "! ";

    for(int i=1;i<=n;i++) cout << res[i] << ' ';

    cout << endl;

    return 0;

}

巴特西

CF-1451 E Bitwise Queries 异或交互题

E - Bitwise Queries

最新文章

热门文章

巴特西

CF-1451 E Bitwise Queries 异或 交互题

E - Bitwise Queries

最新文章

热门文章

CF-1451 E Bitwise Queries 异或交互题