[湖北省选模拟 2024] 花神诞日 / sabzeruz 题解

· · 题解

分享一下考场上的笨比分讨做法。

首先不妨设 k_1 \ge k_2，同时规定 trie 树上的根深度为 59，叶子深度为 -1。

同时为了方便计算，我们将空集也算入合法答案，在最后再减去。

首先把所有数插入到 trie 树上，注意到在深度为 \operatorname{highbit}(k_1) 的点的子树内 k_1 最多选择一个点进入 S_1 集合。

所以这启发我们对 \operatorname{highbit}(k_1) 与 \operatorname{highbit}(k_2) 的关系进行讨论。

  1. 当 \operatorname{highbit}(k_1) = \operatorname{highbit}(k_2) 时。

注意到此时深度为 \operatorname{highbit}(k_1) 的子树大小最多为 4，否则答案一定为 0，那么我们直接暴力即可。

  1. 当 \operatorname{highbit}(k_1) \not = \operatorname{highbit}(k_2) 时。

记当前考虑的深度为 \operatorname{highbit}(k_1) 的点为 x。

我们发现 x 的两个子树之间的选择对于 S_2 是独立的，因为 \operatorname{highbit}(k_1) > \operatorname{highbit}(k_2)，所以说之间的最小异或值一定不小于 k_2。

那么问题就变成了两个子树中都有一些点使得选出他之后剩下的点不冲突（xor \ge k_2），然后我们要在两个点集中分别选出最多一个点，使得他们之间的 xor \ge k_1。

如果我们求出了点集，那么后面那个东西是简单的。

求出点集则需要进一步讨论。

还是一样的办法，找到深度为 \operatorname{highbit}(k_2) 的点，记他为 u。

如果 u 的一个儿子大小 \ge 2 一定答案为 0。

如果 u 一个儿子大小为 2 则我们有必选限制，既两个点 S_1 中一定选一个。

那么现在没有必选限制，那么子树大小一定 =2。

然后如果左右子树异或 \le k_2，一定要选走一个数，这也是一个必选限制。

显然如果有多个必选限制答案一定为 0。

然后就做完了。

时间复杂度 \mathcal{O}(n \log n)。

代码（很丑，仅供参考）