异或
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
输出
2
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。
