找球号（三）

时间限制：

2000 ms  |  内存限制：3000 KB

难度：

2

 

描述

xiaod现在正在某个球场负责网球的管理工作。为了方便管理，他把每个球都编了号，且每个编号的球的总个数都是偶数。有一天，xiaod发现少了一个球，你能帮他找出丢的那个球的球号吗？

输入

有多组测试数据。每组数据包括两行。

第一行是一个整数N(0<N<1000000),表示现在所剩的球数。

随后的一行是N个数，表示所剩的各个球的编号M(0<M<10^9)。

输出

对于每组数据，输出弄丢的那个球的球号。

样例输入

51 1 3 6 631 2 1

样例输出

32

解题思路A：最直接的思路，排序，挨个检查。 代码

未通过，

MLE了：

1   2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 #include 
          
            7  8 using namespace std; 9 10 int am[1000005];11 int m;12 13 int main(){14     while(~scanf("%d",&m)){15         for(int i=0;i
          
         
        
       
      

解题思路B：利用set，每查相同即erase，减少内存占用。

代码AC：

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6  7 using namespace std; 8  9 int main(){10     int m,t;11     set
           
             se;12 set
            
             ::iterator it;13 while(~scanf("%d",&m)){14 for(int i=0;i
            
           
          
         
        
       
      

解题思路C：stl有个缺点，就是效率较低，有部分无用内存。这道题有意思的地方是，可以把所有数据直接进行异或，奇数那个编号在异或后会显示出来（偶数的都抵消了）。

代码AC：

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6  7 using namespace std; 8  9 int main(){10     int m,t,ans;11     while(~scanf("%d",&m)){12         ans=0;13         for(int i=0;i