CF2001C 题解

Wuming_Shi · 2024-09-18 14:59:49 · 题解

CF2001C 题解

题意

交互题。有一颗 n 个节点的树，要确定树的形状。每次可以询问两个点 a,b，交互库会返回 a,b 路径上的中点（如果点数为偶数则返回更靠近 a 的）。最多询问 15n 次（n\le1000）。

思路

函数 query(int a,int b) 表示处理点 a 到点 b 的路径。

可以设某个点为树根，每次询问树根与一个未被标记的点 。然后递归处理：

先把询问的 b 点标记，并得到中点 x。现在需要处理 x 到 b 的路径和 a 到 x 的路径。

对于前者，直接递归下去即可。

对于后者，分类讨论一下：若 x 已被标记，说明 x 到根上的路径已经被确定，不需要处理；如果未被标记，则递归处理 a 到 x 的路径。

递归的终止条件为询问的点 a 与得到的点 x 相同（因为这时询问的 a,b 两点相邻），此时要把 a,b 连边。

最后输出这些边即可。

代码

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 2010;
int t, n;
typedef pair<int, int> PII;
vector<PII> ans;
bool vis[MAXN];

void query(int a, int b) {
    vis[b] = 1;
    cout << "? " << a << " " << b << endl;
    cout.flush();
    int mid; cin >> mid; //中点
    if (mid == a) { //中点与a重合，递归终止
        ans.push_back({a, b});
        return;
    }
    if (!vis[mid]) query(a, mid); //处理a到中点的路径
    query(mid, b); //处理中点到b的路径
}

void solve() {
    cin >> n;
    for (int i = 2; i <= n; i++) {
        if (!vis[i]) { //选取未被标记的点
            query(1, i);
        }
    }
    cout << "! ";
    for (PII i : ans) { //输出答案
        cout << i.first << " " << i.second << " ";
    }
    cout << endl;
    cout.flush();
}

void init() {
    for (int i = 1; i <= n; i++) {
        vis[i] = 0;
    }
    ans.clear();
}

int main() {
    cin >> t;

    while (t--) {
        solve();
        init();
    }

    return 0;
}