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

ethansang · 2025-11-01 16:08:27 · 题解

题目传送门

本人作为 xxs 无法参加，但是看到如此简单的 T3 还是忍不住水一篇题解。

思路

先定义一些变量的含义。

• 对 a 数组做一个前缀异或，记前 i 个数的异或值为 s_i。
• 用 l 记录 1 \sim l 的数都无法作为区间的左端点。

然后从前往后扫一遍，需要更新答案的有两种情况：

1. s_i=k
2. pos_{s_i} \ge l$ 且 $cnt_{s_i} > 0

以上两种情况都要让 ans 加 1，l=i。因为此时 i 已经被用过，若以 1 \sim i 中的任意一个数为左端点，则该区间一定包含 i，这是不符合题意的。

注意：如果你是一边遍历一边做前缀异或，那请注意，遇到以上两种情况时，一定要让 s 清零！

有人可能会问，数组到底要开多大呢？根据数据范围，a_i \le 2^{20}，异或一下顶多 2^{20}-1（20 位全是 1），大概是 10^6 多，开到 2 \times 10^6 就足够了。

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define inf 0x3f3f3f3f
#define mod 10007
#define for1(i, a, b) for (register int i = a; i <= b; i++)
#define for2(i, a, b) for (register int i = a; i >= b; i--)
#define pr(x) cout << "In line " << __LINE__ << ": " << #x << " = " << (x) << endl
const int N = 2e6 + 5;
int TT = 1, n, k;
int a[N], cnt[N], pos[N];

void solve()
{
    cin >> n >> k;
    for1(i, 1, n) cin >> a[i];
    int s = 0, ans = 0, l = 0;
    for1(i, 1, n){
        s ^= a[i];
        if (s == k || cnt[s ^ k] && pos[s ^ k] >= l){
            ans++; l = i; s = 0;
        }
        cnt[s]++; pos[s] = i;
    }
    cout << ans << endl;
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    //cin >> TT;
    while (TT--) 
        solve();

    return 0;
}