普通题把完整输入一次性交给程序，交互题却只给出一部分信息。我们需要主动发出询问，评测机根据询问返回结果，再用这些结果决定下一步问什么。

交互题的代码通常不长，难点主要有两个：怎样让一次询问提供足够多的信息，以及怎样证明最坏情况下不会超过询问次数。二分、奇偶性、异或、前缀差分和状态计数，都是设计询问时常见的工具。

这一篇先整理交互协议与代码写法，再通过六道例题说明几种常见模型。正文不依赖配图，重点放在询问的构造、信息量与次数证明。

交互题怎样运行

程序与评测机轮流工作

普通题的过程是：

1
读入完整数据 -> 计算答案 -> 输出答案

交互题则更像一段对话：

1
2
3
4
5
读取初始信息
输出一次询问并刷新缓冲区
读取评测机的回答
根据回答构造下一次询问
确定答案后输出并立即结束

以最常见的询问格式为例：

1
? l r

程序输出询问以后必须停下来读取回答，不能把后面所有询问提前输出。评测机给出的回答本身也是输入的一部分，只是它取决于我们刚才输出了什么。

query 与 print

为了避免在主逻辑中反复写输出、刷新和读入，最好把一次完整交互封装成函数：

1
2
3
4
5
6
7
8
9
10
11
12
int query(int l, int r) {
    cout << "? " << l << " " << r << '\n';
    fflush(stdout);
    int t; cin >> t;
    if (t == -1) exit(0);
    return t;
}

void print(int x) {
    cout << "! " << x << '\n';
    fflush(stdout);
}

调用 query(l,r) 时，函数负责完成“输出询问、刷新、读取回答”三个动作；print只负责提交最终答案。

本文代码保留默认的流同步，并使用 fflush(stdout) 刷新，和后文的代码风格保持一致。如果写了 ios::sync_with_stdio(false)，就应该改用 cout.flush()，不要再依赖C语言的 fflush 刷新已经解除同步的C++流。

为什么一定要刷新

输出通常会先进入缓冲区，积累到一定大小以后才真正发送。普通题最后一次性发送没有问题，但交互题的评测机只有收到询问才会给出回答。

如果询问仍然留在缓冲区中，程序在等待回答，评测机也在等待询问，最后通常得到 Idleness limit exceeded 或 TLE。

下面三种写法都可以主动刷新：

1
2
3
cout << "? " << x << endl;
cout << "? " << x << '\n' << flush;
cout << "? " << x << '\n'; fflush(stdout);

endl会同时换行和刷新，写起来最短，但普通题中频繁使用会增加额外开销。交互题的询问次数通常不大，三种写法都足够；本文统一使用第三种。

-1、非法询问与立即退出

很多交互题会在询问非法、次数超限或答案已经错误时返回$-1$。此时交互已经结束，继续读取只会从关闭的输入流中得到无效数据，因此应该立即退出：

1
2
int t; cin >> t;
if (t == -1) exit(0);

还要逐项检查题面的协议：

  • 询问的下标能否重复；
  • 区间是否允许为空；
  • 输出答案是否计入询问次数；
  • 多组数据之间是否需要额外读取判定结果；
  • 输出答案以后是继续下一组，还是立即结束整个程序。

交互题没有统一格式，上一道题的 query 不能不看题面直接复制到下一道题。

自适应与非自适应交互器

非自适应交互器会在开始前固定隐藏数据，此后只负责如实回答。自适应交互器则可以在不违背已有回答的前提下继续调整隐藏数据。

面对自适应交互器，仅仅找到一个“可能的答案”并不够。所有回答共同构成的约束必须唯一确定答案，否则交互器仍然可以选择另一个同样合法的隐藏状态。

因此，证明一个交互方案时要回答三件事：

  1. 每次回答能推出什么确定信息；
  2. 这些信息能否唯一确定答案；
  3. 最坏情况下用了多少次询问。

怎样设计询问

先写出回答的数学含义

不要一上来就猜询问格式。先把评测机的回答写成关于隐藏量的式子，再观察两次回答之间有哪些量会抵消。

常见的构造方式包括：

方法 询问提供的信息 常见目标
区间计数 某个前缀、后缀或矩形中的数量 二分缺失位置
只替换一个元素 两次回答只相差一个未知量 求每个位置的值
奇偶性或异或 只保留出现奇数次的贡献 消去成对元素
特殊输入 让不同隐藏操作得到明显不同的结果 判断运算类型
枚举顺序 相邻回答共享较长前缀 恢复边或状态转移

