題目

有一序列 a[1]~a[n]，只能詢問 a[i]&a[j] 和 a[i]|a[j]，不能問超過 2n 次。

解法

仔細觀察真值表，只考慮一個 bit 情況下，可以發現 (a&b) ^ (a|b) == a ^ b。

a/b 0 1
0 0 1
1 1 0

如果可以算出其中一個數字，其他數字也能經由 xor 找到。

考慮 a, b, c，a ^ b == a ^ c 代表 b == c，還不確定 b 是 0 或 1，不過我們還有 b&c 可以用，如果 b&c == 1， b 一定是 1。每個 bit 都處理一次可以算出 a[1]~a[3]。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

for(int i = 30; i >= 0; i--) {
    xor_1_2 = (and_1_2 & 1) ^ (or_1_2 & 1);
    xor_2_3 = (and_2_3 & 1) ^ (or_2_3 & 1);
    xor_3_1 = (and_3_1 & 1) ^ (or_3_1 & 1);
    a[1] <<= 1;
    a[2] <<= 1;
    a[3] <<= 1;
    if(!xor_1_2) {
        a[1] |= and_1_2 & 1;
        a[2] |= and_1_2 & 1;
        a[3] |= (and_1_2 & 1) ^ xor_2_3;
    } else if(!xor_2_3) {
        a[2] |= and_2_3 & 1;
        a[3] |= and_2_3 & 1;
        a[1] |= (and_2_3 & 1) ^ xor_1_2;
    } else {
        a[1] |= and_3_1 & 1;
        a[3] |= and_3_1 & 1;
        a[2] |= (and_3_1 & 1) ^ xor_1_2;
    }
    and_1_2 >>= 1, or_1_2 >>= 1;
    and_2_3 >>= 1, or_2_3 >>= 1;
    and_3_1 >>= 1, or_3_1 >>= 1;
}

每個位置 xor a[1] 需要 2n-2 個詢問，a[2] xor a[3] 需 2 個詢問，總共不會超過 2n。最後找到所有數值第 k 小就好。