Olha and Igor

Problem

给定一个高度为

h

的完美二叉树（恰好有

n = 2^h-1

个节点）。

你可以进行以下询问至多

n+420

次。

选择三个互不相同的点 $u,v,w$ ，你需要保证 $1\leq u,v,w\leq n$ 。
交互库会返回当以 $w$ 为根时 $u$ 与 $v$ 的 lca。

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

数据范围：

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

CPP

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

题解：CF1438F Olha and Igor

文章操作

Olha and Igor

Problem

Sol

Code

相关推荐

评论

题解：CF1438F Olha and Igor