一个好的询问，通常会让大部分未知量彼此抵消，只留下当前真正想知道的部分。

维护没有被排除的状态

普通二分维护候选区间，交互二分也一样。假设当前答案一定在$[l,r]$中，一次询问把它分成两部分，回答必须能够确定答案落在哪一侧。

如果一次询问最多把候选状态分成两类，那么$q$次询问最多区分$2^q$种情况，因此至少需要：

$$
q\ge\lceil\log_2 S\rceil
$$

其中$S$是初始可能状态的数量。这不是所有交互题的严格下界，但可以帮助判断询问上限是否暗示二分、按位确定或其他倍增信息的做法。

先计算询问次数，再写代码

假设一个位置需要二分$\lceil\log_2 n\rceil$次，共有三个位置要找，那么最坏询问数就是：

$$
3\lceil\log_2 n\rceil
$$

如果题目只允许$33$次，而$n\le1000$，就有：

$$
3\lceil\log_2(2n+1)\rceil\le3\times11=33
$$

这种计算应该在实现以前完成。只写“复杂度大约是对数级”不够，交互题限制的是具体次数，差一次同样会得到错误答案。

调试时不要污染标准输出

标准输出中的每个字符都可能被交互器当成命令。调试信息应该输出到 cerr：

1
cerr << "l = " << l << ", r = " << r << '\n';

提交以前仍然建议删除调试输出。更稳妥的做法是自己写一个本地交互器，随机生成隐藏数据，并检查询问是否合法、次数是否超限、最终答案是否正确。

例题与典型应用

下面六道题从普通二分开始，逐步加入异或方程、进位、奇偶性、DAG计数和位运算构造。

题目 核心信息 最坏询问次数
AtCoder ABC269 E 矩形中的棋子数量 $2\lceil\log_2 n\rceil$
AtCoder ABC313 D 奇偶性与异或方程 $n$
洛谷 P14843 数位和与进位 $73$
Codeforces 2219B2 频次奇偶性与三次出现 $33$
Codeforces 2196C2 字典序路径与DAG计数 $n+m$
Codeforces 2222E 特殊输入、按位恢复与分类 $n+3$

例题一：AtCoder ABC269 E Last Rook

题目链接：AtCoder ABC269 E Last Rook

有一个$n\times n$棋盘，上面放了$n-1$个车，并且任意两辆车都不在同一行或同一列。每次可以询问一个矩形中有多少辆车，需要找出可以放置最后一辆车的位置。

因为$n-1$辆车占据了$n-1$个不同的行和$n-1$个不同的列，所以恰好缺少一行和一列。分别找出缺失行与缺失列即可。

设缺失行为$x$。询问前$mid$行和全部列组成的矩形，若$x>mid$，前$mid$行每行都有一辆车，回答为$mid$；若$x\le mid$，其中恰好缺少一辆，回答为$mid-1$。因此：

$$
query(1,mid,1,n)<mid\Longleftrightarrow x\le mid
$$

这个判定具有单调性，可以二分第一个满足条件的位置。缺失列完全相同，只要把询问改成全部行与前$mid$列。

点击展开完整代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/* Fufffh */
#include <bits/stdc++.h>
using namespace std;
using i32 = int32_t; using i64 = int64_t; using i128 = __int128_t;
using u32 = uint32_t; using u64 = uint64_t; using u128 = __uint128_t;

int query(int a, int b, int c, int d) {
    cout << "? " << a << " " << b << " " << c << " " << d << '\n';
    fflush(stdout);
    int t; cin >> t;
    if (t == -1) exit(0);
    return t;
}

void print(int x, int y) {
    cout << "! " << x << " " << y << '\n';
    fflush(stdout);
}

int main() {
    int n;
    cin >> n;
    int l = 1, r = n, x = n, y = n;
    while (l <= r) {
        int mid = l + r >> 1;
        if (query(1, mid, 1, n) < mid) { x = mid; r = mid - 1; }
        else l = mid + 1;
    }
    l = 1, r = n;
    while (l <= r) {
        int mid = l + r >> 1;
        if (query(1, n, 1, mid) < mid) { y = mid; r = mid - 1; }
        else l = mid + 1;
    }
    print(x, y);
    return 0;
}

寻找一维位置需要$\lceil\log_2n\rceil$次询问，行列各做一次，总询问数不超过$2\lceil\log_2n\rceil$。由于$n\le1000$，最多只需$20$次，恰好满足限制。

