被打乱的异或和

思路

题目说的是：有一个长度为 的原始数组，把所有元素异或起来得到 ，然后把 追加到数组末尾变成长度 的数组，再随机打乱顺序给你。问原始数组的异或值是多少。

乍一看好像得想办法把 从打乱的数组里"找出来"，但仔细想想会发现一个关键性质：

打乱后数组所有 个元素的异或值一定是 0。

为什么？设原始数组为 ，那么 。打乱后的数组包含这 个元素加上 ，全部异或起来就是：

$$

这意味着什么呢？对于数组中的任意一个元素 ，把它当作被追加的那个 ，剩下的 个元素的异或值恰好就是 本身（因为总异或是 0，去掉 后异或值就是 ）。

所以每种拆分方式都是合法的，我们只需要输出数组中的任意一个元素即可！直接读第一个数输出就行了。

举个例子验证一下

样例 1：数组 ，总异或 。

  • 选 当答案：剩余 ✓
  • 选 当答案：剩余 ✓
  • 任何元素都行！

代码

#include <bits/stdc++.h>
using namespace std;
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        int n;
        scanf("%d",&n);
        int x;
        scanf("%d",&x);
        for(int i=1;i<n;i++){
            int a;
            scanf("%d",&a);
        }
        printf("%d\n",x);
    }
    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) {
            int n = sc.nextInt();
            int x = sc.nextInt();
            for (int i = 1; i < n; i++) {
                sc.nextInt();
            }
            System.out.println(x);
        }
    }
}

import sys
input = sys.stdin.readline

t = int(input())
for _ in range(t):
    n = int(input())
    a = list(map(int, input().split()))
    print(a[0])

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', (line) => lines.push(line.trim()));
rl.on('close', () => {
    let idx = 0;
    const t = parseInt(lines[idx++]);
    const res = [];
    for (let i = 0; i < t; i++) {
        const n = parseInt(lines[idx++]);
        const a = lines[idx++].split(' ').map(Number);
        res.push(a[0]);
    }
    console.log(res.join('\n'));
});

复杂度

  • 时间复杂度：，需要读入所有元素。
  • 空间复杂度：，只需要存第一个元素。