3599. 划分数组得到最小 XOR

发表于 分类于 阅读次数： Waline： 本文字数： 1.4k 阅读时长 ≈ 5 分钟

考点

  • 划分DP
  • 前缀和
  • 二分

思路

划分DP

直接看代码即可，要注意这里异或值可能会非常大，0x3f3f3f3f不够用，建议直接上INT_MAX

我代码用0x7f7f7f7f发现也可以：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
 public:
  static const int inf = 0x7f7f7f7f;
  int minXor(vector<int>& nums, int k) {
    int n = nums.size(), f[300][300];
    // f[j][i]: 前i个数字划分为j个数组时的最大异或值，取最小
    // 要注意, 这里最大值有可能接近1<<30, 所以无穷取0x7f7f7f7f或者INT_MAX
    memset(f, 0x7f, sizeof(f));
    f[0][0] = 0;
    for (int j = 1; j <= k; ++j) {
      for (int r = j; r <= n; ++r) {
        int s = 0;
        for (int l = r; l >= j; --l) {
          s ^= nums[l - 1];
          if (f[j - 1][l - 1] != inf)
            f[j][r] = min(f[j][r], max(f[j - 1][l - 1], s));
        }
      }
    }
    return f[k][n];
  }
};

当然也可以滚动数组滚掉一维：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
 public:
  static const int inf = INT_MAX;
  int minXor(vector<int>& nums, int k) {
    int n = nums.size(), f[300];
    // f[j][i]: 前i个数字划分为j个数组时的最大异或值，取最小
    // 要注意, 这里最大值有可能接近1<<30, 所以无穷取INT_MAX
    for (int i = 1; i <= n; ++i) f[i] = inf;
    f[0] = 0;
    for (int j = 1; j <= k; ++j) {
      for (int r = n; r >= j; --r) {
        f[r] = inf;
        int s = 0;
        for (int l = r; l >= j; --l) {
          s ^= nums[l - 1];
          if (f[l - 1] != inf) f[r] = min(f[r], max(f[l - 1], s));
        }
      }
    }
    return f[n];
  }
};

二分+DP

本题用二分并不优，因为内部还要用一次DP，锻炼码力也可以写一下

先证明一下二分的可行性，尽管异或值本身并不单调，但二分答案根本不需要“异或值本身单调” 二分需要的是一个 布尔函数 的单调性：

F(T) = 是否存在一种划分，使得所有段的 XOR 都 ≤ T

只要能证明： 如果 F(T) = true，那对所有 T' > T 也有 F(T') = true， 那就可以二分 T。 这里的“单调性”是 F(T) 随着 T 的单调（从 false→true），跟异或怎么跳来跳去无关。

1. 命题描述

题目：给定数组 nums 和整数 k，把它划成 k 段， 每段的 XOR 记为 xor_seg_1, xor_seg_2, ..., xor_seg_k， 我们想最小化 max(xor_seg_1, ..., xor_seg_k)。

定义一个函数：

F(T) = 是否存在一种把数组划成 k 段的方案， 使得每一段的 XOR 都 ≤ T。

那么题目要找的答案就是所有满足 F(T)=true 的 T 的最小值。

二分需要的条件：

如果 F(T) = true，则对所有 T' ≥ T，F(T') 也必须是 true。

这就是所谓的“二分单调性”。

2. 证明 F(T) 的单调性（这跟 XOR 本身无关）

假设对某个 T，F(T) = true。 这意味着：存在某种划分方案 S，把数组分成 k 段：

  • 这一种方案 S 下，每一段的 XOR 都 ≤ T。

现在随便取一个更大的数 T' ≥ T。

同一套划分方案 S，所有段的 XOR 仍然是当初那几个值，没变： 它们原来 ≤ T，所以当然也 ≤ T'（因为 T' 更大）。

所以：

  • 用同一个方案 S，F(T') 也为 true。

这说明：

T 满足 ⇒ 所有更大的 T' 也满足， F 在 T 上是从 false→true 一次性跳过去，就不会来回乱跳。

你可以把这个逻辑注意一下： 我们二分的是 “允许的最大值 T 有多松”， 约束越松（T 越大），方案只会更多，不会更少。 这个跟“异或值自己是不是递增”一点关系都没有。

3. 举例

比如数组 nums = [1, 2, 3]，k = 2。 我们可以列一下所有划分方案和它们的 “最大 XOR”：

  1. [1] | [2,3]
    • XOR: 1 和 2^3=1，max = 1
  2. [1,2] | [3]
    • XOR: 1^2=3 和 3，max = 3

所以所有可能的“最大 XOR”是 {1, 3}，答案是 min{1,3} = 1。

现在看 F(T)：

  • T = 0： 没有任何划分方案能让所有段 XOR ≤ 0 ⇒ F(0) = false
  • T = 1： 方案 1 里 max XOR = 1 ≤ 1 ⇒ F(1) = true
  • T = 2： 方案 1 里 max XOR = 1 ≤ 2 ⇒ F(2) = true
  • T = 3： 方案 1、2 都可以 ⇒ F(3) = true

所以：

1
2
T:    0  1  2  3 ...
F(T): 0  1  1  1 ...

这就是典型的 0,0,...,0,1,1,1,1... 的模式，可以二分

二分的思路如下：

二分主体思路

我们现在要二分的是一个上界 limit：

1
F(limit) = 是否存在一种把数组划分成恰好 k 段的方案，使得每一段的 XOR 都 ≤ limit

如果 F(limit) 为真，那么同一套划分在更大的 limit' 下也一定合法，所以：

1
F(limit) = true  ⇒  对所有 limit' ≥ limit, F(limit') 也为 true

这个布尔函数对 limit 是单调的，可以二分

二分区间可以取：

  • lo = 0
  • hi = (1 << 30) - 1 （因为 nums[i] ≤ 1e9 < 2^30，任何子数组 XOR 都 < 2^30）

编写 check(limit)

用一个布尔 DP：

  • dp[i][c]：前 i 个数（nums[0..i-1]）能不能被划分成恰好 c 段，且每一段的 XOR 都 ≤ limit

初始条件：

  • dp[0][0] = true
  • dp[0][c>0] = false

转移：

  • 让最后一段是 [l .. i-1]（1-based 就是 [l..i]），它的 XOR 记为 xor(l..i-1)
  • 如果：
    • dp[l][c-1] == true，并且
    • xor(l..i-1) ≤ limit
  • 那么：
1
dp[i][c] = true;

这样最后 dp[n][k] 就是 F(limit) 的真假。

AC代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
 public:
  static const int inf = INT_MAX;
  int minXor(vector<int>& nums, int k) {
    int n = nums.size();
    auto check = [&](int mid) -> bool {
      // f[j][i]: 前i个数凑成j个数组，每个数组的异或和能否小于等于mid
      bool f[305][305];
      memset(f, 0, sizeof(f));
      f[0][0] = 1;
      for (int j = 1; j <= k; ++j) {
        for (int r = j; r <= n; ++r) {
          int s = 0;
          for (int l = r; l >= j; --l) {
            s ^= nums[l - 1];
            if (s <= mid && f[j - 1][l - 1]) {
              f[j][r] = 1;
              break;
            }
          }
        }
      }
      return f[k][n];
    };
    // 二分主体
    int l = 0, r = (1 << 30) - 1;
    while (l < r) {
      int mid = (l + r) >> 1;
      if (check(mid))
        r = mid;
      else
        l = mid + 1;
    }
    return l;
  }
};