CF1368

Codeforces Global Round 8

ABC略。

CF1368D

link

CF1368D题意

给定 \(n\) 个非负整数 \(a_1,\cdots,a_n\)。

你可以进行如下操作：选择两个不同的下标 \(i,j\) 满足 \(1\leq i,j\leq n\)，并将 \(a_i\gets a_i\ \mathsf{AND}\ a_j,\ a_j\gets a_i\ \mathsf{OR}\ a_j\)，两个赋值同时进行。AND 是按位与，OR 是按位或。

你可以进行任意次操作。求操作后所有数的平方和的最大值，即 \(\max \sum a_i^2\)。

CF1368D题解

首先观察这个操作，不难发现其实就是将一个数在二进制位中的 \(0\) 位尽可能用另一个数相同位置的 \(1\) 填入。
而且，因为是平方和最大，那么尽可能的填满一个数一定更优。
没了。

CF1368D代码

#include<bits/stdc++.h>
using namespace std;
inline int read(){
    int x = 0, f = 1;char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-') f = -1;ch = getchar();}
    while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48);ch = getchar();}
    return x * f;
}
const int maxn = 2e5 + 10;
int n, a[maxn];
int buc[30];
signed main(){
    n = read();
    for(int i = 1;i <= n;i++){
        a[i] = read();
        for(int j = 20;j + 1;j--)
            if(a[i] & (1 << j))buc[j]++;
        a[i] = 0;
    }
    long long sum = 0;
    for(int i = 1;i <= n;i++){
        for(int j = 20;j + 1;j--)
            if(buc[j]){a[i] |= (1 << j);buc[j]--;}
        sum += (long long)a[i] * a[i];
    }
    printf("%lld\n",sum);
    return 0;
}