[原创]广工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)$ 的做法,只要先排个序 ,然后找在扫一遍就行了. 但是这题的时限只有1000ms,所以就TLE了

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

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

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

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

# 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;
}