CF2222E Seek the Truth
XXh0919
·
·
题解
upd on 2026.4.28：解释了操作次数。
所以还是交互题好玩。
题意
太长了，自己去看题。
解法
首先容易注意到题目中保证 c\not=0，所以我们可以直接令 a=0，并将其作为 S 的初始元素。
现在来看如何找到答案。
::::info[k=1]{open}
我们可以这样构造 $c$：对于 $0\le i<n$，每次插入 $2^i$，如果说在插入后 $|S|$ 变了，就说明 $c$ 的第 $i+1$ 个二进制位是 $1$，那么我们就把 $2^i$ 加入答案。
::::
::::info[$k=2$ 或 $3$]{open}
因为你在第一次插入了 $0$，而 $0 \operatorname{or} c=0\operatorname{xor} c=c$，所以此时 $S=\{0,c\}$。那么我们可以通过第二种查询，二分找到 $c$。
由于异或的性质，我们可以找到 $c$ 在二进制下的某一位 $1$（假设它是第 $i$ 位），然后向 $S$ 插入 $2^i$。如果说 $|S|$ 没变，那么就说明是按位或运算（$k=2$），因为此时 $c\operatorname{or} 2^i=c$。否则 $k=3$，因为此时 $c$ 的第 $i$ 位上的 $1$ 会因为异或变成 $0$ 导致多了一个数。
::::
代码实现就是按照上面的过程模拟。
对于与运算，用了 $n+1$ 次 `I` 操作，所以操作数是 $n+1$；对于剩下两种运算，二分中最多用 $n$ 次 `Q` 操作，若 $c$ 不是 $2$ 的幂，则仅用 $1$ 次 `I` 操作，若 $c$ 是 $2$ 的幂，则要用 $1$ 次 `I` 操作和 $1$ 次 `Q` 操作，总操作数最多 $1+n+1+1=n+3$ 次。
::::success[Code]
```cpp
int n;
inline void init (i64 x) {
cout << x << endl;
return ;
}
inline i64 I (i64 x) {
cout << "I " << x << endl;
i64 res;
cin >> res;
return res;
}
inline i64 Q (i64 x) {
cout << "Q " << x << endl;
i64 res;
cin >> res;
return res;
}
inline void A (int k, i64 c) {
cout << "A " << k << " " << c << endl;
return ;
}
inline i64 find () {
i64 l = 1, r = (1ll << n) - 1, ans = r;
while (l <= r) {
i64 mid = l + r >> 1;
if (Q (mid) > 0) ans = mid, l = mid + 1;
else r = mid - 1;
}
return ans;
}//二分
inline void solve () {
cin >> n;
int k;
i64 c = 0;
init (0);
i64 siz = I (0);
if (siz == 1) {//按位与运算
k = 1;
for (i64 i = 0; i < n; ++ i) {
i64 now = I (1ll << i);
if (now == siz + 1) c |= (1ll << i);
siz = now;
}
A (k, c);
return ;
} else {
c = find ();
//这里为了方便取了最低位的 1
if ((c & -c) == c) {
I ((1ll << n) - 1);
i64 cnt = Q ((1ll << n) - 1);
if (cnt == 1) k = 2;
else k = 3;
//特判 c 是不是 2 的幂，因为这样的话不管 k 是多少插入后集合大小都不会变
} else {
i64 now = I(c & -c);
if (now == 3) k = 3;//按位异或运算
else k = 2;//按位或运算
}
A (k, c);
return ;
}
}
```
::::