每天一把: 2020-10-06
文章目录
题目思路代码实现
题目
原题链接:https://codeforc.es/problemset/problem/1420/B
思路
比较两个数的与运算和异或运算的大小。
思考位运算，只有当两个数二进制最高位相同时，与运算才会大于异或，否则异或大于与。
即我们要寻找最高位相同的数共有多少。
明显若有n个数最高位相同，则其能组成n*(n-1)/2个pair
最后注意所有数开longlong int会爆(我就这样WA了3次…)
代码实现
#include <iostream>
#include <cmath>
#include <cstring>
using namespace std
;
#define ll long long
ll t
, n
, num
;
ll a
[100];
int main()
{
ios
::sync_with_stdio(false);
cin
.tie(0);
cout
.tie(0);
cin
>> t
;
while (t
--)
{
memset(a
, 0, sizeof(a
));
cin
>> n
;
for (int i
= 1; i
<= n
; i
++)
{
cin
>> num
;
a
[(int)log2(num
) + 1]++;
}
ll cnt
= 0;
for (int i
= 1; i
<= 99; i
++)
{
if (a
[i
] != 0)
cnt
+= a
[i
] * (a
[i
] - 1) / 2;
}
cout
<< cnt
<< endl
;
}
return 0;
}
