P1469

luogu的题解

天国的luogu题解

P1469

像我这样的fw都能发题解了，夭寿

1145141919810

前置理论

位运算中异或的性质：
自反：a^b^a = b
交换律：a^b = b^a

开始烹饪

这代码并非清汤寡水，里面还有一位蒟蒻在烹饪

先看题目，4mb的内存属实是不当人（不然我的马桶排序也可以过）
同时1<=n<=10^7+1 and 1<=a<=10^9 这么大的数据给这么小的内存，
那么就不能用存储数据再剔除的方法来解决

---

最好只有一个变量，这样就不用考虑内存问题。
这时，位运算就成了最好的选择

---

自反的性质在此时刚好可以用上，假设用a1,a2,a3等来代表相同的数字，那么表达式就可以变成：a1^a2^a3^a3^a1….=a1^a2^a3^a3^a1….=a2

这样的话就只剩下一根筷子的长度了。

附上AC代码：

#include<iostream>
using namespace std;
int main(){
	int num,ans = 114514,n;//ans初始赋值，避免警告
    cin>>n;
  	for(int i = 0;i<n;i++){
    	cin>>num;
  		ans^=num;
    }
  	ans^=114514;
  	cout<<ans<<endl;
	return 0;
}

返回：点击此处