B. Arpa’s obvious problem and Mehrdad’s terrible solution

time limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output
There are some beautiful girls in Arpa’s land as mentioned before.

Once Arpa came up with an obvious problem:

Given an array and a numberx, count the number of pairs of indicesi, j(1 ≤ i < j ≤ n) such that , where is bitwisexoroperation (see notes for explanation).

Second line containsnintegersa1, a2, ..., an(1 ≤ ai≤ 105) — the elements of the array.
Output
Print a single integer: the answer to the problem.
Examplesinput

2 31 2

output

1

input

6 15 1 2 3 4 1

output

2

Note
In the first sample there is only one pair ofi = 1andj = 2. so the answer is1.

In the second sample the only two pairs arei = 3,j = 4(since ) andi = 1,j = 5(since ).

A bitwisexortakes two bit integers of equal length and performs the logicalxoroperation on each pair of corresponding bits. The result in each position is1if only the first bit is1or only the second bit is1, but will be0if both are0or both are1. You can read more about bitwisexoroperation here: https://en.wikipedia.org/wiki/Bitwise_operation#XOR.

题意：找出给定数列里两两异或值为x的组合个数a^b=x; x^a=b; x^b=a;x已经给定 我们只需循环a找是否有b与之对应。附AC代码：

1 #include<bits/stdc++.h> 
 2 using namespace std;
 3 int a[100010];
 4 int main(){
 5     map<int ,int > m;
 6     int n,x;
 7     cin>>n>>x;
 8     for(int i=1;i<=n;i++){
 9         scanf("%d",a+i);
10     }
11     long long ans=0;
12     for(int i=1;i<=n;i++){
13         if(m.count(x^a[i])) //找到返回1 否则返回0 
14         ans+=m[x^a[i]];
15         m[a[i]]++;
16     }
17     cout<<ans<<endl;
18     return 0;
19 }

原文链接: https://www.cnblogs.com/Kiven5197/p/6140000.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