例题二：AtCoder ABC313 D Odd or Even

题目链接：AtCoder ABC313 D Odd or Even

有一个长度为$n$的隐藏01序列$a$。每次选择$k$个不同位置，评测机返回这些位置之和的奇偶性，其中$k$为奇数。最多询问$n$次，需要确定整个序列。

奇偶性可以直接看成异或。先只考虑前$k+1$个位置。对每个$i\in[1,k+1]$，询问除$i$以外的另外$k$个位置，记回答为$b_i$。

设前$k+1$个数的异或和为：

$$
s=a_1\oplus a_2\oplus\cdots\oplus a_{k+1}
$$

由于第$i$次恰好没有选择$a_i$，所以：

$$
b_i=s\oplus a_i
$$

再把所有$b_i$异或起来。每个$a_j$一共出现在$k$次询问中，而$k$是奇数，因此：

$$
b_1\oplus b_2\oplus\cdots\oplus b_{k+1}=s
$$

于是前$k+1$个数都可以由$a_i=s\oplus b_i$恢复。

剩余位置更简单。固定前$k-1$个已知位置，再加入一个未知位置$i$询问。设前$k-1$个数的异或和为$pre$，回答就是$pre\oplus a_i$，因此$a_i=pre\oplus query$。

点击展开完整代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
/* Fufffh */
#include <bits/stdc++.h>
using namespace std;
using i32 = int32_t; using i64 = int64_t; using i128 = __int128_t;
using u32 = uint32_t; using u64 = uint64_t; using u128 = __uint128_t;

int query(const vector<int> &q) {
    cout << "? ";
    for (int x : q) cout << x << " ";
    cout << '\n';
    fflush(stdout);
    int t; cin >> t;
    if (t == -1) exit(0);
    return t;
}

void print(const vector<int> &a) {
    cout << "! ";
    for (int i = 1; i < (int)a.size(); i++) cout << a[i] << " ";
    cout << '\n';
    fflush(stdout);
}

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n + 1), b(k + 2), q;
    int s = 0;
    for (int i = 1; i <= k + 1; i++) {
        q.clear();
        for (int j = 1; j <= k + 1; j++) if (i != j) q.push_back(j);
        b[i] = query(q);
        s ^= b[i];
    }
    for (int i = 1; i <= k + 1; i++) a[i] = s ^ b[i];
    int pre = 0;
    for (int i = 1; i < k; i++) pre ^= a[i];
    for (int i = k + 2; i <= n; i++) {
        q.clear();
        for (int j = 1; j < k; j++) q.push_back(j);
        q.push_back(i);
        a[i] = pre ^ query(q);
    }
    print(a);
    return 0;
}

前$k+1$个位置使用$k+1$次询问，其余位置使用$n-k-1$次，总数正好为$n$。即使交互器可以自适应，这$n$个独立关系也会唯一确定整个序列。

例题三：洛谷 P14843 Interactive Number Guessing

题目链接：洛谷 P14843 Interactive Number Guessing

评测机保存了一个小于$10^{18}$的非负整数$x$。每次选择非负整数$a$，可以得到$x+a$的十进制数位和。最多询问$75$次，需要确定$x$。

先询问$a=0$，得到$x$本身的数位和，记作$sum$。

现在单独考虑第$i$位，位权为$p=10^i$，这一位数字为$d$。询问$m\cdot p$，其中$0\le m\le9$。

如果$d+m\le9$，这一位不会产生进位，新的数位和恰好为：

$$
sum+m
$$

如果$d+m\ge10$，至少会产生一次进位。一次进位会让当前位减少$10$，并让更高一位增加$1$，数位和相对没有进位的情况少$9$；进位每向高位继续传播一次，还会再少$9$。所以回答不再等于$sum+m$。

因此“回答是否等于$sum+m$”关于$m$单调。最大的合法$m$恰好是$9-d$，从而得到：

$$
d=9-m
$$

对每一位分别在$[0,9]$中二分即可。

点击展开完整代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/* Fufffh */
#include <bits/stdc++.h>
using namespace std;
using i32 = int32_t; using i64 = int64_t; using i128 = __int128_t;
using u32 = uint32_t; using u64 = uint64_t; using u128 = __uint128_t;

int query(i64 x) {
    cout << "query " << x << '\n';
    fflush(stdout);
    int t; cin >> t; return t;
}

void print(i64 x) {
    cout << "answer " << x << '\n';
    fflush(stdout);
}

