蓝桥杯第3217题简单的异或难题 C++ Java Python

题目

思路和解题方法

计算给定数组中子数组异或和的问题。它采用了前缀异或的方法来预处理数组，然后对于每个查询，通过异或操作计算子数组的异或和。

读取输入的数组，并计算每个位置的前缀异或和。
对于每个查询，读取查询的左右边界，计算对应子数组的异或和并输出。

复杂度

时间复杂度:O(n+m)

预处理数组的时间复杂度为 O(n)，每个查询的时间复杂度为 O(1)，因此总体时间复杂度为 O(n + m)，其中 n 是数组长度，m 是查询次数。

空间复杂度:O(n)

程序的空间复杂度取决于数组大小和其他常量，因此为 O(n)。

c++ 代码

#include <iostream>
using namespace std;

const int N = 1e5+10;

int main() {
    // 关闭输入输出流的同步，提高速度
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n, m;
    cin >> n >> m;
    int a[N], prefix[N];

    // 读取数组并计算前缀异或和
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        prefix[i] = prefix[i - 1] ^ a[i];
    }

    while (m--) {
        int l, r;
        cin >> l >> r;
        // 计算子数组的异或和
        int ans = prefix[r] ^ prefix[l - 1];
        cout << ans << '\n';
    }
    return 0;
}

Java 版本（仅供参考）

import java.util.*;

public class Main {
    static final int N = 100009;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int[] a = new int[N];
        int[] prefix = new int[N];

        for (int i = 1; i <= n; i++) {
            a[i] = scanner.nextInt();
            prefix[i] = prefix[i - 1] ^ a[i];
        }

        while (m-- > 0) {
            int l = scanner.nextInt();
            int r = scanner.nextInt();
            int ans = prefix[r] ^ prefix[l - 1];
            System.out.println(ans);
        }
    }
}

Python 版本（仅供参考）

n, m = map(int, input().split())
a = list(map(int, input().split()))
prefix = [0] * (n + 1)

for i in range(1, n + 1):
    prefix[i] = prefix[i - 1] ^ a[i - 1]

for _ in range(m):
    l, r = map(int, input().split())
    ans = prefix[r] ^ prefix[l - 1]
    print(ans)