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

RootSign · 2025-11-01 20:05:59 · 题解

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的区间就立即选择(贪心策略)。选择区间后清空哈希表,重新开始计算。

代码

#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 值的最大值,优化查找过程。

代码

#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,更稳定。

代码

#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;
}

复杂度分析

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

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

特殊性质说明:

• 性质 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,异或和为0意味着选择偶数个1,贪心选择长度为2的区间即可。

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

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

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

原因: 100^2 = 10^4,完全足够,代码简单不易出错。

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

原因: 1000^2 = 10^6,在时限内,基础DP足够。

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

原因: O(n²)会达到2.5 \times 10^{11},必须使用O(n log n)优化。

完整数据分层表

算法选择决策树

开始读入 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(虽然有点悬) 次运算:

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

#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;
}

代码说明

三个核心算法函数

1. solve_special_all_ones(n) - O(1)

   • 处理所有元素都是1且k=0的特殊情况
   • 直接返回 n/2

2. solve_dp_basic(n, k, a) - O(n²)

   • 基础动态规划,适用于小数据
   • 枚举所有区间,DP转移

3. solve_dp_map(n, k, a) - O(n log n)

   • Map优化的动态规划,适用于大数据
   • 用map记录前缀异或和对应的最大dp值

分层判断逻辑

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

关键知识点

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

温馨提示

注意事项:

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

解题技巧

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