int main() {
    int sum = query(0);
    i64 ans = 0, p = 1;
    for (int i = 0; i < 18; i++, p *= 10) {
        int l = 0, r = 9, t = 0;
        while (l <= r) {
            int mid = l + r >> 1;
            if (query(mid * p) == sum + mid) { t = mid; l = mid + 1; }
            else r = mid - 1;
        }
        ans += (9 - t) * p;
    }
    print(ans);
    return 0;
}

第一次询问得到原数位和，每一位最多二分$4$次，共有$18$位，因此最坏询问数为：

$$
1+18\times4=73
$$

这比限制的$75$次少$2$次。

例题四：Codeforces 2219B2 Unique Values

题目链接：Codeforces 2219B2 Unique Values

隐藏数组长度为$2n+1$。其中一个值出现三次，其余$n-1$个值各出现两次。每次选择若干不同位置，评测机返回在这些位置中恰好出现一次的值有多少个，需要在$33$次询问内找出特殊值的三个位置。

设一次询问选择了$k$个位置，回答为$u$。先只看一个普通值：

在询问中出现次数 对$k$奇偶性的贡献 是否计入$u$
$0$ $0$ $0$
$1$ $1$ $1$
$2$ $0$ $0$

普通值无论出现零次、一次还是两次，对$k$和$u$的奇偶性贡献都相同。特殊值出现零到两次时也一样，只有三个位置全部被选中时，它对$k$贡献奇数，却不会被计入$u$。

因此：

$$
(u\bmod2)\oplus(k\bmod2)=1
$$

当且仅当询问集合包含特殊值的全部三个位置。

先询问前缀$[1,mid]$，二分第一个包含全部三个位置的前缀，它的右端点就是最右侧位置$qr$。再询问后缀$[mid,2n+1]$，二分最后一个包含全部三个位置的后缀，得到最左侧位置$ql$。

最后把$ql,qr$固定加入询问，再对中间区间二分。此时选中的特殊值已经出现两次，当前区间包含中间位置时才会变成三次，仍然可以使用同一个奇偶判定。

点击展开完整代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
/* Fufffh */
#include <bits/stdc++.h>
using namespace std;
using i32 = int32_t; using i64 = int64_t; using i128 = __int128_t;
using u32 = uint32_t; using u64 = uint64_t; using u128 = __uint128_t;

int query(int l, int r) {
    int k = r - l + 1;
    cout << "? " << k << " ";
    for (int i = l; i <= r; i++) cout << i << " ";
    cout << '\n';
    fflush(stdout);
    int t; cin >> t;
    if (t == -1) exit(0);
    return t;
}

int qry(int l, int r, int qi, int qj) {
    int k = r - l + 3;
    cout << "? " << k << " " << qi << " " << qj << " ";
    for (int i = l; i <= r; i++) cout << i << " ";
    cout << '\n';
    fflush(stdout);
    int t; cin >> t;
    if (t == -1) exit(0);
    return t;
}

void print(int i, int j, int k) {
    cout << "! " << i << " " << j << " " << k << '\n';
    fflush(stdout);
}

void solve() {
    int n;
    cin >> n;
    n = 2 * n + 1;
    int l = 1, r = n;
    int ql, qr, m;
    while (l <= r) {
        int mid = l + r >> 1;
        if ((query(1, mid) & 1) ^ (mid & 1)) { qr = mid; r = mid - 1; }
        else l = mid + 1;
    }
    l = 1, r = n;
    while (l <= r) {
        int mid = l + r >> 1;
        int d = n - mid + 1;
        if ((query(mid, n) & 1) ^ (d & 1)) { ql = mid; l = mid + 1; }
        else r = mid - 1;
    }
    l = ql + 1, r = qr - 1;
    if (l == r) { print(ql, l, qr); return; }
    while (l <= r) {
        int mid = l + r >> 1;
        int d = mid - l + 1;
        if ((qry(l, mid, ql, qr) & 1) ^ (d & 1)) { m = mid; r = mid - 1; }
        else l = mid + 1;
    }
    print(ql, m, qr);
}

int main() {
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}

数组长度不超过$2001$，一次二分最多询问$11$次，三个位置合计不超过$33$次。最后一段只有一个位置时可以直接确定，不需要继续询问。

例题五：Codeforces 2196C2 Interactive Graph

题目链接：Codeforces 2196C2 Interactive Graph

评测机保存了一个$n$个点、$m$条边的有向无环图。所有路径按照顶点序列的字典序排列，每次可以询问第$k$条路径，需要在$n+m$次询问内还原整张图。

