1893: 985的数学难题
Time Limit: 2 Sec
Memory Limit: 128 MB
Submit: 174
Solved: 43
Submit
Status
Web Board
Description
985有n个正整数,他想快速知道下面函数的返回值
int a[N+1];
long long Solve() {
int i, j;
long long ans = 0;
for(i = 1; i <= N; i++) {
for(int j = i + 1; j <= N; j++) {
ans += a[i] + a[j] + (a[i] ^ a[j]) + (a[i] | a[j]) + (a[i] & a[j]);
}
}
return ans;
}
注:^表示异或运算。
Input
第一行输入一个整数t,代表有t组测试数据。
每组数据第一行输入一个整数代表元素个数,接下来一行输入n个正整数a[]。
注:1 <= t <= 30,1 <= n,a[] <= 100000。
Output
一个整数代表最后的返回值ans。
Sample Input
211021 1
Sample Output
04
HINT
Source
题意即为n个数,两两相加,相或,相与,相异或,求最后的和。
#include<stdio.h>
#include<algorithm>
using namespace std;
bool cmp(long long a,long long b)
{
return a>b;
}
int main()
{
int t,n,i;
long long ans,sum,ant;
long long a[100010];
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
sum=0;
ans=0;
for(i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
sum+=a[i];
}
ans+=sum*(n-1);
sort(a+1,a+1+n,cmp);
int m=1;\\判断在2进制的哪一位
while(a[1])
{
ant=0;
for(i=1;i<=n;i++)
{
if(a[i]&1)
ant++;
a[i]>>=1;
}
ans+=m*(ant*(ant-1)>>1); \\相与,只有两两都为1结果才为一
ans+=((n-ant)*ant+(ant*(ant-1)>>1))*m;\\相或,
ans+=(n-ant)*ant*m;\\相异或
m<<=1;
}
printf("%lld\n",ans);
}
return 0;
}
转载请注明原文地址: https://ju.6miu.com/read-1298603.html