异或和【牛客tracker 每日一题】
异或和
时间限制：2秒 空间限制：32M
网页链接
牛客tracker
牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！
题目描述
小s u n sunsun非常的喜欢数字，现在他想到了一个新问题：给你一个数列，想你帮他算算，这个数列中，出现次数为奇数个的数字的异或和。
输入描述：
第一行是一个整数n nn
接下来一行，n nn个整数a i a_iai，代表整个数列
输出描述：
一行，代表出现次数为奇数个的数字的异或和
示例1
输入：
5 1 2 3 4 4输出：
0示例2
输入：
5 1 1 2 3 3输出：
2备注：
数据范围：
1 ≤ n ≤ 10000000 1≤n≤100000001≤n≤10000000
1 ≤ a i ≤ 1 e 9 1≤a_i≤1e91≤ai≤1e9
注意数据较大，c i n cincin会T TT掉
解题思路
本题核心是利用异或运算的核心性质求解目标值。异或满足交换律、结合律，且x^x=0、0^x=x，因此数组中出现偶数次的数字会两两抵消，最终异或结果就是所有出现奇数次数字的异或和。针对n≤1e7的超大数据规模，代码开启快速IO优化避免输入超时，仅需一次线性遍历数组，全程仅用单个变量维护异或结果，无需开辟额外空间统计数字频次。算法时间复杂度O ( n ) O(n)O(n)，空间复杂度O ( 1 ) O(1)O(1)，极致高效地处理千万级数据量。
总结
核心逻辑：异或运算自动抵消偶数次重复数字，直接得到奇数次数字的异或和。
关键操作：快速I O IOIO优化输入效率，线性遍历数组并累加异或值。
效率保障：线性时间+常数空间，完美适配千万级数据规模，无超时、内存溢出风险。
代码内容
#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=1e3+10;constll p=1e9+7;constll INF=1e18;constll M=1e6+10;intmain(){ios::sync_with_stdio(0);cin.tie(0);ll n;cin>>n;ll ans=0,a;for(ll i=1;i<=n;i++){cin>>a;ans^=a;}cout<<ans<<"\n";return0;}