Burnling's Blog
0%

CF2001C Guess The Tree

发表于 更新于 分类于 ，

题意简述

这是一个交互式问题。

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}$。

这个式子吧，我们稍微放缩一下来找一下上界。

所以操作次数最多也不会超过 $n\log_2 n$ 次。

对于 $n \leq 1000$，不会超过 $10n$ 次。

绰绰有余！

代码展示

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
#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;
}