首页 > 代码库 > DLUTOJ1215
DLUTOJ1215
题目大意是:给出N个正整数,其中至多有一个数只出现一次,其余的数都出现了两次。判断是否有某个数只出现一次,若有输出这个数,否则输出“-1”。 1<=N<=5000000
这道题的正解是用位运算中的异或XOR(^)
位运算有一个重要性质:与顺序无关。
证明:
1^0=1, 0^0=0
1^1=0, 0^1=1
即0,1与0异或不变,与1异或取反,所以与0异或可以忽略。只考虑1。若m个0, n个1逐次取反,考虑把其中任一位置于开头,若开头是0,则结果为0取反n次,若开头是1,则结果为1取反n-1次,两者必然相等。所以异或运算是可任意交换位置,任意加括号的。
至于这道题,若N是偶数,必然没有只出现一次的数,若N是偶数,根据上面的证明,将0与这N个数逐次异或,最后得到的数就是只出现了一次的那个。异或运算不用特别考虑符号位,代码中unsigned型换成int也行。
#include<cstdio>using namespace std;int main(){ unsigned t; scanf("%u",&t); while(t--) { unsigned k=0, n, id; scanf("%u",&n); if(n%2==0) { for(int i=0; i<n; i++) scanf("%u",&id);//虽然到这步就可以直接判断但还是要接着读后面的数据 printf("-1\n"); continue; } for(int i=0; i<n; i++) { scanf("%u",&id); k^=id; } printf("%u\n",k); } return 0;}
DLUTOJ1215
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。