如何利用异或求出合理的答案 - C语言论坛

已结贴√ 问题点数：20 回复次数：8

如何利用异或求出合理的答案

有一行n个数，其中所有数都恰好出现了两次，除了两个特殊的数只出现了一次。现在Quasrain想知道这两个特殊的数分别是多少
Input
多组数据。
第一行一个整数T表示数据组数（T<=5）
对于每组数据，第一行一个整数n，意义如题面所示（保证n为偶数，n<=1000000）

接下来一行n个正整数Ai。(0<=Ai<2^31-1)
Output

对于每组数据，输出一行两个正整数，表示两个特殊的数,请按从小到大的顺序输出
Sample Input
2

4

2 2 3 4

6

1 2 3 2 3 5

Sample Output
3 4
1 5

搜索更多相关主题的帖子: 答案　异或　一行　数据　正整数　

第 2 楼

得分:0

程序代码：

#include <stdio.h>

int main( void )
{
    unsigned t;
    scanf( "%u", &t );
    while( t-- )
    {
        unsigned n;
        scanf( "%u", &n );
        static unsigned buf[1000000];
        
        // 扫描第一遍，消去了出现偶数次的数
        unsigned xor = 0;
        for( unsigned i=0; i!=n; ++i )
        {
            scanf( "%u", buf+i );
            xor ^= buf[i];
        }

        // 取 xor 中任意一个为 1 的 bit，用此 bit 就可以将数组分成两组，两个特殊的数分在不同组中
        const unsigned mark = (xor^(xor-1))/2+1;
        unsigned a=0, b=0;
        for( unsigned i=0; i!=n; ++i )
        {
            if( buf[i]&mark )
                a ^= buf[i];
            else
                b ^= buf[i];
        }
        printf( "%u %u\n", b<a?b:a, a<b?b:a );
    }
}

第 3 楼

得分:0

此题要求不能使用数组存储n个整数，且要使用快读

第 4 楼

得分:0

真不好意思才看到忘记发表内个限制了，不过这题用32个数组呢

第 5 楼

得分:0

以下是引用xiaohuo66在2020-11-4 09:05:00的发言：

此题要求不能使用数组

只用“抑或”肯定需要遍历两次，遍历两次就肯定需要存储。
如果可以使用“抑或”之外的运算，那么再来一种运算，可以从两个运算结果中通过“解方程组”的手段还原出两个数。（没时间写代码了，包工头让我去搬砖）

第 6 楼

得分:0

回复 4楼 xiaohuo66

可以使用数组但不能用数组存入该n个整数，不一定只用异或运算吧，也可以位运算应该

谢谢

第 7 楼

得分:0

回复 5楼 rjsp

可以使用数组但不能用数组存入该n个整数，不一定只用异或运算吧，也可以位运算应该

谢

第 8 楼

得分:20

只想到这种丑陋的办法

#include <stdio.h>

int main( void )
{
    unsigned t;
    scanf( "%u", &t );
    while( t-- )
    {
        unsigned n;
        scanf( "%u", &n );

        unsigned zero_cnt = 0;
        unsigned a[32][2] = { 0 };
        for( unsigned i=0; i!=n; ++i )
        {
            unsigned value;
            scanf( "%u", &value );

            zero_cnt += (value==0);
            for( unsigned i=0; i!=32; ++i )
                a[i][value>>i&1] ^= value;
        }

        for( unsigned i=0; i!=32; ++i )
        {
            if( (zero_cnt%2!=0) == (a[i][0]==0 || a[i][1]==0) )
            {
                printf( "%u %u\n", a[i][1]<a[i][0]?a[i][1]:a[i][0], a[i][0]<a[i][1]?a[i][1]:a[i][0] );
                break;
            }
        }
    }
}

设不相同的两个数为 x 和 y
因为 x 和 y 不同，所以这两个数必然有至少一个bit不相同
根据这个bit是0还是1，分成两组，那么x和y就必然分在两个不同的组内
每个组分别进行各自元素的异或，就得到了x和y

但是，现在不知道哪个bit不相同，只能将32个bits分别处理（这就是代码中定义 unsigned a[32][2] 的原因）
组内各自异或后得到两个可能数值对，分别是 {x,y} 和 {0,x^y}
这两个数值对中，我也不知道哪个数值对是{x,y}
所以我又统计 0 的数目，（这就是代码中定义 unsigned zero_cnt 的原因）
如果0的数目是偶数，那么x和y都不是0，那我只要在这两个数值对中选都不是0的那个就行了
如果0的数目是奇数，那么x和y必然有一个是0；如果x和y必然有一个是0，那么 {x,y} 和 {0,x^y} 是相同的，所以我只要在这两个数值对中选其中一个是0的那个就行了。

第 9 楼

得分:0

回复 8楼 rjsp

感谢 ac了我就是这个意思