题目描述
The Hamming Distance between two integers is the number of different digits between their binary representation. For example the hamming distance between 4(=01002) and 14(11102) is 2.
Given N integers, A1, A2, … AN, find out the total hamming distance of all pairs of them.
输入
The first line contains an integer N.
The second line contains N integers denoting A1, A2, … AN.
For 80% of the data: 1 <= N <= 1000
For 100% of the data: 1 <= N <= 100000 1 <= Ai <= 1000000000
输出
The total hamming distance
样例输入
3
1 2 3
样例输出
4
题意
输入一个n,接下来n个数,然后求这个n个数两两比较二进制位数不同的总和
思路
首先想到暴力n²枚举,优化思路变为 对于每一个二进制位,统计一下N个数中,有几个在这一位是0,有几个在这一位是1。假设有x个是0,y个是1,那么在这一位的产生的距离就是xy。如果我们把32个二进制位看成是常数,那么时间复杂度是O(N)的。
AC代码
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define LL long long
#define ULL unsigned long long
#define bug(x) cout<<"bug-----"<<x<<endl
#define R(i,n) for(int i = 0; i < n; i++)
using namespace std;
const int mod= 1e9+7;
const int maxn = 110 +10;
LL a[33+10];
LL b[33+10];
int main(){
//freopen("C:\\Users\\admin\\Desktop\\1.in","r",stdin);
//freopen("C:\\Users\\admin\\Desktop\\1.out","w",stdout);
std::ios::sync_with_stdio(false);
int n;
cin>>n;
for(int i=0;i<n;i++)
{
LL t;
cin>>t;
for(int i=0;i<=34;i++)
{
if(t&1)
{
a[i]++;
}
else
{
b[i]++;
}
t>>=1;
//cout<<t<<endl;
}
}
LL ans=0;
for(int i=0;i<=34;i++)
{
ans+=a[i]*b[i];
}
cout<<ans<<endl;
return 0;
}