题意：交互题。给出一棵树的点数 $n$，你每次询问可以给出一个点集 $S$ 和一个点 $x$，可以得到 $x$ 是否在点集 $S$ 的最小连通块中，需要还原出树。$n = 1000$，你最多可以询问 22000 次。求构造方案。
这个题的做法有很多，我们切入一个比较简单并且易懂的角度。
首先我们考虑如果我们已经知道了这棵树的拓扑序后怎么做。注意此时我们需要定义一个根，然后每条边从儿子指向父亲。简单来说就是父亲的拓扑序在儿子的后面。
注意到我们在拓扑序上枚举到了 $x$，我们求它的所有后代。容易发现它的所有后代都是在它前面的，并且除了 $x$ 的儿子以外，其他的点都已经被这种方式覆盖过了。这给我们一个区分儿子和后代的办法：拿到所有的后代后，直接在拓扑序中把这些点删除，这样后面就不会再遍历到这些点了。那么我们就可以保证，现在拿到的所有的点都满足是 $x$ 的儿子。这样做下去，容易发现询问复杂度是 $O(n\log n)$ 的，因为遍历到一个点就会把他删除，遍历到点的过程可以二分查找前半段是否存在 $x$ 的后代，所以就是 $O(n\log n)$ 的。
那么现在问题就转化成了求树的拓扑序。假设我们当前 $S$ 集合里面的点都没有放进拓扑序，我们要把 $x$ 子树内全部放进去。做法比较神秘，我们考虑找到一个 $S$ 内部并且在 $x$ 子树内部的点 $y$，然后先将 $y$ 子树内部的点放进拓扑序（注意到 $y$ 子树内部的点一定在 $x$ 前面），$S$ 集合对应更新。我们这样做的话，显然是一定会把 $x$ 子树内部的所有点全部都放进拓扑序。最后放 $x$，这样的话就可以完成构造拓扑序。
考虑分析一下上述算法的复杂度。注意到每一个 $x$ 都只会被遍历一次（不挂其子树内是什么），找到一个 $x$ 的后代的过程同样可以二分，于是询问复杂度也是 $O(n\log n)$ 的。
综上，我们可以在询问复杂度 $O(n\log n)$ 的时间内完成，时间复杂度可以较容易地做到 $O(n ^ 2)$。
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
| void del(int x) {
for (int i = 0; i < (int) s.size(); ++ i)
if (s[i] == x) return s.erase(s.begin() + i), void();
}
bool query(std::vector<int> s, int x)
{
s.push_back(1);
return ask(s, x);
}
void solve(int x)
{
del(x);
while (s.size() && query(s, x))
{
int l = 1, r = s.size();
while (l < r) {
int mid = (l + r) >> 1;
if (query({s.data(), s.data() + mid}, x)) r = mid;
else l = mid + 1;
}
int y = s[l - 1];
solve(y);
}
ord.push_back(x);
}
std::vector<std::pair<int, int>> work(int n)
{
std::vector<std::pair<int, int>> res;
for (int i = 0; i < n; ++ i) s.push_back(i + 1);
solve(1);
std::vector<int> vec;
for (int i = 0, x; i < n; ++ i)
{
x = ord[i];
while (vec.size() && query(vec, x)) {
int l = 1, r = vec.size();
while (l < r) {
int mid = (l + r) >> 1;
if (query({vec.data(), vec.data() + mid}, x)) r = mid;
else l = mid + 1;
}
res.push_back({x, vec[l - 1]}), vec.erase(vec.begin() + l - 1);
}
vec.push_back(x);
}
return res;
}
|