2025 异或和 · 方案一贪心能接就接

CSP-J 标程 · 复赛真题 · 代码 · cpp · 难度 3/5 · 共 1227 字

前缀异或加一个可选起点集合

2025
位运算

正文

// CSP-J 2025 复赛 T3 · 异或和
// 原题：https://oj.yecheng.tv/p/CSP2025JC
// 题意：给一个序列 a 和一个数 k，要选出尽量多个互不相交的区间，
// 使每个区间里所有数的异或和都等于 k。问最多能选几个。
//
// 方案一 · 贪心：从左到右，能接就接
// 先算前缀异或 s[i] = a[1] ^ ... ^ a[i]（s[0] = 0）。
// 区间 [l, r] 的异或和 = s[r] ^ s[l-1]，它等于 k 等价于 s[l-1] = s[r] ^ k。
// 于是问题变成：不断找一对位置 (j, i)，j < i 且 s[j] = s[i] ^ k，
// 每一对就对应一个区间 [j+1, i]，并且这些区间不能重叠。
// 贪心策略：用一个集合记下「当前还可选的起点 j 的前缀异或值」，
//   从左到右扫，一旦 s[i] ^ k 在集合里，就选中这个区间、答案加一，
//   然后把集合清空、只留下 s[i]（因为下一个区间只能从 i 之后开始）。
// 为什么对：越早结束的区间给后面留的位置越多，早结束永远不吃亏 ——
//   这跟经典「区间调度」的贪心是同一个道理。

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

int main() {
    freopen("xor.in", "r", stdin);
    freopen("xor.out", "w", stdout);

    int n;
    long long k;
    cin >> n >> k;

    set<long long> avail;
    avail.insert(0);                 // s[0] = 0，是第一个可用的起点
    long long s = 0;
    int ans = 0;

    for (int i = 1; i <= n; i++) {
        long long x;
        cin >> x;
        s ^= x;                      // s 就是 s[i]
        if (avail.count(s ^ k)) {    // 存在起点 j，使得 [j+1, i] 的异或和是 k
            ans++;
            avail.clear();           // 选完了，后面的区间只能从 i 之后开始
        }
        avail.insert(s);             // 位置 i 本身也可以当下一轮的起点
    }
    cout << ans << "\n";
    return 0;
}

2025 异或和 · 方案一 贪心能接就接

正文

CSP-J 标程 · 复赛真题的其它内容

2025 异或和 · 方案一贪心能接就接