P14359 异或和 - 题解

核心思路

利用前缀异或和将区间异或和转化为前缀异或和的差值:

区间 [l, r] 的异或和 = prefix[r] ^ prefix[l-1]
如果区间 [l, r] 异或和为 k,则 prefix[r] ^ prefix[l-1] = k
即 prefix[l-1] = prefix[r] ^ k

利用这个性质,可以用哈希表快速查找满足条件的区间。

方法1: 贪心 + 前缀异或和 (O(n))(最好想)

思路

从左到右扫描,一旦找到异或和为k的区间就立即选择(贪心策略)。选择区间后清空哈希表,重新开始计算。

代码

CPP

#include<bits/stdc++.h>

using namespace std;

#define endl '\n'
#define file(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)
#define fclose fclose(stdin), fclose(stdout)

void solve() {
    int n, k;
    cin >> n >> k;

    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    int count = 0;
    int xor_sum = 0;
    int last_end = 0; // 上一个选择区间的右端点

    unordered_map<int, int> last_pos; // 记录每个前缀异或和最后出现的位置
    last_pos[0] = 0;

    for (int i = 1; i <= n; i++) {
        xor_sum ^= a[i];
        int target = xor_sum ^ k;

        if (last_pos.count(target) && last_pos[target] >= last_end) {
            count++;
            last_end = i;
            last_pos.clear();
            last_pos[0] = i;
            xor_sum = 0;
        } else {
            last_pos[xor_sum] = i;
        }
    }

    cout << count << endl;
}

signed main() {
    //file(xor);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int T = 1;
    while (T--) {
        solve();
    }
    return 0;
}

方法2: DP + 哈希优化 (O(n))

思路

定义 dp[i] 为前 i 个元素能选出的最大区间数。

转移方程:

不选包含 i 的区间: dp[i] = dp[i-1]
选以 i 为右端点的区间 [j+1, i]: dp[i] = dp[j] + 1

用哈希表 best[x] 记录前缀异或和为 x 的所有位置中,dp 值的最大值,优化查找过程。

代码

CPP

#include<bits/stdc++.h>

using namespace std;

#define endl '\n'
#define file(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)
#define fclose fclose(stdin), fclose(stdout)

void solve() {
    int n, k;
    cin >> n >> k;

    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    vector<int> dp(n + 1, 0);
    unordered_map<int, int> best;
    best[0] = 0;

    int prefix_xor = 0;

    for (int i = 1; i <= n; i++) {
        prefix_xor ^= a[i];
        dp[i] = dp[i - 1];

        int target = prefix_xor ^ k;
        if (best.count(target)) {
            dp[i] = max(dp[i], best[target] + 1);
        }

        best[prefix_xor] = max(best[prefix_xor], dp[i]);
    }

    cout << dp[n] << endl;
}

signed main() {
    //file(xor);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int T = 1;
    while (T--) {
        solve();
    }
    return 0;
}

方法3: Map优化DP (O(n log n)) (推荐)

思路

与方法3相同,但使用 map 代替 unordered_map,避免哈希冲突导致的最坏情况 TLE,更稳定。

代码

CPP

#include<bits/stdc++.h>

using namespace std;

#define endl '\n'
#define file(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)
#define fclose fclose(stdin), fclose(stdout)

void solve() {
    int n, k;
    cin >> n >> k;

    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    vector<int> dp(n + 1, 0);
    map<int, int> best;
    best[0] = 0;

    int prefix_xor = 0;

    for (int i = 1; i <= n; i++) {
        prefix_xor ^= a[i];
        dp[i] = dp[i - 1];

        int target = prefix_xor ^ k;
        auto it = best.find(target);
        if (it != best.end()) {
            dp[i] = max(dp[i], it->second + 1);
        }

        best[prefix_xor] = max(best[prefix_xor], dp[i]);
    }

    cout << dp[n] << endl;
}

signed main() {
    //file(xor);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int T = 1;
    while (T--) {
        solve();
    }
    return 0;
}

复杂度分析

方法	时间复杂度	空间复杂度	特点
方法1	O(n)	O(n)	贪心,简洁直观
方法2	O(n)	O(n)	DP,理论最优
方法3	O(n log n)	O(n)	最稳定,避免哈希冲突

推荐: 比赛中优先使用方法3(最稳定),其次方法2(最好想),最后是方法1(最简洁, 不过我觉得应该没人追求这个吧)。

测试点分布与数据特征（用于数据分层）

