区间异或和最大数量问题详解

题目分析

核心概念

1. 区间权值：区间 [l, r] 的权值是该区间内所有元素的异或和
2. 目标：选择尽可能多的不相交区间，使得每个区间的异或和都等于 k

关键性质

• 区间异或和可以用前缀异或快速计算
• 设 p[i] = a[1] ⊕ a[2] ⊕ ... ⊕ a[i]
• 则区间 [l, r] 的异或和 = p[r] ⊕ p[l-1]
• 要使区间异或和为 k，需要：p[r] ⊕ p[l-1] = k
• 即：p[r] = p[l-1] ⊕ k

解题思路

贪心策略

从左到右扫描，一旦找到满足条件的区间就立即选择

为什么贪心正确？

• 如果我们找到一个以位置 i 结尾的区间 [j+1, i] 满足异或和为 k
• 选择这个区间不会影响前面已选的区间
• 尽早结束当前区间，给后面留下更多空间

算法步骤

1. 计算前缀异或数组
2. 使用哈希表记录每个前缀异或值最后一次出现的位置
3. 动态规划：
   • dp[i] = 考虑前 i 个元素，最多能选出的区间数
   • 对于位置 i：
     • 不选：dp[i] = dp[i-1]
     • 选：如果存在 j 使得 p[i] ⊕ p[j] = k，则 dp[i] = max(dp[i], dp[j] + 1)

代码实现

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    
    // 计算前缀异或
    vector<int> p(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        p[i] = p[i - 1] ^ a[i];
    }
    
    // dp[i] 表示前 i 个元素最多能选出的区间数
    vector<int> dp(n + 1, 0);
    
    // 记录每个前缀异或值最后出现的位置
    unordered_map<int, int> lp;
    lp[0] = 0; // p[0] = 0
    
    for (int i = 1; i <= n; i++) {
        // 不选以 i 结尾的区间
        dp[i] = dp[i - 1];
        
        // 尝试选以 i 结尾的区间
        // 需要找到 j 使得 p[i] ^ p[j] = k
        // 即 p[j] = p[i] ^ k
        int t = p[i] ^ k;
        if (lp.find(t) != lp.end()) {
            int j = lp[t];
            dp[i] = max(dp[i], dp[j] + 1);
        }
        
        // 更新当前前缀异或值的位置
        lp[p[i]] = i;
    }
    
    cout << dp[n] << endl;
    
    return 0;
}

样例详解

样例 1：n=4, k=2, a=[2,1,0,3]

前缀异或：

• p[0] = 0
• p[1] = 0 ⊕ 2 = 2
• p[2] = 2 ⊕ 1 = 3
• p[3] = 3 ⊕ 0 = 3
• p[4] = 3 ⊕ 3 = 0

DP 过程：

i	p[i]	t	lastPos[t]	dp[i]	说明
0	0	-	-	0	初始
1	2	0	0	1	区间 [1,1]，异或和=2
2	3	1	不存在	1	无法形成新区间
3	3	1	不存在	1	无法形成新区间
4	0	2	1	2	区间 [2,4]，异或和=1⊕0⊕3=2

答案：2（选择区间 [1,1] 和 [2,4]）

样例 2：n=4, k=3, a=[2,1,0,3]

DP 过程：

• i=1: p[1]=2, t=1, 不存在, dp[1]=0
• i=2: p[2]=3, t=0, lastPos[0]=0, dp[2]=max(0, 0+1)=1
• i=3: p[3]=3, t=0, lastPos[0]=0, dp[3]=max(1, 0+1)=1
• i=4: p[4]=0, t=3, lastPos[3]=2, dp[4]=max(1, 1+1)=2

答案：2（选择区间 [1,2] 和 [4,4]）

样例 3：n=4, k=0, a=[2,1,0,3]

当 k=0 时，需要找异或和为 0 的区间。

• 只有单个元素 0 的异或和为 0
• 位置 3 的元素是 0

答案：1（选择区间 [3,3]）

关键点总结

1. 前缀异或技巧：快速计算任意区间异或和
2. 贪心 + DP：从左到右扫描，尽早确定区间
3. 哈希表优化：快速查找满足条件的前缀位置
4. 不相交保证：通过 dp[j] 转移确保区间不重叠

这道题综合运用了异或性质、前缀和、动态规划和贪心思想