对于顶点$v$，设$cnt_v$为从$v$开始的路径数量。只包含$v$自己的序列也是一条路径；随后每条出边$v\to u$都可以接上任意一条从$u$开始的路径，因此：

$$
cnt_v=1+\sum_{v\to u}cnt_u
$$

图是DAG，所以这个递归一定会结束。

字典序路径可以看成对“路径前缀树”进行先序遍历。相邻两条路径 pre 与 cur 会共享一段最长公共前缀。设公共前缀长度为$t$，那么当前第一次进入的新分支对应边：

$$
cur_{t-1}\to cur_t
$$

如果顶点$cur_t$以前从未完整处理，就继续询问下一条路径；如果已经求出$cnt_{cur_t}$，说明这个顶点后面的所有路径结构都已经见过，可以直接把$k$增加$cnt_{cur_t}$，跳过整段重复后缀。

当枚举离开某个已经收集完全部出边的顶点时，再用上面的递推式计算它的 cnt。这样每次询问要么发现一条新边，要么完成一个新顶点，不会逐条走过指数级的全部路径。

点击展开完整代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
/* Fufffh */
#include <bits/stdc++.h>
using namespace std;
using i32 = int32_t; using i64 = int64_t; using i128 = __int128_t;
using u32 = uint32_t; using u64 = uint64_t; using u128 = __uint128_t;

vector<int> query(i64 k) {
    cout << "? " << k << '\n';
    fflush(stdout);
    int n; cin >> n;
    if (n == -1) exit(0);
    vector<int> p(n);
    for (int &x : p) cin >> x;
    return p;
}

void solve() {
    int n;
    cin >> n;
    int m = 0;
    vector<vector<int>> g(n + 1);
    vector<i64> cnt(n + 1, -1);
    function<void(int)> calc = [&](int v) {
        if (cnt[v] != -1) return;
        cnt[v] = 1;
        for (int u : g[v]) { calc(u); cnt[v] += cnt[u]; }
    };
    vector<int> pre = {1};
    i64 k = 2;
    while (true) {
        vector<int> cur = query(k);
        if (cur.empty()) break;
        int t = 0;
        while (t < (int)pre.size() && t < (int)cur.size() && pre[t] == cur[t]) t++;
        if (t < (int)pre.size()) calc(pre[t]);
        if (t) { g[cur[t - 1]].push_back(cur[t]); m++; }
        if (cnt[cur[t]] == -1) k++;
        else k += cnt[cur[t]];
        pre = cur;
    }
    cout << "! " << m << '\n';
    for (int v = 1; v <= n; v++) for (int u : g[v]) cout << v << " " << u << '\n';
    fflush(stdout);
}

int main() {
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}

所有从同一个顶点开始的后缀路径只会被完整展开一次，之后都通过 cnt 整段跳过。询问可以分别归到一个新顶点或一条新边上，因此总询问数不超过$n+m$。

例题六：Codeforces 2222E Seek the Truth

题目链接：Codeforces 2222E Seek the Truth

有两个隐藏整数$k,c$，其中$k\in{1,2,3}$，分别表示按位与、按位或、按位异或：

$$
k=1:\qquad f(x)=x\mathbin{\mathrm{AND}}c
$$

$$
k=2:\qquad f(x)=x\mathbin{|}c
$$

$$
k=3:\qquad f(x)=x\oplus c
$$

评测机维护一个集合$S$。我们先选择一个初始元素，之后有两类询问：把$f(x)$插入集合并返回集合大小，或者询问集合中不小于$y$的元素数量。需要在$n+3$次以内求出$k,c$。

先令初始集合为$S={0}$，再插入$f(0)$：

$$
0\mathbin{\mathrm{AND}}c=0,\qquad 0\mathbin{|}c=0\oplus c=c
$$

如果集合大小仍然为$1$，运算一定是按位与；否则运算是按位或或按位异或，并且此时$S={0,c}$。

按位与

依次插入$f(2^i)$。当$c$的第$i$位为$1$时，结果是$2^i$，集合大小增加；否则结果为$0$，集合不变。这样用$n$次询问就能恢复$c$的每一位。

按位或或按位异或

此时集合只有$0,c$。对于$y\ge1$，询问集合中不小于$y$的元素数量，结果大于$0$当且仅当$c\ge y$，因此可以在$[1,2^n-1]$中二分出$c$。

最后区分按位或与按位异或。

