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

Columbula · 2025-11-01 18:44:22 · 题解

思路：

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)，存储前缀异或值的位置信息

代码

#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;
}