Codeforces Round #672 (Div. 2 B. Rock and Lever (位运算)

题意:给你一组数,求有多少对\((i,j)\),使得\(a_{i}\)&\(a_{j}\ge a_{i}\ xor\ a_{j}\).

题解:对于任意两个数的二进制来说,他们的最高位要么相同要么不相同,如果相同,那么肯定是满足题目条件的,因为异或是不进位的加法,所以我们只要找到所有最高位相同的数的个数,用桶存下来,然后再对他们求个和就行了.

代码:

int t;
int n;
ll x;
map<ll,ll> mp;int main() {
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>t;
    while(t--){
    cin>>n;
    mp.clear();
    for(int i=1;i<=n;++i){
    cin>>x;
    ll cnt=0;
    while(x){
    cnt++;
    x>>=1;
    }
    mp[cnt]++;
    }
    ll res=0;
    for(auto w:mp){
    res+=w.se-1+(w.se-1)*(w.se-2)/2;
    }
    cout<<res<<endl;
    }    return 0;
}