1893: 985的数学难题

Time Limit: 2 Sec  Memory Limit: 128 MB

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;
}
注:^表示异或运算。

</div>

Input

第一行输入一个整数t,代表有t组测试数据。
每组数据第一行输入一个整数代表元素个数,接下来一行输入n个正整数a[]。
注:1 <= t <= 30,1 <= n,a[] <= 100000。

</div>

Output

一个整数代表最后的返回值ans。

Sample Input

2
1
10
2
1 1

Sample Output

0
4


很显然不能直接写函数计算

这种类型的题目涉及到二进制运算

有定理

x^y+x&y==x|y

考虑二进制的每一位对结果的影响

比如1101、1001、1010进行上述运算

则可发现

从右到左每一位上有1的个数记为

cnt[0]~cnt[3]分别为

2、1、1、3

因为或运算除了0|0==0

其余都为1

也就是0|1+1|1

所以对于最右边运算后有效的1个数

为 cnt[0]*(n-cnt[0])+(cnt[0]*(cnt[0]-1))/2

而这些1所代表的个数要转变为十进制

则要乘上其对应的1<<0

所以核心代码为

for(int i=0; i<lx; i++) {
    res+=(1<<i)*(cnt[0][i]*cnt[1][i]+(cnt[1][i]-1)*cnt[1][i]/2);
}

其中lx代表最大数的二进制位数

至于求a[i]+a[j]

只需要把a[1~n]相加求和之后乘(n-1)

也就是每个数用了n-1次


#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
long long a[100200];
int main() {
    int T;
    scanf("%d",&T);
    while(T--) {
        int n;
        scanf("%d",&n);
        for(int i=0; i<n; i++) {
            scanf("%d",&a[i]);
        }
        sort(a,a+n);
        long long cnt[2][50];
        int lx=0;
        memset(cnt,0,sizeof(cnt));
        for(; a[n-1]>>lx!=0; lx++)
            for(int i=0; i<n; i++)
                cnt[a[i]>>lx&1][lx]++;
        long long res=0;
        for(int i=0; i<lx; i++) {
            res+=(1<<i)*(cnt[0][i]*cnt[1][i]+(cnt[1][i]-1)*cnt[1][i]/2);
        }
        res*=2;
        for(int i=0; i<n; i++) {
            res+=(n-1)*a[i];
        }
        printf("%lld\n",res);
    }
    return 0;
}

题目地址:【郑轻】[1893]985的数学难题

© DiDaPiPa all right reserved,powered by GitbookRevision Time: 2020-03-12 21:32:06

results matching ""

    No results matching ""