CF1864E Guess Game

发布时间 2023-09-11 15:33:39作者: FOX_konata

原题

翻译

非常好的一道题,不过前半部分的逻辑推理比较难理解,这很博弈

由于或运算是有\(1\)就为\(1\),因此我们对于一对数\((a,b)\),我们不需要看\(a|b\)中为\(0\)的那些位,因此我们只需要考虑\(a|b\)\(1\)的情况即可

我们考虑一下如果\(Alice\)说"我不知道"说明什么?说明在\(a\)\(b\)的二进制表示下,\(a\)最高位为\(1\)。否则如果\(a\)最高位为\(0\),则\(b\)最高位一定为\(1\),因此\(Alice\)一定可以推断出\(a < b\)

同理的,在第二轮\(Bob\)这里如果\(b\)的最高位为\(0\),那他可以直接推断出\(a > b\),因此如果\(Bob\)说"我不知道"说明\(b\)的最高位也为\(1\)。但是我们还要多考虑一点,如果\(b\)的最高位为\(1\)但次高位为\(0\),那\(Bob\)也可以推断出\(a > b\),因为\(b\)的次高位为\(0\)就说明\(a\)的次高位一定为\(1\),也可以推断\(a > b\)。因此如果\(Bob\)说"我不知道",就把\(b\)的最高位和次高位都为\(1\)的信息告诉了\(Alice\)

第三轮同理,\(Alice\)也可以判断\(a,b\)的大小关系,或通过说"不知道"来告诉\(Bob\) \(a\)的次高位和次次高位为\(1\)……如此反复,直到一个人找到一位使得\(a,b\)中有一个数为\(0\),或判断\(a=b\)

在发现这样的逻辑后,我们就可以通过\(a\)\(b\)对每一位二进制枚举来求出操作轮数。

\[\begin{cases} a=b & popcnt(a)+1 \\ a<b & x + [x \mod 2 = 0] \\ a>b & x + [x \mod 2 = 1] \\ \end{cases} \]

其中\(x\)表示\(a\ and\ b\)在二进制下最高位\(0\)的位置(肯定是不算前导\(0\)的),\(popcnt(x)\)表示\(x\)二进制下\(1\)的个数

于是我们就可以得到一个\(O(n^2 \log V)\)的一个做法:暴力枚举选哪两个数,然后在对他们的二进制暴力找到\(x\)


方法1:\(01trie\)

显然看到二进制的题我们首先能想到\(01trie\)这个东西

我们把所有的数都加入\(01trie\)中,枚举一个数\(s_i\)作为被选择的\(a\),然后看有多少个\(b\)满足\(b<a\),然后计算答案即可


方法2: 分治

对于二进制按位贪心的题我们也可以考虑分治。与其说是分治,不如说是一种\(01trie\),但他的特点是没有把树真正的建出来,而是用递归树来代替

我们对于所有的\(s_i\)从高位往低位考虑,对于当前这一位,我们把它分成这一位为\(0\)\(1\)的部分,分别递归计算贡献,在合并的时候这一位为\(0\)的显然能对为\(1\)的产生贡献

最后再除以总方案数极为要求的答案