1893: 985的数学难题

    xiaoxiao2025-04-30  17

    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
    最新回复(0)