C. C. Blog

Security Research, Algorithm and Data Structure

51Nod 2493 二进制距离之和

Problem

小b有一个数组a,她想知道a中任意两个数之间二进制距离的总和。

两个整数的二进制距离指的是这两个数字的二进制数对应位不同的数量。

样例解释:

在二进制表示中,4表示为0100,14表示为1110,2表示为0010。 4和14的距离为2,因为0100和1110只有右数第2,4位不同。其他同理。 所以答案为: Distance(4, 14) + Distance(4, 2) + Distance(14, 2) = 2 + 2 + 2 = 6.

Solution

对于每一位,假设有x个1,那么这一位的距离是x*(n-x),相加即可。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<stdio.h>
typedef long long ll;
int n,x,sum[120];
ll ans=0;
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&x);
for(int j=0;j<=30;j++){
if(x&(1<<j)){
sum[j]++;
}
}
}
for(int i=0;i<=30;i++){
ans+=sum[i]*(n-sum[i]);
}
printf("%lld\n",ans);
return 0;
}
  • 本文作者: CCWUCMCTS
  • 本文链接: https://ccwucmcts.github.io/posts/59914/
  • 版权声明: 本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!