Problem 4. 字典树考试【算法赛】

思路：贡献法，二进制按位操作

Accode

#include <bits/stdc++.h>
using namespace std;
int main()
{
  // 请在此输入您的代码
  ios::sync_with_stdio(false);
    int n;
    vector<int> q;
    cin>>n;
    for(int i=0;i<n;i++){
        int x;
        cin>>x;
        q.push_back(x);
    }
    long long  ans = 0;
    //枚举int里每个二进制位1的个数
    for(int i=0;i<31;i++){
        int  sum = 0;
        for(int j=0;j<n;j++){
            if(q[j]>>i&1==1) sum++;
        }
        //爆int
        ans+=(long long)sum*(sum-1)/2;
    }
    cout << ans<<endl;
  return 0;
}