【题解】CF1438F Olha and Igor
CF1438F Olha and Igor
交互题。
给定一棵深度为的满二叉树,则其恰好有 个节点。你可以进行以下询问不超过 次:
选择三个互不相同的点,交互库将回答以 为根的时候, 的 。
你需要回答原树的根。。
为什么交互题都是神仙乱搞题啊......
首先上述的询问以
那么假设一个点作为根的时候,其三个儿子大小分别为
也就是当询问的三个点分别在三个子树内,或其中有一个是该点本身的所有方案数。
设原树根是
那么如果所有方案数等概率出现,那么回答为
这个东西在
随机
至于证明最大的两个都是 我也不会 可以考虑算出根两个儿子的一共四个儿子作为回答的概率,通过上述算法可得大概在
假设这四个点中有一个成为了前二大,只需要四个点中有一个比根节点某一个儿子出现次数多即可,设这两个点分别出现
这个东西通过电脑计算,概率大概在
所以直接随机