基础算法题——找筷子（位的异或）

迷南。 2022-11-21 11:30 152阅读 0赞

#### [找筷子][Link 1] ####

题目描述  
经过一段时间的紧张筹备，电脑小组的“RP 餐厅”终于开业了，这天，经理 LXC 接到了一个定餐大单，可把大家乐坏了！员工们齐心协力按要求准备好了套餐正准备派送时，突然碰到一个棘手的问题:筷子！

CX 小朋友找出了餐厅中所有的筷子，但遗憾的是这些筷子长短不一，而我们都知道筷子需要长度一样的才能组成一双，更麻烦的是 CX 找出来的这些筷子数量为奇数，但是巧合的是，这些筷子中只有一只筷子是落单的，其余都成双，善良的你，可以帮 CX 找出这只落单的筷子的长度吗？

输入格式  
第一行是一个整数，表示筷子的数量 n。

第二行有 n 个整数，第 i 个整数表示第 i 根筷子的长度 ai 。

输出格式  
输出一行一个整数表示答案。

输入输出样例  
输入 \#1  
9  
2 2 1 3 3 3 2 3 1  
输出 \#1  
2  
说明/提示  
数据规模与约定  
对于 30% 的数据，保证 n ≤ 105。  
对于 100% 的数据，保证 1 ≤ n ≤ 107\+1，1 ≤ ai ≤ 109。

--------------------

看看这可恶的数据范围，直接淘汰的一般方法：存储每个筷子长度，再查找数量为奇数的筷子长度。

--------------------

让我们来再了解 异或的性质：  
若 a，b，c 三个数进行异或，结果相当于对三个数的每一位进行异或，然后利用二进制权值计算出的值。

//枚举出所有位可能的情况
    0 ^ 0 ^ 0 = 0
    0 ^ 0 ^ 1 = 1
    0 ^ 1 ^ 0 = 1
    0 ^ 1 ^ 1 = 0
    1 ^ 0 ^ 0 = 1
    1 ^ 0 ^ 1 = 0
    1 ^ 1 ^ 0 = 0
    1 ^ 1 ^ 1 = 1;

我们能够发现每个情况，若 1 出现的次数为奇数，则异或后结果为 1，否则为 0 。

--------------------

拓展到题目，若只有一个筷子长度出现的次数为奇数，则异或后结果为该长度。

**直接全部长度异或，最终结果就是奇数长度。**

#include<stdio.h>
    int main(){ 
    	int n, ans=0;;
    	scanf("%d", &n);
    	for(int i=0; i<n; i++){ 
    		int tmp;
    		scanf("%d", &tmp);
    		ans = tmp^ans;
    	}
    	printf("%d", ans);
    	
    	return 0;
    }

[Link 1]: https://www.luogu.com.cn/problem/P1469