如果$c$不是二的幂，取$c$最低的一个$1$为$b$。按位或得到$c$，不会加入新元素；按位异或得到$c\oplus b$，它既不是$0$也不是$c$，集合大小会增加。

如果$c$是二的幂，选择另一个二进制位$b$，并插入$f(c\mathbin{|}b)$。按位或会插入$c\mathbin{|}b$，按位异或只会插入$b$。两种情况集合大小都会增加一次，但再询问集合中是否存在不小于$c\mathbin{|}b$的元素，就可以区分二者。

点击展开完整代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
/* Fufffh */
#include <bits/stdc++.h>
using namespace std;
using i32 = int32_t; using i64 = int64_t; using i128 = __int128_t;
using u32 = uint32_t; using u64 = uint64_t; using u128 = __uint128_t;

int insert(i64 x) {
    cout << "I " << x << '\n';
    fflush(stdout);
    int t; cin >> t;
    if (t == -1) exit(0);
    return t;
}

int query(i64 x) {
    cout << "Q " << x << '\n';
    fflush(stdout);
    int t; cin >> t;
    if (t == -1) exit(0);
    return t;
}

void print(int k, i64 c) {
    cout << "A " << k << " " << c << '\n';
    fflush(stdout);
}

void solve() {
    int n;
    cin >> n;
    cout << 0 << '\n';
    fflush(stdout);
    int sz = insert(0);
    if (sz == 1) {
        i64 c = 0;
        for (int i = 0; i < n; i++) {
            int t = insert(1LL << i);
            if (t > sz) c |= 1LL << i;
            sz = t;
        }
        print(1, c);
        return;
    }
    i64 l = 1, r = (1LL << n) - 1, c = 1;
    while (l <= r) {
        i64 mid = l + r >> 1;
        if (query(mid)) { c = mid; l = mid + 1; }
        else r = mid - 1;
    }
    if (c & (c - 1)) {
        i64 b = c & -c;
        print(insert(b) > sz ? 3 : 2, c);
        return;
    }
    i64 b = c == 1 ? 2 : 1;
    i64 x = c | b;
    insert(x);
    print(query(x) ? 2 : 3, c);
}

int main() {
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}

按位与分支使用$n+1$次询问。另一个分支先用一次询问排除按位与，再用$n$次二分恢复$c$；区分运算最多再用两次，总数不超过$n+3$。

常见错误与询问次数

常见错误

忘记刷新缓冲区

询问已经写进代码，却没有真正发送给评测机，程序和评测机互相等待。把“输出、换行、刷新、读入”统一放进 query，最不容易漏。

收到 -1 后继续运行

$-1$通常表示交互已经失败。继续把它当成普通回答参与计算，后面的下标与询问格式只会进一步失控。读到$-1$应立即退出。

只证明平均询问次数

评测限制看的是最坏情况。二分时应使用上取整，多个阶段的次数要相加，还要算上初始化、分类与最终验证使用的询问。

询问集合中出现重复下标

有些题要求询问的所有下标互不相同。把固定位置和二分区间拼在一起时，要先证明它们不会重叠，否则询问会被直接判为非法。

把非自适应思路用在自适应交互器上

自适应交互器不必提前固定唯一隐藏数组。最终输出以前，必须证明已有回答只对应一个合法状态，而不是只构造出其中一种可能。

按普通题方式读取全部输入

交互样例只是一次对话记录，不能把评测机后续回答当成开局就存在的完整输入。每个回答都必须在对应询问输出以后再读取。

忽略题目归档后的非交互版本

Codeforces等平台会为交互题提供 Hacks 格式，归档后也可能要求提交读取隐藏数据的非交互版本。本文完整代码对应原始交互协议，用于理解交互解法；实际提交以前应再次检查当前页面要求的输入格式。

询问次数与普通复杂度

交互题通常同时分析两个量：程序自身的运行复杂度，以及与评测机通信的询问次数。后者往往更加严格。

例题 询问次数 程序自身的主要复杂度
ABC269 E $O(\log n)$ $O(\log n)$
ABC313 D $n$ $O(nk)$
洛谷 P14843 $73$ $O(1)$
CF2219B2 $O(\log n)$，且不超过$33$ $O(n\log n)$输出量
CF2196C2 不超过$n+m$ $O(n(n+m))$
CF2222E 不超过$n+3$ $O(n)$

交互题真正要优化的并不一定是计算量，而是每次通信能排除多少状态。先把回答写成数学关系，再考虑二分、异或、奇偶性或特殊输入，通常比直接尝试猜答案更容易找到突破口。