竞赛题

F 还有两个东西

Time Limit:400MS Memory Limit:65535K

题型: 编程题语言: 无限制

描述

给出n（ n >= 2 ）个整数，其中有 2 个数 a , b 只出现过一次 ， 并且 a != b , 其他数都只出现偶数次 ， 问这两个数分别是什么 ?

输入格式

第一行输入一个n （ 2 <= n <= 2000000 ）

第二行输入 n 个数 xi ( 0 <= xi < 10^9 ) , 用空格隔开

输出格式

分别输出两个数 a , b ( a <= b )

输入样例

4

7 7 9 8

输出样例

8 9

由于时间条件苛刻，排序的方法nlogn的方法也过不了，只能用n的方法。

这里利用到异或：

1.一个数异或0等于它本身

2.两个相同的数异或等于0，

3.异或满足交换律

4.当a^b=c时，满足c^a=b 和c^b=a

题解：

将所有数字异或，由于其他数都出现偶数次，那么他们的异或结果为0，所以最终的结果为：这两个只出现一次的数的异或结果s。异或，即在某一位上，不同才为1。

由于这两个是不同的数，那么他们的二进制至少有一位不同，而此时s在这个位上为1。所以做法是：找出s从右边起，二进制第一个为1的位置，然后根据这个位置，

对数组用ans1和ans2进行分组异或。由于相同的数必定分在同一组，且除这两个数外，其他数都出现偶数次，这表明这些数都“消了”，只剩下只出现一次的数，且

这两个数分在不同的组，ans1，
ans2的最终结果，即为这两个数。

代码如下：

#include<cstdio>

#include<cstring>

using namespace std;

int a[2000005];

int main()

{

    int n, i, s = 0, pos = 0, ans1 = 0,ans2 = 0;

    scanf("%d",&n);

    for(i = 0; i<n; i++)

    {

        scanf("%d",&a[i]);

        s ^= a[i];

    }

    while((s&1)==0 && pos<32)

        pos++, s = s>>1;

    for(i = 0; i<n; i++)

    {

        if((a[i]>>pos)&1)

            ans1 ^= a[i];

        else

            ans2 ^=a[i];

    }

    if(ans1<ans2)

        printf("%d %d\n",ans1,ans2);

    else

        printf("%d %d\n",ans2,ans1);

    return 0;

}

巴特西

SCAU 还有两个东西 —— 异或

竞赛题

F 还有两个东西

描述

输入格式

输出格式

输入样例

输出样例

最新文章

热门文章