d708. 小王的积木

題目 Problem

題目連結：https://zerojudge.tw/ShowProblem?problemid=d708

敘述 Description

自从小涵去商店买了那么多的积木，小王也去买了一大堆。
不过小王比较喜欢数学，所以他买的积木上写的只有数字；因为他认为偶数比较吉利，于是他买的积木是全是偶数快的。
听说小涵少了一个积木，他便整理了一下他的，可是他发现他也少了一块积木…（很无语吧…）
上次他见你已经帮小涵找到了积木，于是就请你来帮他找找，而且他还告诉你：“我的积木比小涵的好找很多。”
半信半疑的你决定帮帮他。

輸入 Input

只有一笔测资。测资末尾会有多余信息，忽略就好。//感谢asas提醒。2015/8/6

输入数据的第一行，是小王告诉你他的积木个数N（N一定是一个正偶数，而且2<=N<=1000000，你看他的积木可没有小涵的多）。
接下来每行有（N-1）个数字，表示小王每个积木上的数字（可以用longint存储）。

輸出 Output

对于每组测资，输出小王缺少的那块积木的数字。

範例輸入 Sample Input

範例輸出 Sample Output

提示 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

c651. 三、區間xor(RXQ) 這篇文章有寫過有關 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;
}