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$

解题思路

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

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

代码实现

CPP

#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 解释并编辑。

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

文章操作

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

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

题目分析

解题思路

代码实现

后记

声明

相关推荐

评论

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