Strange device
题目大意
这是一道交互题，你需要猜出一个 \(n\) 个点的树。
你可以作出 \(\leq 80\) 次如下询问：
给交互库一个序列 \(d_1,d_2, \ldots, d_n\)，交互库会返回一个 01 串，表示对于每一个节点 \(i\) 是否存在节点 \(j\ (i \neq j)\) 使得 \(dis(i,j) \leq d_j\)。
\(2 \leq n \leq 1000\)
题解
遇到这种题一般的套路是先确定每个点在整个树中的位置然后再具体确定父子关系，因为往往你能做的操作只能得出祖先关系。
所以我们先考虑怎么求出一个点的深度。
如何求出深度
可以考虑一个分治的过程，先假定 \(1\) 为根，会好做一点。
可以先求出所有距离 \(1\) 大于 \(\frac{n}{2}\) 的点，等于 \(\frac{n}{2}\) 的点，小于 \(\frac{n}{2}\) 的点。
具体的，我们做两次询问，第一次 \(d_1=\frac{n}{2}\) 其余为 \(0\)，第二次 \(d_1=\frac {n}{2} - 1\) 其余为 \(0\)。
对这个做法推而广之，对于每个子区间我们都可以这样对其求出具体的一个新的深度的点击，并且将其分为两个本质相同的子问题。
但是我们这样对题目的条件使用率太低了，也无法完成他题目中询问次数的限制。
于是我们考虑将同一层的询问合并。
由于对于一个点询问可能会影响到上方的点，又因为每次询问的距离大约为一半的区间长度，所以我们可以将奇数下标的区间合并到一个询问，将偶数下表的区间合并到一个询问，这样每个询问之间就不会互相影响了。
如何求出父子关系
考虑拆位，如果我们将深度为 \(d\) 的第 \(k\) 位为 \(1\) 的点都设为 \(1\) 其余设为 \(0\)，那么深度为 \(d+1\) 的点在结果中的值就是其父亲第 \(k\) 位的值。
正确性显然。
且这种询问方法只影响到 \(d - 1,d,d + 1\) 深度的点，所以我们可以将所有 \(\mod{3}\) 同余的点塞入同一个询问中。
总结
求出深度需要用 \(4 \log n\) 次询问，求出父子关系需要用 \(3 \log n\) 次询问。
总的需要 \(7 \log n\) 次询问，时间复杂度为 \(\mathcal{O}(n \log n)\)。
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int n, head[N], nxt[N * 2], to[N * 2], tot;
void add(int x, int y) { nxt[++ tot] = head[x]; head[x] = tot, to[tot] = y; }
vector<int> curd;
bool dfs(int x, int fa, int dis) {
if (dis <= curd[x]) return true;
for (int i = head[x]; i; i = nxt[i]) {
int y = to[i];
if (y != fa && dfs(y, x, dis + 1)) return true;
}
return false;
}
vector<int> interact(vector<int> d) {
assert(d.size() == n + 1);
#ifdef LOCAL
curd = d;
vector<int> v(n + 1);
for (int i = 1; i <= n; i ++) v[i] = dfs(i, i, 0);
return v;
#else
for (int i = 1; i <= n; i ++) printf("%d%c", d[i], " \n"[i == n]);
fflush(stdout);
vector<int> v(n + 1);
for (int i = 1; i <= n; i ++) scanf("%d", &v[i]);
return v;
#endif
}
void init_local() {
for (int i = 1, x, y; i < n; i ++) scanf("%d%d", &x, &y), add(x, y), add(y, x);
}
struct Node { int l, r, mid; };
vector<int> d[N];
vector<Node> t[N];
int mtier;
void build(int tier, int l, int r) {
if (r - l + 1 <= 2) return;
mtier = max(mtier, tier);
int mid = (l + r) >> 1;
t[tier].push_back({ l, r, mid });
build(tier + 1, l, mid);
build(tier + 1, mid, r);
}
int main() {
scanf("%d", &n);
#ifdef LOCAL
init_local();
#endif
build(1, 0, n);
d[0].push_back(1);
for (int tier = 1; tier <= mtier; tier ++) {
vector<pair<int, int>> query[2];
for (int i = 0; i < t[tier].size(); i ++) {
int l = t[tier][i].l, r = t[tier][i].r, mid = t[tier][i].mid;
query[i % 2].push_back({ l, mid - l });
}
for (int type : { 0, 1 }) {
vector<int> q(n + 1);
for (auto p : query[type]) q[p.first] = p.second;
vector<int> fq = interact(q);
for (int i = 1; i <= n; i ++) if (q[i]) -- q[i];
vector<int> sq = interact(q);
vector<int> type1;
for (int i = 1; i <= n; i ++) {
}
}
}
return 0;
}