2315 问题 C: [传智杯]众数出现的次数

 时间限制: 5s 内存限制: 512MB
题目描述

传智专修学员的课堂上，为了活跃气氛，并巩固位运算的知识，同学们玩起了一个游戏。

班级里有 n(n<=10^6) 名同学，每位同学都获得了两张卡，红卡或者黑卡。每张卡上都有一个不超过 10^9 的非负整数。第 i 位同学手里红卡数字是 ai ，黑卡数字是 bi。

现在需要每位同学出牌。每位同学可以直接将红卡上的数字打出，或者将自己的红卡上的数字和自己黑卡数字进行按位异或操作后的结果打出。最后老师会收集所有同学打出的数字。

这些数字中出现次数最多的数字是众数。在所有同学合作的最优策略下，我们希望众数对应数字出现的次数尽可能多。请问出现次数最多的数字是多少呢？

输入

第一行，一个正整数 n。

接下来 n 行，其中第 i 行时非负整数 ai,bi 代表第 i 名同学手上红卡和黑卡的数字。

输出
一个整数，表示答案。如果有多个解，请输出最小的那个。

样例输入

4
21 9
28 9
28 3
17 4

样例输出

21
提示

样例解释：

众数出现次数最多是 3 次，有如下两种方法：

  • 1 号同学直接出红卡，2 号同学出红黑异或，3 号同学随便出，4 号同学出红黑异或。这样 1,2,4 号同学都可以打出 21。
  • 1 号同学出红黑异或，2 号同学直接出红卡，3 号同学直接出红卡, 4 号同学随便出。这样 1,2,3号同学都可以打出 28。

所以 21 和 28 都是出现次数最多的众数，因为最多可以出现 3 次，不存在出现 4 次的方案。但是由于要求如果有多解输出小的，请输出 21。 


                
                
                

                                        

                        
                        

                                                            
                                
                                                        
                            
                            
                            
                        

                    

                

                


                

            

            

                

                    

                        
比赛公告

                    

                    

                        

                            

	排名前60%即前240名同学顺利进入决赛




	时间为：4.18日下午16：30~19：30




	到时间直接参加即可，无需再报名，也无需密码可以进入

                        

                    

                

                

                    

                        
比赛状况