题解 | #被打乱的异或和#
被打乱的异或和
https://www.nowcoder.com/practice/116db6858c424fb89b821125053bbc15
题目链接
题目描述
有一个长度为 的原始整数数组
。计算出该数组所有元素的按位异或和,记为
。然后将
添加到数组
的末尾,形成一个长度为
的新数组。最后,这个新数组被随机打乱,得到了我们看到的输入数组
。
给定被打乱后的数组 ,我们需要找回原始的异或和
。题目保证至少有一个解,若有多个可能的解,输出任意一个即可。
解题思路
这道题的核心在于巧妙地运用异或运算的性质。
我们来回顾一下异或(XOR, )的几个关键性质:
- 交换律和结合律:
,
。这意味着一串数字的异或和与它们的顺序无关。
- 自反性:
。任何数与自身异或的结果是 0。
- 单位元:
。任何数与 0 异或的结果是它本身。
设原始数组是 。
其异或和是
。
将
添加后,数组变为
。
输入的数组
是
的一个随机排列。
根据异或的交换律和结合律,数组 中所有元素的异或和与数组
相同。我们来计算一下这个总异或和:
我们知道括号里的部分就是 的定义,所以:
根据自反性,。所以:
这意味着,无论原始数组是什么,被打乱后的输入数组 的所有元素异或和永远是 0。
现在,我们如何找到 ?题目要求我们输出任意一个可能的
。
让我们从输入数组 中任意选择一个元素,比如
,然后假设它就是我们要找的
。
如果这个假设成立,那么数组 中剩下的
个元素就应该是原始数组
。
为了验证这个假设,我们需要检查这剩下的 个元素的异或和是否真的等于我们假设的
(也就是
)。
剩下的 个元素的异或和可以这样计算:将
的总异或和,再与
进行一次异或(这相当于从总和中“移除”
)。
我们已经证明了 ,所以:
这个结果说明,我们计算出的“剩下元素的异或和”恰好就等于我们一开始假设的那个元素 !
这个推导对于我们从数组 中选择的任何一个元素
都成立。
结论:输入数组 中的每一个元素都是一个合法的解。既然题目允许我们输出任意一个,最简单的做法就是直接输出数组的第一个元素。
代码
#include <iostream>
void solve() {
int m;
std::cin >> m;
// 只需要读取第一个数字作为答案
int first_num;
std::cin >> first_num;
std::cout << first_num << std::endl;
// 读取并丢弃剩下的 m-1 个数字
for (int i = 1; i < m; ++i) {
int temp;
std::cin >> temp;
}
}
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int t;
std::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) {
int m = sc.nextInt();
// 只需要读取第一个数字作为答案
int firstNum = sc.nextInt();
System.out.println(firstNum);
// 读取并丢弃剩下的 m-1 个数字
for (int i = 1; i < m; i++) {
sc.nextInt();
}
}
}
}
import sys
def solve():
m = int(sys.stdin.readline())
# 读取整行,并只取第一个数字作为答案
nums = sys.stdin.readline().split()
print(nums[0])
def main():
t_str = sys.stdin.readline()
if not t_str:
return
t = int(t_str)
for _ in range(t):
solve()
if __name__ == "__main__":
main()
算法及复杂度
- 算法:数学/位运算。基于对异或运算性质的分析,我们得出结论:输入数组中的任何一个元素都是一个有效的答案。因此,我们只需读取并输出第一个元素。
- 时间复杂度:对于每个测试用例,我们读取
个整数,但只处理第一个。总时间复杂度取决于读入所有数字所需的时间,即
,其中
是所有测试用例的数组长度之和。
- 空间复杂度:我们不需要存储整个数组,只需要存储单个变量。因此,空间复杂度为
。