logo头像

野渡's小小知识乐园

2.异或

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

异或


题目原链接: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.示例

输入

1
2
3 10  
6 5 10

输出

1
2

5.解题思路

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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.实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
*
*@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;
}

能通过的解法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#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。