欢迎前往 我的博客 获得也许更好的阅读体验！
题意简述
这是一个交互式问题。
Misuki 选择了一棵有 \(n\) 个节点的秘密树，节点编号为 \(1\) 到 \(n\)，并要求你通过以下类型的查询来猜出这棵树：
“? a b” — Misuki 会告诉你哪个节点 \(x\) 最小化了 \(|d(a,x) - d(b,x)|\)，其中 \(d(x,y)\) 是节点 \(x\) 和节点 \(y\) 之间的距离。如果有多个这样的节点，Misuki 会告诉你其中使 \(d(a,x)\) 最小的那个节点。
使用最多 \(15n\) 次查询来找出 Misuki 的秘密树的结构！
思路分析
首先，通过分析题目我们容易知道，返回的 \(x\) 实际上是 \(a\) 与 \(b\) 的中间节点。
如果查询 ? a b 的返回值为 a，那么表明 \(a\) 与 b 之间通过一条边直接相连。
否则再次查询 ? a x 以及 ? x+1 b直到找到相邻的边。
如果设在此树上 \(a\) 与 \(b\) 之间的距离为 \(l\)，那么此次操作至多询问 \(l-1\) 次。
为了减少查询次数，引入并查集来维护已经连通的节点。
每次查询的两个节点应处于两个不同的连通块，查询后将它们合并起来。
对每一个节点都查一遍与节点 \(1\) 之间的通路即可。
对于这种解法，操作次数最多的树的结构为链状，且节点编号依次为 \(1,2,\cdots,i,\cdots,n\)。
我们首先需要 \(n-1\) 次的查询 ? 1 i 。
对于这其中的每一次 ? 1 i，前 \(i-1\) 个节点已经处于同一个连通块中，所以会花费 \(\lfloor\log_2(i-1)\rfloor +1\) 次的二分操作来不断逼近右边界。
所以总的操作次数为 \(\sum\limits_{i=2}^{n} (\lfloor\log_2(i-1)\rfloor +1)=\sum\limits_{i=2}^{n} \lfloor\log_2(i-1)\rfloor + (n-1)\)。
操作次数的上限不会超过 \(\displaystyle\sum\limits_{i=1}^{\lfloor\log_2(n-1)\rfloor} i\cdot2^{i-1}\)。
这个式子吧，我们稍微放缩一下来找一下上界。
\[\begin{align} \displaystyle\sum\limits_{i=1}^{\lfloor\log_2(n-1)\rfloor} i\cdot2^{i-1} &\leq \displaystyle\sum\limits_{i=1}^{\lfloor\log_2(n-1)\rfloor} \lfloor\log_2(n-1)\rfloor\cdot2^{i-1} \\ & = \lfloor\log_2(n-1)\rfloor\cdot\displaystyle\sum\limits_{i=1}^{\lfloor\log_2(n-1)\rfloor} 2^{i-1}\\ &= \lfloor\log_2(n-1)\rfloor\cdot (2 ^ {\lfloor\log_2(n-1)\rfloor}-1)\\ &\leq \lfloor\log_2(n-1)\rfloor\cdot 2 ^ {\lfloor\log_2(n-1)\rfloor} \\ &\leq n \cdot \log_2 n \end{align} \]所以操作次数最多也不会超过 \(n\log_2 n\) 次。
对于 \(n \leq 1000\)，不会超过 \(10n\) 次。
绰绰有余！
代码展示
#include<bits/stdc++.h>
using namespace std;
const int maxN = 1000 + 10;
vector<int> G[maxN];
int N;
int fa[maxN];
int find(int x){
return x == fa[x] ? fa[x] : (fa[x] = find(fa[x]));
}
void dfs(int lp,int rp){
int a = find(lp);
int b = find(rp);
if(a == b) return;
cout << "? " << lp << " " << rp << endl;
cout.flush();
int x;
cin >> x;
if(x == lp){
fa[lp] = b;
G[lp].push_back(rp);
return;
}
dfs(lp,x);
dfs(x,rp);
}
inline void solve(){
cin >> N;
for(int i = 1;i<=N;i++) G[i].clear();
for(int i = 1;i<=N;i++) fa[i] = i;
for(int i = 2;i<=N;i++) dfs(i,1);
cout << "! ";
cout.flush();
for(int i = 1;i<=N;i++){
for(auto p : G[i]){
cout << i << " " << p << " ";
cout.flush();
}
}
cout << endl;
cout.flush();
}
int main(){
int T;
cin >> T;
while(T--) solve();
return 0;
}