[原创]广工2016新生决赛 H《为什么会变成这样呢》 [位运算]【思维】【好题】
[原创]广工2016新生决赛 H《为什么会变成这样呢》 [位运算]【思维】【好题】
2016-12-07 21:39:16 Tabris_ 阅读数:636
博客爬取于2020-06-14 22:42:31
以下为正文
版权声明:本文为Tabris原创文章,未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/53510746
题目连接:http://gdutcode.sinaapp.com/problem.php?cid=1051&pid=7
-----------------------------------------.
《为什么会变成这样呢》
Problem Description:
“第一次有了喜欢的人,还得到了一生的挚友,两份喜悦互相重叠,这双重的喜悦又带来了更多更多的喜悦,本应已经得到了梦幻一般的幸福时光,然而,为什么,会变成这样呢?”双重的喜悦感却无法带来更多的幸福,现在,雪菜在很多喜悦感之中只想要得到两份不重叠的喜悦感(其他的喜悦感都是重叠的),你能帮她找出这两份不同的喜悦感是多少吗?
Input:
第一行一个整数T,代表数据的组数(1<=T<=10),接下来T组数据,每组数据的第一行是一个整数n(1<=n<=1000000),第二行是n个整数ai(0 <= ai <= 1000000000)代表喜悦感,每两个整数之间有一个空格,题目保证有且仅有两个不同的整数出现一次,其他的整数都是出现两次。
Output:
对于每组数据,输出两个整数,分别代表两份不同的喜悦感,中间有一个空格,并且喜悦感较小的先输出。
Sample input:
2
6
2 2 1 1 3 4
4
1 1 3 4
Sample output:
3 4
3 4
-------------------------------------------------------.
题意:中文题 不解释,
解题思路:
遇到这个题目 大家应该都能想出来的做法,只要先排个序 ,然后找在扫一遍就行了. 但是这题的时限只有1000ms,所以就TLE了
正解是采用位运算 用的做法
首先考虑,除了要求的两个数之外,其他的数都有2个 那么 对于所有的数异或的话,结果就是目标两个数的异或和,
因为这两个数不同,所以异或的结果一定>0
这时候考虑,异或的结果在某二进制上的某一个1 一定是目标数的其中一个贡献的,那么只要讲之间的在同二进制位下为1/0的分成两部分分别求异或和,结果一定是目标数.
输出的时候判断下大小就好了
附本题代码
----------------------------------------.
1 | # include <bits/stdc++.h> |