- \(\sum d_i <=5*10^7\)一定是解题的突破口;可是,该怎么利用这个条件呢?
- 不妨更进一步——考虑数据的特征,发现数字的种类是有限的
点击查看代码
#include <bits/stdc++.h>
using namespace std;
int d[2000005],r[2000005];
map<int,long long>q;
int read1()
{
char cc=getchar();
while(!(cc>=48&&cc<=57))
{
if(cc=='-')
{
break;
}
cc=getchar();
}
bool f=false;
int s=0;
if(cc=='-')
{
f=true;
}
else
{
s=cc-48;
}
while(1)
{
cc=getchar();
if(cc>=48&&cc<=57)
{
s=s*10+cc-48;
}
else
{
break;
}
}
if(f==true)
{
s=-s;
}
return s;
}
int lowbit(int n)
{
return n&(-n);
}
int calc(int x)
{
int s=0;
while(x!=0)
{
x-=lowbit(x);
s++;
}
return s;
}
int main()
{
int n;
cin>>n;
int cnt=0;
for(int i=1;i<=n;i++)
{
d[i]=read1();
if(q.find(d[i])==q.end())
{
cnt++;
r[cnt]=d[i];
}
q[d[i]]++;
}
long long ans=0;
for(int i=1;i<=cnt;i++)
{
for(int j=1;j<=cnt;j++)
{
ans=ans+q[r[i]]*q[r[j]]*(calc(r[i]+r[j])+calc(abs(r[i]-r[j])));
}
}
cout<<ans<<endl;
return 0;
}