T1 地雷
题目很简单呢, 就是求哪个数只出现了一次就可以了哦~
我一开始的想法是桶排 (这也是最单纯最简单的想法吧~), 但是空间开 232 肯定会炸的, 而且时间好像也会炸掉.
然后左边的 ych 大佬小声说了一句:"得换个算法."
嗯, 确实要换个算法, 然后我就觉得新算法一定是不用开数组, 直接输完数据就能出答案的那种!
然后不知道怎么就想到了 zhx 讲博弈论的时候输入的同时将 ......(一些稀奇古怪的东西) 异或起来就是答案, 这不正好跟我理想的新算法很像嘛?
异或异或? 咦, 又想到了六月底那次考试有个叫 [音乐会] 达拉崩吧 . 上 https://www.cnblogs.com/xcg123/p/11112398.html 的毒瘤题, 上面给的两条提示:
对呀, 两个相同的数异或起来就是 0!
所以我们可以将所有的数都异或起来, 只要有两个相同的就变成 0 了, 那么最后剩下的不就是那个落单的了嘛?
所以代码就出来了鸭~:
- #include<iostream>
- #include<cstdio>
- using namespace std;
- int read()
- {
- char ch=getchar();
- int a=0,x=1;
- while(ch<'0'||ch>'9')
- {
- if(ch=='-') x=-x;
- ch=getchar();
- }
- while(ch>='0'&&ch<='9')
- {
- a=(a<<1)+(a<<3)+(ch-'0');
- ch=getchar();
- }
- return a*x;
- }
- int n,x,ans;
- int main()
- {
- n=read();
- for(int i=1;i<=n;i++)
- {
- x=read();
- ans^=x; // 求每个数的异或和
- }
- printf("%d",ans);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3133017.html