LeetCode 第 460 场周赛 Q4 3630. 划分数组得到最大异或运算和与运算之和

问题描述

给你一个整数数组 nums。将数组划分为三个（可以为空）子序列 、 和 ，使得 nums 中的每个元素 恰好 属于一个子序列。

你的目标是 最大化 以下值：
其中：

  • XOR（arr）表示 arr 中所有元素的按位异或结果。如果 arr 为空，结果定义为 0 。

  • AND（arr）表示 arr 中所有元素的按位与结果。如果 arr 为空，结果定义为 0 。

返回可实现的最大值。

注意：如果有多种划分方式得到相同的 最大 和，你可以按其中任何一种划分。

子序列：是指一个数组通过删除一些或不删除任何元素，不改变剩余元素的顺序得到的元素序列。

很简单的想法就是枚举 子序列，然后对于剩余 nums - ，我们最大化，这样最终答案就是。枚举 子序列非常简单，总共种情况，难点就是剩下的最大化XOR和的部分。单独拿出来看该子问题。

前置问题：划分数组得到最大异或运算之和

给你一个整数数组 nums。将数组划分为两个（可以为空）子序列 、 ，使得 nums 中的每个元素 恰好 属于一个子序列。

你的目标是 最大化 以下值：

对于该问题需要用到之前线性基的知识。

这里把之前的模板包装成类：

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
class XorBasis:
    def __init__(self, W=31):
        self.W = W                    # 支持到 2^W
        self.basis = [0] * (W + 1)    # basis[k] 存放最高位为 k 的基向量

    def insert_basis(self, x: int) -> None:
        """
        将整数 x 插入线性基。
        """
        for k in range(self.W, -1, -1):
            if not ((x >> k) & 1):
                continue
            if self.basis[k] == 0:
                # 找到空位，x 成为新的基向量
                self.basis[k] = x
                return
            # 否则，用已有基消去 x 在第 k 位的 1
            x ^= self.basis[k]
        # 若 x 最终变为 0，则表示它是冗余的，无需插入

    def get_max_xor(self) -> int:
        """
        在已插入的数中，选子集求最大异或和。
        """
        res = 0
        for k in range(self.W, -1, -1):
            # 若使用 basis[k] 能提升结果，就异或它
            if (res ^ self.basis[k]) > res:
                res ^= self.basis[k]
        return res

问题是该模板是找出单个子集最大化，而我们这里需要最大化的是两个子集之和，因此依然需要对问题进行转换，从补集的角度考虑。我们首先把所有nums都划分给，这意味着此时和为所有数的异或结果。

接下来再一个个剔除给 C，利用结论：

对任意两个子集 A、C，且  互不交，

其中 是将 中某些元素摘出来后，它们异或结果在位上能“翻转”带来的额外增益。
跳到「附录：证明结论」

于是我们有 是原始整体异或。令 bitlen 是所有数 起来的最高位数，那么。

取 ：它表示在哪些二进制位上，原始异或结果是 0（我们可以通过适当分组让那一位变成 1，从而在总和里多加 ）。

接下来，为了在 中选一个子集 ，使得在这些可翻转的位上贡献最大，我们对 中的每个元素 nums[i]，取v = nums[i] & Z —— 只保留它在可翻 Flip 位上的部分。

于是我们完成了对于问题的转化，只需要套用模板最大化 即可：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
from functools import reduce
from operator import or_, xor_

def maximizeXorXor(nums: list[int]) -> int:
    OR_all = reduce(or_, nums, 0)   # 所有数的或运算结果
    bitlen = OR_all.bit_length()    # OR_all 最高位

    X = reduce(xor_, nums, 0)       # 所有数的异或运算结果
    Z = ((1 << bitlen) -1) ^ X      # 可以进行改进的位数

    basis = XorBasis(bitlen)        # 接下来套用线性基
    vs = [n & Z for n in nums]

    for v in vs:
        basis.insert_basis(v)
    M = basis.get_max_xor()
    return X + 2*M

回到本题

现在只需要补全一些细节就可以

预处理子集的异或值和与值

设 n = len(nums)，用动态规划先把所有 个子集的异或值和与值算出来：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
n = len(nums)

xor_mask = [0] * (1<<n)
for mask in range(1, 1<<n):
    lb = mask & -mask         # 取最低位 1
    i = lb.bit_length() - 1   # 最低位对应的 nums 下标
    prev = mask ^ lb
    xor_mask[mask] = xor_mask[prev] ^ nums[i]

and_mask = [0] * (1<<n)
for mask in range(1, 1<<n):
    lb = mask & -mask
    i = lb.bit_length() - 1
    prev = mask ^ lb
    # 如果 prev = 0（只有一个元素），and_mask = nums[i]；否则累 “与”
    and_mask[mask] = (and_mask[prev] & nums[i]) if prev else nums[i]

套用前置问题

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
37
38
39
40
41
42
43
44
class XorBasis:
    ...

class Solution:
    def maximizeXorAndXor(self, nums: List[int]) -> int:
        n = len(nums)
        
        xor_mask = [0] * (1<<n)
        for mask in range(1, 1<<n):
            lb = mask & -mask         # 取最低位 1
            i = lb.bit_length() - 1   # 最低位对应的 nums 下标
            prev = mask ^ lb
            xor_mask[mask] = xor_mask[prev] ^ nums[i]

        and_mask = [0] * (1<<n)
        for mask in range(1, 1<<n):
            lb = mask & -mask
            i = lb.bit_length() - 1
            prev = mask ^ lb
            # 如果 prev = 0（只有一个元素），and_mask = nums[i]；否则累 “与”
            and_mask[mask] = (and_mask[prev] & nums[i]) if prev else nums[i]

        full = (1 << n) - 1
        OR_all = reduce(or_, nums)
        bitlen = OR_all.bit_length()
        full_bits_mask = (1 << bitlen) - 1
    
        ans = 0
        for B in range(1 << n):
            R = full ^ B
            XR = xor_mask[R]
            Z = full_bits_mask ^ XR
    
            vs = [(nums[i] & Z) for i in range(n) if (R >> i) & 1]
            basis = XorBasis(bitlen)

            for v in vs:
                basis.insert_basis(v)

            M = basis.get_max_xor()
            acb =  XR + 2 * M + and_mask[B]
            ans = max(ans, acb)
    
        return ans

复杂度分析

  • 时间复杂度：，其中。枚举需要次循环，每一个循环中我们用线性基找最大值，复杂度为，故总共时间复杂度为。对于数据量是足够的。
  • 空间复杂度：，其中。储存预计算结果用到，线性基储存需要。

附录：证明结论

把这个问题拆成按位（bit）来考察。记：

  • ，且 与 互不相交。

  • 对第 位，我们用小写字母表示：

    • 表示 在第 位上的值（要么是 0，要么是 1）。
    • 表示 在第 位上的值。
    • 表示 在第 位上的值。

位运算基本关系

因为 是把 和 并起来的异或，由于良好的交换结合律，所以有

我们关心第 位对总和 的贡献：

而 。列举一下所有可能：
0 0
1 1
1 1
0 2

剔除元素不会让这一位上的总和减少的原因就在于，即使XOR(A)_k减少了1，XOR(C)_k会对应的增加1，因此总和是不会减少的。而表中最后一行：当 时，移动一个元素使得在「两边都有 1」，可以使总和多出了一个 的增益。