异或和【牛客tracker 每日一题】

张开发
• 2026/4/24 4:02:28 • 15 分钟阅读

最新文章

推荐文章

相关文章

分享文章

异或和【牛客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≤100000001 ≤ a i ≤ 1 e 9 1≤a_i≤1e91≤ai​≤1e9注意数据较大c i n cincin会T TT掉解题思路本题核心是利用异或运算的核心性质求解目标值。异或满足交换律、结合律且x^x0、0^xx因此数组中出现偶数次的数字会两两抵消最终异或结果就是所有出现奇数次数字的异或和。针对n≤1e7的超大数据规模代码开启快速IO优化避免输入超时仅需一次线性遍历数组全程仅用单个变量维护异或结果无需开辟额外空间统计数字频次。算法时间复杂度O ( n ) O(n)O(n)空间复杂度O ( 1 ) O(1)O(1)极致高效地处理千万级数据量。总结核心逻辑异或运算自动抵消偶数次重复数字直接得到奇数次数字的异或和。关键操作快速I O IOIO优化输入效率线性遍历数组并累加异或值。效率保障线性时间常数空间完美适配千万级数据规模无超时、内存溢出风险。代码内容#includebits/stdc.husingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll p1e97;constll INF1e18;constll M1e610;intmain(){ios::sync_with_stdio(0);cin.tie(0);ll n;cinn;ll ans0,a;for(ll i1;in;i){cina;ans^a;}coutans\n;return0;}

更多文章