網(wǎng)址：https://ac.nowcoder.com/acm/contest/4853/A

題目描述

給定n個(gè)整數(shù)，依次為a_1,a_2,...,a_n。求sum=a_i&a_j（i從一到n,j從一到n）“&”是二進(jìn)制的與運(yùn)算符。

輸入描述:

第一行一個(gè)整數(shù)n.
第二行n個(gè)整數(shù)a_i.

輸出描述:

一個(gè)整數(shù)表示上述求和式的答案.

輸入

5
1 2 3 4 5

輸出

33

備注:

1≤n≤1e5,0≤a_i≤1e8

題解:

這道題如果使用雙重for循環(huán)是一定會超時(shí)的。這里的a_i不是負(fù)數(shù)比較好做，如果a_i可以是負(fù)數(shù)，那么這道題就不算簽到題了。
首先將n個(gè)數(shù)都進(jìn)行二進(jìn)制討論，例如看看二進(jìn)制位從右數(shù)第三位上有多少個(gè)1，那么這一位的貢獻(xiàn)就是個(gè)數(shù)個(gè)數(shù)(i<<3),將所有位的貢獻(xiàn)加到一起，就是最后的結(jié)果。

AC代碼：

#include<iostream>
#include<cmath>
using namespace std;
#define ll long long int
int main(){
    ll sum=0;
    ll n,a,b[50]={0};
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a;
        for(int j=0;a;j++){
            if(a&1) b[j]++;
            a=a>>1;
        }
    } 
    for(int i=0;i<=40;i++){
    //    sum+=b[i]*b[i]*pow(2,i);
        sum+=b[i]*b[i]*(1<<i);
    }
    cout<<sum<<endl;
    return 0;
}

打卡第17天。過好每一天。