CF1438F Olha and Igor

交互题。
给定一棵深度为 h 的满二叉树,则其恰好有 2h1 个节点。你可以进行以下询问不超过 n+420 次:
选择三个互不相同的点 u,v,w,交互库将回答以 w 为根的时候,u,vlca
你需要回答原树的根。
3h18

Solution

为什么交互题都是神仙乱搞题啊......

首先上述的询问以 w 为根的时候 u,vlca 是在瞎扯,考虑一下 lca 的意义,实际上这个点就是距离 u,v,w 三个点距离和最小的点。

那么假设一个点作为根的时候,其三个儿子大小分别为 s1,s2,s3(若本就是原树的根或叶子则不足的补 0)。那么询问回答这个点的方案数有:

s1×s2×s3+s1×s2+s2×s3+s1×s3

也就是当询问的三个点分别在三个子树内,或其中有一个是该点本身的所有方案数。

设原树根是 rt,其两个儿子分别为 a,b,我们可以来算算 a,b 作为答案的方案数。

cnta2h2×2h2×2h1+2h2×2h1+2h2×2h2+2h1×2h2

那么如果所有方案数等概率出现,那么回答为 ab 的概率应该约等于:

cnta23h

这个东西在 3h18 的时候,最小也是 15 左右。在所有 2h1 个节点中,他们两个作为回答的概率竟然都高达 15,所以考虑随机化算法。

随机 420 组询问,将所有点作为回答的次数记录下来。取出出现次数最多的两个,我们认为他们两个就分别是 rt 的儿子,记他们分别是 p1,p2。那么对于所有 x,询问 (p1,p2,x),若回答正好是 x,则 x 是根。

至于证明最大的两个都是 rt我也不会 可以考虑算出根两个儿子的一共四个儿子作为回答的概率,通过上述算法可得大概在 110 左右,那么剩下所有点作为回答的概率之和大概为 15

假设这四个点中有一个成为了前二大,只需要四个点中有一个比根节点某一个儿子出现次数多即可,设这两个点分别出现 p,q 次,那么这样的概率是:

p>q(110)p(15)q(710)420pq(420p,q)

这个东西通过电脑计算,概率大概在 7×104 的样子?这还是十分不准确的估计,实际概率应该更小吧。

所以直接随机 420 组,得到 p1,p2 再对每个点询问即可。时间复杂度 O(2h)

标签: 交互, 随机化, 概率

添加新评论