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

zwcz0009 · 2025-11-01 16:05:11 · 题解

P14359 [CSP-J 2025] 异或和 / xor

前言：异或运算的重要性质

异或运算有一个关键特性：

• 如果 a \oplus b = c，那么 a \oplus c = b 且 b \oplus c = a

题目分析

本题要求在一个序列中找出尽可能多的不相交区间，使得每个区间的异或和都等于给定的 k。

根据前言所给的性质，可得：

• 区间 [l, r] 的异或和可以表示为前缀异或的差值：sum[r] \oplus sum[l-1]，其中 sum[i] = a_1 \oplus a_2 \oplus \dots \oplus a_i
• 如果区间 [l, r] 的异或和为 k，那么 sum[r] \oplus sum[l-1] = k，即 sum[r] = sum[l-1] \oplus k

解题思路

我们可以使用贪心策略来解决这个问题：

1. 计算前缀异或数组 sum
2. 维护一个集合来记录已经出现的前缀异或值
3. 遍历前缀异或数组，对于每个位置 i：
   • 检查 sum[i] ^ k 是否在集合中
   • 如果存在，说明找到了一个满足条件的区间，计数加一，并清空集合（因为区间不能相交）
   • 将当前的前缀异或值加入集合

代码实现

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

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n, k;
    cin >> n >> k;
    vector<int> arr(n);
    for(int i = 0; i < n; i++)
        cin >> arr[i];

    vector<int> sum(n);
    sum[0] = arr[0];
    for(int i = 1; i < n; i++)
        sum[i] = sum[i-1] ^ arr[i];

    unordered_map<int, bool> s;
    s[0] = 1;  // 前缀异和为0的情况（空区间）
    int cnt = 0;

    for(int i = 0; i < n; i++)
    {
        if(s.find(sum[i] ^ k) != s.end())
        {
            cnt++;
            s.clear();
        }
        s[sum[i]] = 1;
    }

    cout << cnt;
    return 0;
}

后记

考试时一看代码时间复杂度为 O(n) ,还以为做错了。。。
不得不说CSP公开速度是真的很快。
本蒟蒻的第一篇文章，多多包涵。

声明

本文章代码为手写，由 Deepseek 解释并编辑。