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

~~年龄限制考不了。反正明年就行了。~~

大意是选择尽可能多的不相交区间，使得每个区间的异或和都等于

k

。

设前缀异或数组：

s_i = a_1 \oplus a_2 \oplus \cdots \oplus a_i

其中

s_0 = 0

。

区间

[l, r]

的异或和可表示为：

a_l \oplus \cdots \oplus a_r = s_r \oplus s_{l-1}

要使区间

[l, r]

的异或和等于

k

，需满足：

s_r \oplus s_{l-1} = k \iff s_r = s_{l-1} \oplus k

原问题转化为：在

s_0, s_1, \dots, s_n

中寻找尽可能多的下标对

(p, q)

，满足：

$p < q$
$s_q = s_p \oplus k$
对应区间 $[p+1, q]$ 互不重叠

可以用贪心来做，哈希表记录各前缀异或值最近出现位置，然后按照条件选取区间即可。

CPP

#include<bits/stdc++.h>
using namespace std;
const int N=500005;
int a[N],s[N];
unordered_map<int,int> lst;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n,k;
    cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>a[i];
    lst[0]=0;
    int last=0,ans=0;
    for(int i=1;i<=n;i++)
	{
        s[i]=s[i-1]^a[i];
        int tar=s[i]^k;
        if(lst.count(tar)&&lst[tar]>=last)
		{
            ans++;
            last=i;
        }
        lst[s[i]]=i;
    }
    cout<<ans;
    return 0;
}

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

文章操作

相关推荐

评论

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