找球号(三)南阳acm528(异或' ^ &…
2018-12-04 07:13:23来源:博客园 阅读 ()
找球号(三)
- 描述
-
xiaod现在正在某个球场负责网球的管理工作。为了方便管理,他把每个球都编了号,且每个编号的球的总个数都是偶数。有一天,xiaod发现少了一个球,你能帮他找出丢的那个球的球号吗?
- 输入
- 有多组测试数据。每组数据包括两行。
第一行是一个整数N(0<N<1000000),表示现在所剩的球数。
随后的一行是N个数,表示所剩的各个球的编号M(0<M<10^9)。 - 输出
- 对于每组数据,输出弄丢的那个球的球号。
- 样例输入
-
5 1 1 3 6 6 3 1 2 1
- 样例输出
-
3 2
- 来源
- hdu改编
- 上传者
- ACM_丁国强
- 算法思想:刚开始我是想要数组存储这n个数,然后从小到大快速排序,只要找到某个数的个数为奇数时,就输出,可惜内存超了,无奈~~代码如下:
-
1 #include<stdio.h> 2 #include<stdlib.h> 3 int a[1000005]; 4 int f(const void *a,const void *b) 5 { 6 return *(int*)a-*(int*)b; 7 } 8 int main() 9 { 10 int n,i,t,ans,k; 11 while(scanf("%d",&n)!=EOF) 12 { 13 for(i=0; i<n; i++) 14 scanf("%d",&a[i]); 15 qsort(a,n,sizeof(int),f); 16 ans = 1; 17 k = 1; 18 for(i=0; i<n-1; i++) 19 { 20 if(a[i] == a[i+1]) 21 ans++; 22 else 23 { 24 if(ans%2 == 1) 25 { 26 printf("%d\n",a[i]); 27 k = 0; 28 break; 29 } 30 ans = 1; 31 } 32 } 33 if(k) 34 printf("%d\n",a[n-1]); 35 } 36 return 0; 37 }
后来网上看了别人的,利用异或来做(大佬),思想是因为丢失的那个球号必定是奇数,所以对所有球号进行排查,必定找出。那什么是异或呢?比如:5和6异或,5的二进制101,6的二进制110等于011也就是3,两个相同的数异或时为0。具体看代码实现:
1 #include<iostream> 2 using namespace std; 3 int main() 4 { 5 int n; 6 while(cin>>n) 7 { 8 int a,b = 0; 9 while(n--) 10 { 11 cin>>a; 12 b^=a; 13 } 14 cout<<b<<endl; 15 } 16 return 0; 17 }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:取对数(整数,不精确)
- 1的个数 南阳acm514 2018-12-04
- 异 形 卵 南阳acm709 2018-12-04
- 密码发生器 南阳acm519 2018-12-04
- 糖果 南阳acm589 2018-12-04
- 南阳 ACM16 矩形嵌套 动态规划 2018-06-18
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash