hdoj 2095 find your present (2)【位运算，异或】

迈不过友情╰ 2022-08-04 14:54 138阅读 0赞

# find your present (2) #

**Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)  
Total Submission(s): 18608    Accepted Submission(s): 7167**

题目大意：给你n个数，找出其中唯一一个出现过奇数次的数；

Sample Input

5
    1 1 3 2 2
    3
    1 2 1
    0

Sample Output

3
    2

异或：

a⊕b = (¬a ∧ b) ∨ (a ∧¬b)

A⊕B=C

![Image 1][]

0⊕0=0          1⊕0=1        1⊕1=0        0⊕1=1

下面给出两个8位二进制数的“异或”运算结果：

01010101

⊕     11001010

10011111

已Accept代码

1)         717MS

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    int k[1000001];
    int main(){
        int n,i;
        while(scanf("%d",&n),n){
            for(i=0;i<n;i++)
                scanf("%d",&k[i]);
            std::sort(k,k+n);
            for(i=1;i<n-1;i++){
                if(k[i]!=k[i+1]&&k[i]!=k[i-1])
                    break;
            }
            printf("%d\n",k[i]);
        }
        return 0;
    }

2)     已优化  577MS

【此代码与1563通用】

#include <iostream>
    #include <stdio.h>
    using namespace std;
    
    int fun() {				//据说当输入数据比较多是，这个函数比scanf快 
    	char c;
    	int r = 0;
    	while((c = getchar()) && c >= '0' && c <= '9')
    		r=r*10+c-'0';
    	return r;
    }
    
    int main() {
    	int n, b;
    	char c;
    	while(scanf("%d", &n), n){
    		int a = 0;
    		getchar();
    		for(int i = 0; i < n; i++){
    			b = fun();
    			a = (a ^ b);
    		}
    		cout << (a ^ 0) << endl;
    	}
    	return 0;
    }

[Image 1]: