題目 Problem#
題目連結：https://zerojudge.tw/ShowProblem?problemid=d708
敘述 Description#
自从小涵去商店买了那么多的积木，小王也去买了一大堆。 不过小王比较喜欢数学，所以他买的积木上写的只有数字；因为他认为偶数比较吉利，于是他买的积木是全是偶数快的。 听说小涵少了一个积木，他便整理了一下他的，可是他发现他也少了一块积木…（很无语吧…） 上次他见你已经帮小涵找到了积木，于是就请你来帮他找找，而且他还告诉你：“我的积木比小涵的好找很多。” 半信半疑的你决定帮帮他。
輸入 Input#
只有一笔测资。 测资末尾会有多余信息，忽略就好。//感谢asas提醒。2015/8/6
输入数据的第一行，是小王告诉你他的积木个数N（N一定是一个正偶数，而且2<=N<=1000000，你看他的积木可没有小涵的多）。 接下来每行有（N-1）个数字，表示小王每个积木上的数字（可以用longint存储）。
輸出 Output#
对于每组测资，输出小王缺少的那块积木的数字。
範例輸入 Sample Input#
8
1
2
3
2
3
4
4
範例輸出 Sample Output#
1
提示 Hint#
提示 ： 小涵的积木的AC代码可以直接AC本题。 但我希望您可以想想另一种解答方式，想想数字有什么特殊性，参考时间复杂度$O(n)$，空间复杂度$O(1)$。
还有一种算法时间复杂度$O(n\log{n})$，空间复杂度$O(n)$的…
如果哪种语言直接输入都超时的话，请与我联系，我将调整时间限制。
//感谢ck99126指出题目存在的一些问题！
題解 Solution#
1.直接暴力做#
無庸置疑，跟 C++ Map 一起使用
程式碼 I Accepted Code I#
#include <bits/stdc++.h>
#define _ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
int main(){
_
long long int N;
cin>>N;
map<int,int> m;
long long int A;
for(int i=0;i<N-1;i++){
cin>>A;
map<int,int>::iterator it=m.find(A);
if(it==m.end())
m[A]=1;
else
m[A]++;
}
for(auto it=m.begin();it!=m.end();it++)
if(it->second%2){
cout<<it->first<<'\n';
break;
}
return 0;
}
2.XOR#
{% post_link zj-c651 %} 這篇文章有寫過有關 XOR 的性質 用歸零律跟自反性就可以完成了
程式碼 II Accepted Code II#
#include <stdio.h>
int main(){
int N,ans=0;
scanf("%d",&N);
N--;
while(N--){
int S;
scanf("%d",&S);
ans^=S;
}
printf("%d\n",ans);
return 0;
}
後記 Afterword#
很神奇吧，這樣複雜度都壓下去了 但 後面有些東西是用HTML補上去的 不曉得是不是 Hexo 出 BUG 了 有些正常的 Markdown 無法解析成功 就這樣吧