使每个连续元素的按位异或为 k 的子序列的最大长度

Question

我正在尝试解决这个问题，我们必须找到子序列的最大长度，使得每个连续元素的 XOR 等于 k。例如：数组 = [3,2,4,3,5] 且 k=1。答案是 3. subsequence = [3,2,3]

到目前为止，我已经尝试了这些方法：

朴素的双循环解决方案，我们将使用两个循环并找到 XOR 等于 k.This 的子序列方法让我超时，因为数组中的元素数量最多可达 10^5.Psuedo代码：

int finalAns=0;
loop (i=0...n):
  int xortillnow = array[i], count=1;  // since we have already selected one element
  loop(j=i+1..n):
      if((xortillnow ^ array[i])==k):
          count++;
          xortillnow = xortillnow ^ array[i];
   finalAns = max(count,finalAns);

2.Second 我正在考虑动态规划，我可以在其中存储已计算子序列的异或，但我无法完成算法。

谁能告诉我解决这个问题的其他方法。

Answer 1

XOR 运算符有一个很好的属性，对于任何值 x，只有一个值 y，其中 x ⊕ y = k。具体来说，该值 y 由 x ⊕ k 给出，因为

(x ⊕ k) ⊕ k = x ⊕ (k ⊕ k) = x ⊕ 0 = x.

想象一下从左到右扫描数组。每次看到一个新元素，它可以

是当前长度为 1 的新子序列的开始，或者
继续现有的子序列，但前提是序列中 x ⊕ k 出现在它之前。如果确实出现 x ⊕ k，则子序列的长度将等于一加最长子序列的长度，此属性以 x ⊕ k 结尾。

这给出了一个相对简单的算法来解决这个问题。维护哈希 table 或 BST 映射 previously-seen 值到子序列的最大长度，此属性以该值结尾。从左到右扫描阵列。对于每个元素 x，计算 x ⊕ k 并检查它是否在 table 中。如果是，记录 x 的长度为 m + 1，其中 m 是为 x ⊕ k 存储的长度。如果不是，则记录 x 的长度为 1。

这需要使用 BST 的确定性时间 O(n log n) 和使用散列的预期时间 O(n) table。

使每个连续元素的按位异或为 k 的子序列的最大长度

Maximum length of the subsequence such that the bitwise XOR of each consecutive element is is k

algorithm

xor

subsequence