[原创]广工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

-------------------------------------------------------.

题意:中文题 不解释,

解题思路:
遇到这个题目 大家应该都能想出来O(nlogn)O(nlogn)的做法,只要先排个序 ,然后找在扫一遍就行了. 但是这题的时限只有1000ms,所以就TLE

正解是采用位运算 用O(n)O(n)的做法

首先考虑,除了要求的两个数之外,其他的数都有2个 那么 对于所有的数异或的话,结果就是目标两个数的异或和,
因为这两个数不同,所以异或的结果一定>0
这时候考虑,异或的结果在某二进制上的某一个1 一定是目标数的其中一个贡献的,那么只要讲a1,a2,...,ana_1,a_2,...,a_n之间的在同二进制位下为1/0的分成两部分分别求异或和,结果一定是目标数.

输出的时候判断下大小就好了

附本题代码
----------------------------------------.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
# include <bits/stdc++.h>

# define abs(a) (((a)>0)?(a):-(a))

typedef long long int LL;
using namespace std;
const int N = 1e6+7;
/******************************************/

int a[N];
int main()
{
int _;
while(~scanf("%d",&_))
{
while(_--)
{
int n,x;
scanf("%d",&n);
for(int i=1; i<=n; i++)
scanf("%d",&a[i]),x^=a[i];
int num1 = 0, num2 = 0;
int tmp = 1;
while(!(tmp & x)) tmp <<= 1;
for(int i = 1; i <= n; i++)
{
if(tmp & a[i]) num1 ^= a[i];
else num2 ^= a[i];
}
printf("%d %d\n", min(num1, num2), max(num1, num2));



}
}
return 0;
}