异或 - 简书

异或

题目原链接：https://www.nowcoder.com/practice/fc05f68c5f47438db54c6923ef23cf4a?tpId=85&&tqId=29876&rp=3&ru=/activity/oj&qru=/ta/2017test/question-ranking

1.题目描述

给定整数m以及n各数字A1,A2,..An，将数列A中所有元素两两异或，共能得到n(n-1)/2个结果，请求出这些结果中大于m的有多少个。

2.输入描述

第一行包含两个整数n,m.
第二行给出n个整数A1，A2，...，An。
数据范围:
对于30%的数据，1 <= n, m <= 1000
对于100%的数据，1 <= n, m, Ai <= 10^5

3.输出描述

输出仅包括一行，即所求的答案

4.示例

输入

3 10  
6 5 10

输出

5.解题思路

参考链接：https://blog.csdn.net/qq_30507287/article/details/68947863。

考虑用字典树来解决该题，用示例中6、5、10来构建一颗如下字典树(虚线表示不用)：

graph TB
root-->0
root-->1
0-.->00(0)
0-->01(1)
01-->010(0)
01-->011(1)
011-->0110(0)
011-.->0111(1)
010-.->0100(0)
010-->0101(1)
1-->10(0)
1-.->11(1)
10-.->100(0)
10-->101(1)
101-->1000(0)
101-.->1001(1)

从已有的数据中选一个数记为a，遍历该字典树（二叉树）,求所有与a异或大于m的数的个数，分情况讨论：

如果a的当前位为0，m的当前位为0，那么明显父节点的右子树的所有数与a异或都大于m；但左子树不能确定，需要继续查询。
如果a的当前位为1，m的当前位为0，那么明显父节点的左子树的所有数与a异或都大于m；但右子树不能确定，需要继续查询。
如果a的当前位为0，m的当前位为1，那么明显父节点的左子树中的数和a异或一定小于m，查询结束；右子树的数不能确定，需要继续查询。
如果a的当前位为1，m的当前位为1，那么明显父节点的右子树中的数和a异或一定小于m，查询结束；左子树的数不能确定，需要继续查询。

具体求解过程如下:

（1）依次读取n,m,将n个数依次放入数组并且构建对应的字典树。
（2）获取获取数组中的数，查询字典树，计算与其异或值大于m的数的个数。
（3）得到的count除2，因为如果a^b大于m,那么b^a也会大于m。

6.实现代码

*
*@bref:暴力求解，好像是可以通过80%，果然暴力还是不行
*
int main()
{
    int n,m,i,j,result,count=0,*value;
    cin>>n>>m;
    value=new int[n];
    
    for(i=0;i<n;i++)
    {
        cin>>value[i];
    }
    for(i=0;i<n-1;i++)
    {
        for(j=i+1;j<n;j++)
        {
            result=value[i]^value[j];
            if(result>m) count++;
        }
    }
    cout<<count<<endl;
    return 0;
}

能通过的解法：

#include<iostream>
using namespace std;
/*
* @bref:参考了大神们的思路，服气
*       了解字典树之后，理解这个题的解法就好多了
*/

//定义字典树节点
class trieTree
{
    public:
      int num;
      trieTree *son[2];
    public:
      trieTree(int num) 
      {
          this->num=num;
          son[0]=nullptr;
          son[1]=nullptr;
      }
};

int foo;
static void insert(int a,trieTree *current)
{
    //插入每一个节点，17位所能表示的最大值位131071
    for(int i=16;i>=0;i--)
    {
        foo=(a>>i)&1;//获取对应的位
        if(current->son[foo] == nullptr)
        {
            current->son[foo]=new trieTree(0);
        }
        current=current->son[foo];
        current->num++;//记数加1
     }
}

//查询结果
static int query(trieTree *root,int a,int m,int i)
{
    if(root==nullptr) return 0;
    
    trieTree *current=root; 
    int aDigit=(a>>i)&1;
    int mDigit=(m>>i)&1;
    if(aDigit==0 && mDigit==0)
    {
        int p=(current->son[1]==nullptr? 0:current->son[1]->num);
        int q=query(current->son[0],a,m,i-1);
        return p+q;
    }
    else if(aDigit==1 && mDigit==0)
    {
        int q=(current->son[0]==nullptr? 0:current->son[0]->num);
        int p=query(current->son[1],a,m,i-1);
        return p+q;
    }
    else if(aDigit==0 && mDigit==1)
    {
        if(current->son[1]==nullptr) return 0;
        return query(current->son[1],a,m,i-1);
    }
    else if(aDigit==1 && mDigit==1)
    {
        if(current->son[0]==nullptr) return 0;
        return query(current->son[0],a,m,i-1);
    }
    return 0;
}

int main()
{
    int m,n,*data;
    long count=0;
    trieTree root(-1);
    
    cin>>n>>m;
    data=new int[n];

    for(int i=0;i<n;i++)
    {
        cin>>data[i];
        insert(data[i],&root);//将所有的数
    }
       
    for(int i=0;i<n;i++)
    {
        count+=query(&root,data[i],m,16);
    }
    cout<<count/2<<endl;
    return 0;
}

6.思考与分析

这种题目的第一思路是暴力求解，虽然很大概率是不行的，但不妨一试，能想出合理高效的求解方案不是每一个人都能做到的，问题的抽象能力、联想能力往往是解题的关键，常备知识，遇到问题才能直击痛点，庖丁解牛。
在写这个题的时候，我自己实现了代码，但是感觉完全没问题，然后提交之后一直只通过80%，我后来花了将近两天的时间近乎一直在想这个题，最后突然灵光发现是用来存结果的count值是int型，而实际结果要大于int型所能表示的范围。真的服气.......我发誓以后存结果的数一定用long。

异或

异或