题目链接

被打乱的异或和

题目描述

有一个长度为 的整数数组 。令 为数组中所有元素的按位异或结果，即 。将 添加至数组末尾（此时数组长度变为 ），并对新数组进行随机排列。

现给出这个被打乱的、长度为 的新数组，请你找回原来的 。

输入:

  • 第一行一个整数 ，表示测试用例数。
  • 每个测试用例包含两行：
    • 第一行一个整数 ，表示新数组的长度 ()。
    • 第二行 个整数，表示新数组的元素。

输出:

  • 对每个测试用例，输出一个整数，即原始的异或和 。

解题思路

这道题的关键在于利用按位异或(XOR)运算的两个核心性质：

  1. 自反性: 任何数与自身进行异或运算，结果为 0。即 。
  2. 交换律和结合律: 多个数进行异或运算，顺序和分组不影响结果。即 。

我们得到的新数组包含原始数组的所有元素 ，以及它们的总异或和 。 新数组可以表示为 ，只是顺序被打乱了。

如果我们把新数组中的所有元素都进行异或运算，会发生什么呢？ 根据题意， 本身就等于 。所以上式可以写成： 根据异或的自反性， 。

这似乎让我们离答案越来越远了。但我们换个角度思考：题目要求找到 。在新数组中，除了 本身，其他的元素就是原始数组的元素。假设我们能从新数组中剔除掉 ，剩下的元素异或起来就是答案。可我们不知道哪个是 。

让我们再次回到所有元素的异或和。假设新数组的元素是 。它们的总异或和是： 这个结论对于找到 没有直接帮助。

但是，如果我们从新数组中任选一个元素，比如 ，并假设它就是我们要找的 。那么，新数组中剩余的所有元素的异或和就应该是 。 也就是说，如果 ，那么新数组中除 之外所有元素的异或和应该等于 。 设新数组的总异或和为 。除 之外的所有元素的异或和等于 。 这个检查是恒成立的！无论我们选择哪个 作为假设的 ，剩余元素的异或和总是它本身。

这说明，对于给定的新数组，任何一个元素都有可能是我们要找的那个 。 例如，如果原数组是 ，则 。新数组是被打乱的 。

  • 如果我们假设 是答案 ，那么原数组就是 。这两个元素的异或和是 。这与我们的假设相符。
  • 同理，假设 是答案，或 是答案，都会得到自洽的结果。

因此，这道题的解是开放的。既然任意一个元素都可以作为答案，我们只需要输出新数组中的任意一个元素即可。最简单的做法就是输出第一个元素。

代码

#include <iostream>
#include <vector>
#include <numeric>

using namespace std;

void solve() {
    int m;
    cin >> m;
    // 只需要读取第一个数作为答案
    int first_element;
    cin >> first_element;
    // 读取并忽略剩余的 m-1 个数
    for (int i = 1; i < m; ++i) {
        int temp;
        cin >> temp;
    }
    cout << first_element << endl;
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- > 0) {
            solve(sc);
        }
    }
    
    public static void solve(Scanner sc) {
        int m = sc.nextInt();
        // 只需要读取第一个数作为答案
        int firstElement = sc.nextInt();
        // 读取并忽略剩余的 m-1 个数
        for (int i = 1; i < m; i++) {
            sc.nextInt();
        }
        System.out.println(firstElement);
    }
}

def solve():
    m = int(input())
    # 读取整行输入并分割成列表
    arr = list(map(int, input().split()))
    # 输出第一个元素即可
    print(arr[0])

# 读取测试用例数
t = int(input())
for _ in range(t):
    solve()

算法及复杂度

  • 算法：逻辑推理、位运算性质
  • 时间复杂度： - 对于每个测试用例，我们需要读取所有 个输入元素，即使我们只使用第一个。
  • 空间复杂度： (对于Python) 或 (对于C++/Java) - Python版本为了方便一次性读取了所有输入。C++/Java版本可以做到只用常数空间。