题解：P14359 [CSP-J 2025] 异或和 / xor（民间数据）

思路：

1. 前缀异或数组

定义前缀异或数组，其中

p_0 = 0

，

p_i = a_1 \oplus a_2 \oplus \cdots \oplus a_i

。
则区间

[l, r]

的异或和可表示为

p_r \oplus p_{l-1}

，当区间异或和等于

k

时，有

p_{l-1} = p_r \oplus k

。

2. 贪心选择策略

核心思想：从左到右扫描，对于每个右端点，寻找最小的左端点（满足不重叠条件），使得区间异或和为 $k$ 。
一旦找到符合条件的区间就立即选择，并更新最后选中的右端点，这种贪心策略能保证选择结束最早的可行区间，从而最大化区间数量。

3. 优化

使用哈希表记录每个前缀异或值出现的位置列表。
对于每个右端点，通过二分查找快速定位满足条件的最小左端点，确保区间不相交且选择最优。

算法复杂度

时间复杂度： $O(n \log n)$ ，每个位置的二分查找操作均为 $O(\log n)$
空间复杂度： $O(n)$ ，存储前缀异或值的位置信息

代码

CPP

#include <bits/stdc++.h>
using namespace std;

int n, k;
int p, last, counts;
// p:当前前缀异或值, last:最后选择的区间右端点, counts:选择的区间数量

int main() {
    scanf("%d %d", &n, &k);
    
    vector<int> a(n);
    for (int i = 0; i < n; i ++) cin >> a[i];
    
    unordered_map<int, vector<int> > Map;
    Map[0].push_back(0);
    
    for (int i = 1; i <= n; i ++) {
        p ^= a[i - 1]; // 更新前缀异或值
        int target = p ^ k;

         // 检查是否存在满足条件的前缀位置
        if (Map.find(target) != Map.end()) {
            vector<int>& pos = Map[target];

             // 二分查找第一个 >= last 的位置（确保区间不重叠）
            auto it = lower_bound(pos.begin(), pos.end(), last);
            // 如果找到合适的位置且该位置在当前位置之前
            if (it != pos.end() && *it < i) {
                counts ++;
                last = i;
            }
        }
        Map[p].push_back(i);
    }
    
    printf("%d\n", counts);
    return 0;
}

题解：P14359 [CSP-J 2025] 异或和 / xor（民间数据）

文章操作

思路：

1. 前缀异或数组

2. 贪心选择策略

3. 优化

算法复杂度

代码

相关推荐

评论

题解：P14359 [CSP-J 2025] 异或和 / xor（民间数据）