CF1368D-AND, OR and square sum

题目大意：给出一个数列a[]，每次操作可以在a[]中任选两个不同的元素a[i],a[j]，并令a[i]=a[i]&a[j], a[j]=a[i]|a[j]。问经过若干次操作后，a中所有元素的平方和的最大值为多少。

首先需要知道一个比较反常识的性质：x+y==(x&y)+(x|y)，观察左右两边式子做加法时每一位的情况以及能得出的结果就能大概知道为什么会是这样了。

由x+y==(x&y)+(x|y)，若(x&y)=x-k，则(x|y)=y+k。需要知道的是操作后左右两式平方和的变化，即

$(x-k)^2+(y+k)^2-(x^2+y^2)$

化简得

$2k(y-x+k)$

由于$k\geq 0$恒成立，如果$y\geq x$，那么上式总是非负。因此只要在a[]中任意找出两个不相等的元素操作，整个数列的平方和都不会减少。

然而，当(x|y)==y时，k的值为0，上面的式子就为0，整个数列的平方和也不会再增加了。因此需要一直操作，直到对于所有的(a[i]|a[j])==max(a[i],a[j])，最后求出平方和就行了。

还需要知道另一条性质：a[i]=a[i]&a[j], a[j]=a[i]|a[j]这一操作，不会改变整个数列中各个二进制位的1的数量。综合上面所分析的，要做的事情就是统计数列中各个二进制位1的个数，将它们尽可能集中到尽可能少的数上，然后输出这些集中完的数的平方和。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

#include <bits/stdc++.h>
using namespace std;
int a[200005];
int main()
{
    int n, i, sum[25], x;
    long long t, res = 0;
    memset(sum, 0, sizeof(sum));
    scanf("%d", &n);
    while (n--)
    {
        scanf("%d", &x);
        for (i = 0; x; i++, x >>= 1)
            sum[i] += x & 1;
    }
    for (t = 1; t;)
    {
        t = 0;
        for (i = 0; i < 25; i++)
        {
            if (sum[i] > 0)
            {
                t += 1 << i;
                sum[i]--;
            }
        }
        res += t * t;
    }
    printf("%lld", res);
    return 0;
}