2025 CSP-J2 T3 异或和 / xor 题解

chenyuan3 · 2025-11-01 22:22:10 · 题解

（J 组题解链接：T1、T2、T3、T4、视频题解、游记）

:::info[题意简述]

给定数组，求互不重叠的区间的最大数量，使得每个区间内的异或和均为 k。

:::

区间异或和问题，容易想到前缀异或和预处理。然后就是 DP。f_i 表示子问题 1\sim i 的答案。有两种状态转移：

• 不选：f_i=f_{i-1}
• 选：显然区间越小，留给剩下答案的地方就越多，所以要找最后一个满足条件的区间左端点（需要和当前的异或和为 k，移项可得满足条件的数字需要为当前数字异或 k），用一个 map 处理出上一个数字，即可 O(n\log n) 求得答案。

:::success[代码]

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn = 5e5 + 10;
ll n, k, a[maxn], f[maxn];
map<ll, ll> mp;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> k;
    for (ll i = 1; i <= n; i++)
    {
        cin >> a[i];
        a[i] ^= a[i - 1];
    }
    mp[0] = 0;
    for (ll i = 1; i <= n; i++)
    {
        f[i] = f[i - 1];
        if (mp.count(a[i] ^ k))
        {
            f[i] = max(f[i], f[mp[a[i] ^ k]] + 1);
        }
        mp[a[i]] = i;
    }
    cout << f[n];
    return 0;
}

:::

:::success[视频题解]

:::