D1T2

览遍千秋 · 2024-02-27 14:13:12 · 题解

本题解为官方题解。

首先，证明一个结论：对于任意的 a < b < c。都有 a \oplus c > \min(a \oplus b , b \oplus c)。

证明：假设 a 与 c 二进制表示中 a 与 c 不一样的最高位为第 i 位，由 a < c 可知 a 这一位为 0，c 这一位为 1。由 a < b < c 可知 b 在高于第 i 位的每一个二进制位一定与 a 和 c 一样。若 b 的第 i 为为 0，则 a 与 b 二进制表示不一样的最高位低于第 i 位，即 a \oplus b < a\oplus c。同理，如果 b 的第 i 位为 1，那么则有 b \oplus c < a\oplus c。将两种情况总结即可得到 a \oplus c > \min(a \oplus b , b \oplus c)。

根据上面的结论即可得到，一个集合中任意两个正整数的异或的最小值一定出现在集合中大小关系上相邻的两个数之间。

于是，将集合 S 中所有元素从小到大排序得到数组 a，此问题则等价于将数组 a 划分为两个非空子序列 b_1 , b_2，使得 b_1 中任意两个相邻元素的异或大于等于 k_1，且 b_2 中任意两个相邻元素的异或大于等于 k_2 的方案数。

考虑使用动态规划解决此问题：将数组 a 中每个正整数从前向后依次添加到数组 b_1 或数组 b_2 中。设 dp_{i,j} 表示子序列 b_1 末尾元素为 a_i，且子序列 b_2 末尾元素为 a_j 时的方案数。当添加一个数组 a 中的元素到数组 b_1 或 b_2 中时，枚举所有的 (i,j) 并判断是否满足异或限制的条件进行转移。这样即可得到一个 O(n^3) 的动态规划做法，但无法通过此题。

考虑优化上述动态规划做法：由于插入数组 a 中第 i (i > 1)个正整数时，两个子序列 b_1 , b_2 中一定刚好有一个子序列末尾为 a_{i-1}。于是可以用一个 0/1 变量记录 b_1 , b_2 中哪个子序列末尾为第 i-1 个元素，并记录另一个子序列末尾的位置，将时间复杂度优化到 O(n^2)。但仍然无法通过此题。

继续优化上述做法：对于数组 b_1 的末尾为数组 a 第 i-1 个数的情况，将数组 b_2 末尾所有可能的数和对应的方案数插入到一个字典树中。对于数组 b_2 的末尾为数组 a 第 i-1 个数的情况，将数组 b_1 末尾所有可能的数和对应的方案数插入到另一个字典树中。将数组 a_i 个数插入到 b_1 , b_2 中的一个数组时，讨论 a_{i-1} 此时的位置在 b_1 . b_2 哪个数组的末尾，分四种情况讨论转移。单次转移即为查询字典树中所有与 a_i 异或不超过 k_1 或 k_2 的数的总数。单次查询可以在 O(\log(\max(a))) 时间内做到。

总时间复杂度和空间复杂度均为 O(n \cdot \log(\max(a)))。