Time Limit: 2 Sec Memory Limit: 128 MBSubmit: 153 Solved: 35SubmitStatusWeb 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
2
1
10
2
1 1
Sample Output
0
4
1 #include<cstdio>
2 #include<
string.h>
3 #include<algorithm>
4 using namespace std;
5 #define INF 0xfffffff
6 long long n,ans;
7 long long num[
100000+
11];
8 bool cmp(
int a,
int b)
9 {
10 return a>
b;
11 }
12 int main()
13 {
14 int i,T;
15 scanf(
"%d",&
T);
16 while(T--
)
17 {
18 scanf(
"%lld",&
n);
19 ans=
0;
20 for(i=
1;i<=n;i++
)
21 {
22 scanf(
"%d",&
num[i]);
23 ans+=
num[i];
24 }
25 ans*=(n-
1);
26 sort(num+
1,num+n+
1,cmp);
27 long long mul=
1,ant;
28 while(num[
1])
29 {
30 ant=
0;
31 for(i=
1;i<=n;i++
)
32 {
33 if(num[i]&
1)
//计算从右往左每一位上，n个数字1和个数
34 ant++
;
35 num[i]>>=
1;
36 }
37 ans+=
2*(((n-ant)*ant+(((ant-
1)*ant)>>
1))*mul);
/* a|b=a^b+a&b;所以二倍或；也可分别求出异或和与
38 ans+=(((ant-1)*ant)>>1)*mul; 与运算，所有的这位数为1的数相结合
39 ans+=((n-ant)*ant)*mul;异或运算，这一位为0的和这一位为1的相结合 */
40 mul<<=
1;
//二进制转为十进制的时候需要*2的n次方、
41 }
42 printf(
"%lld\n",ans);
43 }
44 return 0;
45 }
View Code
转载于:https://www.cnblogs.com/llal/p/5753935.html