测试点编号	$n \leq$	$k$	特殊性质
$1$	$2$	$=0$	A
$2$	$10$	$\leq 1$	B
$3$	$10^2$	$=0$	A
$4, 5$	$10^2$	$\leq 1$	B
$6 \sim 8$	$10^2$	$\leq 255$	C
$9, 10$	$10^3$	$\leq 255$	C
$11, 12$	$10^3$	$< 2^{20}$	无
$13$	$2 \times 10^5$	$\leq 1$	B
$14, 15$	$2 \times 10^5$	$\leq 255$	C
$16$	$2 \times 10^5$	$< 2^{20}$	无
$17$	$5 \times 10^5$	$\leq 255$	C
$18 \sim 20$	$5 \times 10^5$	$< 2^{20}$	无

特殊性质说明:

性质 A: 对于所有 $1 \leq i \leq n$ ,均有 $a_i = 1$
性质 B: 对于所有 $1 \leq i \leq n$ ,均有 $0 \leq a_i \leq 1$
性质 C: 对于所有 $1 \leq i \leq n$ ,均有 $0 \leq a_i \leq 255$

极致数据分层策略（比赛时有时间就最好做数据分层）

🎯 分层1: 特殊情况优化 - O(1)

测试点	数据特征	使用算法	时间复杂度	说明
1, 3	$a_i = 1$ , $k = 0$	直接计算	O(1)	答案 = $n / 2$

原理: 所有元素都是1,异或和为0意味着选择偶数个1,贪心选择长度为2的区间即可。

🎯 分层2: 极小数据 - O(n²)

测试点	数据范围	使用算法	时间复杂度	运算次数
1, 2	$n \leq 10$	基础DP	O(n²)	≤100

原因: 数据极小,基础DP最简单稳定。

🎯 分层3: 小数据范围 - O(n²)

测试点	数据范围	使用算法	时间复杂度	运算次数
3-8	$n \leq 100$	基础DP	O(n²)	≤10⁴

原因:

100^2 = 10^4

,完全足够,代码简单不易出错。

🎯 分层4: 中等数据范围 - O(n²)

测试点	数据范围	使用算法	时间复杂度	运算次数
9-12	$n \leq 1000$	基础DP	O(n²)	≤10⁶

原因:

1000^2 = 10^6

,在时限内,基础DP足够。

🎯 分层5: 大数据范围 - O(n log n)

测试点	数据范围	使用算法	时间复杂度	运算次数
13-20	$n \leq 5 \times 10^5$	Map优化DP	O(n log n)	≤10⁷

原因: O(n²)会达到

2.5 \times 10^{11}

,必须使用O(n log n)优化。

完整数据分层表

测试点	n范围	k范围	特殊性质	使用算法	时间复杂度	预期运算次数
1	≤2	=0	A	直接计算	O(1)	1
2	≤10	≤1	B	基础DP	O(n²)	100
3	≤100	=0	A	直接计算	O(1)	1
4-5	≤100	≤1	B	基础DP	O(n²)	10⁴
6-8	≤100	≤255	C	基础DP	O(n²)	10⁴
9-10	≤1000	≤255	C	基础DP	O(n²)	10⁶
11-12	≤1000	<2²⁰	无	基础DP	O(n²)	10⁶
13	≤2×10⁵	≤1	B	Map优化DP	O(n log n)	4×10⁶
14-15	≤2×10⁵	≤255	C	Map优化DP	O(n log n)	4×10⁶
16	≤2×10⁵	<2²⁰	无	Map优化DP	O(n log n)	4×10⁶
17	≤5×10⁵	≤255	C	Map优化DP	O(n log n)	10⁷
18-20	≤5×10⁵	<2²⁰	无	Map优化DP	O(n log n)	10⁷

算法选择决策树

CPP

开始读入 n, k, a[]
  │
  ├─ 所有元素都是1 且 k=0?
  │    └─ 是 → 直接计算: ans = n/2, O(1)   [测试点 1, 3]
  │
  ├─ n ≤ 100?
  │    └─ 是 → 基础DP, O(n²)   [测试点 1-8]
  │
  ├─ n ≤ 1000?
  │    └─ 是 → 基础DP, O(n²)   [测试点 9-12]
  │
  └─ n ≤ 5×10⁵?
       └─ 是 → Map优化DP, O(n log n)   [测试点 13-20]

性能对比

假设时限为 1 秒 = 1e9(虽然有点悬) 次运算:

测试点	n	基础DP (O(n²))	Map优化 (O(n log n))
1-8	≤100	10⁴	10³
9-12	≤1000	10⁶	2×10⁴
13-16	≤2×10⁵	4×10¹⁰	4×10⁶
17-20	≤5×10⁵	2.5×10¹¹	10⁷

完整代码实现 (极致分层版本)

CPP

#include<bits/stdc++.h>

using namespace std;

#define endl '\n'
#define file(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)
#define fclose fclose(stdin), fclose(stdout)


