杭電2095
find your present(2)
原題鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=2095
分析
題目大意為在一組數字中找出唯一一個出現奇數次的數字，并且輸出，（題目輸入可以滿足）
萬事皆可暴力的我第一個想的就是暴力求解，但是很不幸的超時了，后來借鑒了大佬演算法發現是異或運算，所以下面著重介紹關于異或運算我自己的一些理解，
暴力方法（超時）
#include<iostream>
using namespace std;
typedef struct tra{
int number;
int num;
}tracker[500000];
//還有一點需要注意一下，就是如果struct后面沒有那個tra可能會報錯，出現annonymous type with no linkage used to declare variable的報錯（如果有人看這個暴力演算法的話的叨叨）
int n,a[1000000];
tracker b;
int main(){
int i,j,f;
while(scanf("%d",&n)!=EOF&&n){
for(i=0;i<n;i++){
cin>>a[i];
}
for(i=0;i<n;i++){
f=0;
for(j=0;j<i;j++){
if(b[j].number==a[i]){
b[j].num+=1;
f=1;break;
}
}
if(!f){
b[j].number=a[i];b[j].num =1;
}
}
for(i=0;i<(n+1)/2;i++){
if(b[i].num %2!=0){
cout<<b[i].number<<endl;
}
}
}
return 0;
}
按位異或運算（^）
這里是異或和移位運算子的參考來源
定義：即對于兩個數的二進制數相同位（只有1和0）逐一進行比較，相同為0（均為1或均為0），不同為1（0^1）
- 0^任何數=任何數
- 1^任何數=任何數取反
- 任何數^自己=0
上面為基本運算的規則，下面是一些特殊但正確的用法
- (（a^b） ^b)=a
- 通過下面的方法可以將a,b置換，而不需要第三個變數
例如a=10100001，b=00000110
a = a^b； //a=10100111
b = b^a； //b=10100001
a = a^b； //a=00000110
分析上面的題目，可知其他數字都出現偶數次，故多次異或以后一定得0而不影響最終結果，只有唯一一個出現奇數次的數字即為答案，代碼如下：
代碼
#include<iostream>
using namespace std;
int main(){
int i,n,t,a;
while(scanf("%d",&n)!=EOF&&n){
a=0;
for(i=0;i<n;i++){
scanf("%d",&t);
a^=t;
}
cout<<a<<endl;
}
return 0;
}
值得 注意的點是scanf和cin的問題，在代碼中兩次使用scanf 的位置使用cin都會報錯，time limit exceeded,原因因為scanf是格式化輸入，cin是輸入流，需要先把資料存入緩沖區再取用給變數，printf和cout同理，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/220868.html
標籤：其他