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;

}

巴特西

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

最新文章

热门文章