// 算法1: 直接计算 - O(1)
// 适用于: 所有元素都是1且k=0的情况
int solve_special_all_ones(int n) {
    return n / 2;
}

// 算法2: 基础DP - O(n²)
// 适用于: n <= 1000 的情况
int solve_dp_basic(int n, int k, vector<int>& a) {
    vector<int> dp(n + 1, 0);
    vector<int> prefix(n + 1, 0);

    // 预处理前缀异或和
    for (int i = 1; i <= n; i++) {
        prefix[i] = prefix[i - 1] ^ a[i];
    }

    // DP转移
    for (int i = 1; i <= n; i++) {
        dp[i] = dp[i - 1]; // 不选包含i的区间

        // 枚举所有以i为右端点的区间
        for (int j = 1; j <= i; j++) {
            int xor_val = prefix[i] ^ prefix[j - 1];
            if (xor_val == k) {
                dp[i] = max(dp[i], dp[j - 1] + 1);
            }
        }
    }

    return dp[n];
}

// 算法3: DP + Map优化 - O(n log n)
// 适用于: n > 1000 的情况,最稳定
int solve_dp_map(int n, int k, vector<int>& a) {
    vector<int> dp(n + 1, 0);
    map<int, int> best; // best[x] = 前缀异或和为x时的最大dp值
    best[0] = 0;

    int prefix_xor = 0;

    for (int i = 1; i <= n; i++) {
        prefix_xor ^= a[i];
        dp[i] = dp[i - 1];

        int target = prefix_xor ^ k;
        auto it = best.find(target);
        if (it != best.end()) {
            dp[i] = max(dp[i], it->second + 1);
        }

        best[prefix_xor] = max(best[prefix_xor], dp[i]);
    }

    return dp[n];
}

void solve() {
    int n, k;
    cin >> n >> k;

    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    int ans = 0;

    // 分层1: 特殊情况 - 所有元素都是1且k=0
    // 适用测试点: 1, 3
    bool all_ones = true;
    for (int i = 1; i <= n; i++) {
        if (a[i] != 1) {
            all_ones = false;
            break;
        }
    }

    if (all_ones && k == 0) {
        // O(1) 直接计算
        ans = solve_special_all_ones(n);
    }
    // 分层2+3: n <= 100 (测试点 1-8)
    // 使用基础DP,代码简单不易出错
    else if (n <= 100) {
        ans = solve_dp_basic(n, k, a);
    }
    // 分层4: n <= 1000 (测试点 9-12)
    // 使用基础DP,10^6次运算可接受
    else if (n <= 1000) {
        ans = solve_dp_basic(n, k, a);
    }
    // 分层5: n <= 5×10^5 (测试点 13-20)
    // 使用Map优化DP,避免哈希冲突
    else {
        ans = solve_dp_map(n, k, a);
    }

    cout << ans << endl;
}

signed main() {
    //file(xor);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int T = 1;
    //cin >> T;
    while (T--) {
        solve();
    }
    //fclose;
    return 0;
}

代码说明

三个核心算法函数

solve_special_all_ones(n) - O(1)
- 处理所有元素都是1且k=0的特殊情况
- 直接返回 n/2
solve_dp_basic(n, k, a) - O(n²)
- 基础动态规划,适用于小数据
- 枚举所有区间,DP转移
solve_dp_map(n, k, a) - O(n log n)
- Map优化的动态规划,适用于大数据
- 用map记录前缀异或和对应的最大dp值

分层判断逻辑

CPP

if (all_ones && k == 0)       O(1)      测试点 1, 3
else if (n <= 100)            O(n²)     测试点 1-8
else if (n <= 1000)           O(n²)     测试点 9-12
else                          O(nlogn)  测试点 13-20

关键知识点

前缀异或和: 区间 [l,r] 异或和 = prefix[r] ^ prefix[l-1]
异或性质: a ^ b = c ⟺ a = b ^ c ⟺ b = a ^ c
贪心策略: 区间调度问题,选择最早结束的区间是最优的
哈希优化: 用哈希表快速查找满足条件的前缀异或和

温馨提示

注意事项:

比赛的时候一定要检查有没有加 freopen, 如果没加的话就加上，加上了之后写代码时先注释掉，最后取消注释的时候一定要再编译一遍！（我同学已经因为这个吃亏了）
比赛写到最后1小时的时候，如果别的题没有思路，就先给已经写过的题做数据分层，根据不同范围分析暴力枚举，深度优先搜索(Depth-First Search, DFS)等算法

解题技巧

可以根据数据范围来猜测算法时间/空间复杂度然后再根据复杂度选取合适的算法
要多观察特殊性质，有时可以通过特殊性质推导出正解，也可以通过特殊性质进行混分，比赛总是分越多拿奖概率越高

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

文章操作