跳转至

按位分治⚓︎

按位分治（\text{Bitwise Divide and Conquer}）是一种基于二进制表示的分治算法。它通过逐位处理整数的二进制位，从最高位到最低位，将问题划分为更小的子问题进行求解。按位分治常用于解决涉及整数集合的最大异或值、最小异或值等问题。

一般思路如下：

  1. 选择位数：从最高有效位（\text{MSB}）开始，逐位向下处理整数的二进制表示。
  2. 划分集合：根据当前处理的位，将整数集合划分为两部分：一部分是该位为 0 的整数，另一部分是该位为 1 的整数。
  3. 递归求解：对于划分后的子集合，递归地处理下一位，直到处理完所有位或子集合为空。
  4. 合并结果：根据子集合的结果，合并得到最终结果。
最大异或对

给定 n 个非负整数，求其中两个数的异或值的最大值。

C++
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int solve(const vector<int> &nums, int l1, int r1, int l2, int r2, int bit) {
  if (bit < 0 || l1 >= r1 || l2 >= r2) { return 0; }
  int m1 = l1;  // [l1, m1) 当前位为0, [m1, r1) 当前位为1
  while (m1 < r1 && ((nums[m1] >> bit) & 1) == 0) { m1++; }
  int m2 = l2;  // [l2, m2) 当前位为0, [m2, r2) 当前位为1
  while (m2 < r2 && ((nums[m2] >> bit) & 1) == 0) { m2++; }
  int ans = 0;
  // 左0右1 和 左1右0能产生 1, 肯定比不产生1的大
  if ((l1 < m1 && m2 < r2) || (m1 < r1 && l2 < m2)) {
    ans = (1 << bit);
    // 同一个区间划分, 两种情况等价
    if (m1 == m2) { return ans + solve(nums, l1, m1, m2, r2, bit - 1); }
    // 不同区间划分, 选择组合的最大值
    return ans + max(solve(nums, l1, m1, m2, r2, bit - 1), solve(nums, m1, r1, l2, m2, bit - 1));
  }
  // 不能产生1，递归同位组合
  if (l1 < m1 && l2 < m2) { ans = max(ans, solve(nums, l1, m1, l2, m2, bit - 1)); }
  if (m1 < r1 && m2 < r2) { ans = max(ans, solve(nums, m1, r1, m2, r2, bit - 1)); }
  return ans;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n;
  cin >> n;
  vector<int> nums(n);
  for (int i = 0; i < n; ++i) { cin >> nums[i]; }
  // 先排序，使得相同bit划分后能原地递归
  sort(nums.begin(), nums.end());
  cout << solve(nums, 0, n, 0, n, 30) << "\n";
  return 0;
}
Sum of Min of XOR

给定 n 个非负整数，以及一个整数 m。求 \sum_{i=0}^{m-1} \text{minXOR}(i)，其中 \text{minXOR}(i) 表示从给定整数集合中选择一个整数与 i 异或得到的最小值。

Hint

当前考虑第 k-1 位，将 A 划分为两个子集：

B_0 = \{ a \in A \mid a < 2^{k-1} \}

B_1 = \{ a - 2^{k-1} \mid a \in A, a \ge 2^{k-1} \}

情况 1：M = 2^k （完整区间）

  1. B_0 和 B_1 都非空：f(A, 2^k, k) = f(B_0, 2^{k-1}, k-1) + f(B_1, 2^{k-1}, k-1)

  2. 只有 B_0 空：f(A, 2^k, k) = 2 \cdot f(B_1, 2^{k-1}, k-1) + 2^{2(k-1)}

  3. 只有 B_1 空：f(A, 2^k, k) = 2 \cdot f(B_0, 2^{k-1}, k-1) + 2^{2(k-1)}

跨组贡献：最高位异或为 1 的情况，每对贡献 2^{k-1}。

情况 2：M \le 2^{k-1} （只在左半区间）

  1. 如果 B_0 为空：f(A, M, k) = f(B_1, M, k-1) + M \cdot 2^{k-1}

  2. 如果 B_1 为空：f(A, M, k) = f(B_0, M, k-1)

如果某一侧为空，所有 x 必然选择另一侧 \longrightarrow 贡献当前位。

情况 3：2^{k-1} < M < 2^k （跨两半区间）

将 x 拆分为两个范围：

  1. 左半区（0 \le x < 2^{k-1}）：\begin{cases} f(B_1, 2^{k-1}, k-1) + 2^{k-1}, & B_0 \text{ 为空} \\ f(B_0, 2^{k-1}, k-1), & \text{否则} \end{cases}

  2. 右半区（2^{k-1} \le x < M）：\begin{cases} f(B_0, M-2^{k-1}, k-1) + 2^{k-1} \cdot (M-2^{k-1}), & B_1 \text{ 为空} \\ f(B_1, M-2^{k-1}, k-1), & \text{否则} \end{cases}

最终答案 = 左半区贡献 + 右半区贡献。

C++
#include <algorithm>
#include <cstdint>
#include <iostream>
#include <vector>
using namespace std;

int64_t dfs(const vector<int> &arr, int64_t m, int bit) {
  if (bit < 0) { return 0; }
  vector<int> a0, a1;  // a0: 当前位为0的数, a1: 当前位为1的数
  for (int x : arr) {
    if (((x >> bit) & 1) != 0) {
      a1.push_back(x);
    } else {
      a0.push_back(x);
    }
  }
  // 将 m 分成两部分: [0, half), [half, m)
  int64_t half = 1LL << bit;
  if (m == (1LL << (bit + 1))) {       // 完整对称区间
    if (!a0.empty() && !a1.empty()) {  // (1)!
      return dfs(a0, half, bit - 1) + dfs(a1, half, bit - 1);
    }
    return 2 * dfs(arr, half, bit - 1) + half * half;  // (2)!
  }
  int64_t res = 0;
  // [0, half) 处理左半部分
  if (!a0.empty()) {  // (3)!
    res += dfs(a0, min(m, half), bit - 1);
  } else {  // (4)!
    res += dfs(arr, min(m, half), bit - 1) + half * min(m, half);
  }
  // [half, m) 处理右半部分
  if (m > half) {       // 对应区间变为 [0, m - half)
    if (!a1.empty()) {  // (5)!
      res += dfs(a1, m - half, bit - 1);
    } else {  // (6)!
      res += dfs(arr, m - half, bit - 1) + half * (m - half);
    }
  }
  return res;
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n, m;
  cin >> n >> m;
  vector<int> nums(n);
  for (int i = 0; i < n; ++i) { cin >> nums[i]; }

  cout << dfs(nums, m, 30) << "\n";
  return 0;
}

  1. a_0 和 a_1 都不为空，则 [0,m) 区间内的每个数都可以选择和高位相同的数进行异或，当前位贡献为 0
  2. 若 a_0 为空，则 [0, \text{half}) 区间内的数都必须和 a_1 中的数异或，当前位贡献为 \text{half}，共 \text{half} 个数；a_1 同理。然后分别处理左右对称两半区间（\times 2）
  3. [0, \text{half}) 区间内的数可以和当前位相同的数进行异或，当前位贡献为 0
  4. [0, \text{half}) 区间内的数只能和当前位不同的数异或，当前位贡献为 half，共 \min(m, half) 个数
  5. [half, m) 区间内的数可以和当前位相同的数进行异或，当前位贡献为 0
  6. [half, m) 区间内的数只能和当前位不同的数异或，当前位贡献为 half，共 m - half 个数

评论