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

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

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;
}

後記 Afterword

很神奇吧,這樣複雜度都壓下去了

後面有些東西是用HTML補上去的
不曉得是不是 Hexo 出 BUG 了
有些正常的 Markdown 無法解析成功
就這樣吧


本部落格所有文章除非特別說明以外,均採用 CC BY-SA 3.0協議 。轉載請註明出處!