[TIOJ] 1513. Problem C. 好多燈泡

題目連結:http://tioj.infor.org/problems/1513
一開始用unordered_map秒過去,可是傳上去後發現速度似乎有點慘,而且記憶體也比大家高,後來才發現其實把所有數字xor起來就會是答案,因為被關掉的編號一定是出現偶數次,而一個數字xor偶數次後必定就會變成0(也就是那個數字就會消失)。
unordered_map版本
#include <bits/stdc++.h>
using namespace std;
#define FF first
#define SS second

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int n;
	while(cin>>n){
		unordered_map<unsigned int,int> mm;
		for(int i=0;i<n;i++){
			unsigned int x;cin>>x;
			mm[x]++;
		}
		for(auto i:mm) if(i.SS&1) cout<<i.FF<<'\n';
	}
	return 0;
}
xor版本
#include <cstdio>

int main(){
	int n;
	while(scanf("%d",&n)!=EOF){
		unsigned int k=0;
		for(int i=0;i<n;i++){
			unsigned int x;scanf("%u",&x);
			k^=x;
		}
		printf("%u\n",k);
	}
	return 0;
}

留言

這個網誌中的熱門文章

[TIOJ] 1271. [IOI 2012] Scrivener 斯克里夫尼

[TIOJ] 1429. [APIO '12] 忍者調度問題

[Codeforces] 731D. 80-th Level Archeology