【zzuliOJ】1893 - 985的数学难题（位运算）

FishWang

发布于 2025-08-27 09:49:15

16200

代码可运行

运行总次数：0

代码可运行

点击打开题目

1893: 985的数学难题

Time Limit: 2 Sec Memory Limit: 128 MB Submit: 85 Solved: 13 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

hpu

依次看二进制末尾有多少数贡献了1，再根据位运算的性质进行计数即可。

代码如下：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define CLR(a,b) memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f
long long num[1000000];
long long ans;
bool cmp(int a,int b)
{
    return a > b;
}
int main()
{
    long long n;
    int u;
    scanf ("%d",&u);
    while (u--)
    {
        scanf ("%lld",&n);
        ans = 0;
        for (int i = 1 ; i <= n ; i++)
        {
            scanf ("%d",&num[i]);
            ans += num[i];
        }
        ans *= (n-1);
        sort(num+1,num+1+n,cmp);
        long long mul = 1;
        long long ant;		//二进制末尾为1的个数 
        while (num[1])
        {
            ant = 0;
            for (int i = 1 ; i <= n ; i++)
            {
                if (num[i] == 0)
                    break;
                if (num[i] & 1)
                    ant++;
                num[i] >>= 1;
            }
            ans += (((ant-1) * ant) >> 1) * mul;		//与运算 
            ans += ((n-ant) * ant + (((ant-1) * ant) >> 1)) * mul;		//或运算 
            ans += ((n-ant) * ant) * mul;		//异或运算 
            mul <<= 1;
        }
        printf ("%lld\n",ans);
    }
    return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2016-08-03，如有侵权请联系 cloudcommunity@tencent.com 删除

二进制