题解：CF1438F Olha and Igor

· · 题解

Olha and Igor

题目链接。cnblogs。

Problem

给定一个高度为 h 的完美二叉树（恰好有 n = 2^h-1 个节点）。

你可以进行以下询问至多 n+420 次。

你需要向交互库回答根的编号。

数据范围：3 \le h \le 18。

Sol

先想想不要询问次数限制怎么做。显然可以枚举点 w。然后随机 u, v 把它们变成 lca。最后判断根节点的度数即可 。但这是 \mathcal{O}(n^2) 次询问。发现 h 竟然 \ge 3，甚至是完全二叉树！。不妨一些限制更弱的、较随机做法。发现 (u, v, w) 得到点 x 是使得 d(u, x) + d(v, x) + d(w, x) 最小的 x。回答为点 u 的方案数为 (s_1+1)(s_2 + 1)(s_3 + 1)，其中 s_1, s_2, s_3 表示点 u 的三棵子树的大小。随机 420 次 (u, v, w)。然后得到概率最大的一定是根的左右儿子。这个东西在 h=18 时，正确概率为 18\%。所以随机出来的概率还是很大的。最后直接枚举根 x，看 (u, v, x) 的回答是不是 x 即可。

Code

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
mt19937_64 orz(time(0) ^ clock());
int rnd(int l, int r) { return orz() % (r - l + 1) + l; }
int h;
int Ask(int u, int v, int w) {
    printf("? %d %d %d\n", u, v, w);
    fflush(stdout);
    int res;
    scanf("%d", &res);
    return res;
}
void Ans(int x) { printf("! %d\n", x); fflush(stdout); }
pii buc[1000005];
int main() {
    cin >> h;
    int n = (1 << h) - 1;
    for (int i = 1; i <= n; ++i) buc[i].second = i;
    for (int i = 1; i <= 422; ++i) {
        int u = rnd(1, n), v = rnd(1, n), w = rnd(1, n);
        while (u == v) v = rnd(1, n);
        while (w == u || w == v) w = rnd(1, n);
        int ret = Ask(u, v, w);
        ++buc[ret].first;
    }
    sort(buc + 1, buc + n + 1, greater<pii>());
    int u = buc[1].second, v = buc[2].second;
    for (int i = 1; i <= n; ++i) {
        if (i == u || i == v) continue;
        int ret = Ask(u, v, i);
        if (ret == i) return Ans(i), 0;
    }
    return 0;
}