AND, OR and square sum

这个位操作题出的挺好的。

首先观察题中“操作”的规律，比如可以看到$(x \texttt{ AND } y - x \texttt{ AND } y) = x \texttt{ XOR } y$， 所以XOR最大的先来？能找到一些规律，但死胡同比较多。

再观察会发现，$a=x \texttt{ AND } y$, $b=x \texttt{ OR } y$，$a$和$b$中间的$1$，和$x$和$y$中间的1，是一样多的，数量没有发生变化的。 每次操作是把1向OR那边集中。而且我们应该有：$a^2 + b^2 \geq x^2 + y^2$，因为总和不变，分得更开了，所以平方和变大。

我们可以想到，这样不停操作下去，到最后不能再操作的终态是确定的，就是如果按从大到小排序， 最终的数会变成把每一位上所有的$1$都集中到最前面的数字上面。例如原来数据是$1, 2, 3, 4, 5$（二进制是$001, 010, 011, 100, 101$）， 可以统计到第$0$位有$3$个$1$，第$1$位$2$个$1$，第$2$位$2$个$1$. 所以最后就会变成：

         111 - 7
         111 - 7
         001 - 1
         000 - 0
         000 - 0

这样我们就可以看出来，问题解法就是数每位上1的个数，然后生成最后的数字序列，求平方和就可以了。 $\mathcal{O}(n \log A)$，$A$是$a_i$的最大值。

再次说明仔细观察，在纸上算例子，然后找规律，是ad-hoc题目的主要解法。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
 
int n;
int cnt[25];
ll ans;
 
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        int a;
        scanf("%d", &a);
        for (int i = 0; i < 20; i++)
            if (a & (1 << i))
                cnt[i]++;
    }
    for (int i = 0; i < n; i++) {
        int a = 0;
        for (int j = 0; j < 20; j++)
            if (cnt[j] > i)
                a += 1 << j;
        ans += (ll)a*a;
    }
    printf("%lld", ans);
 
    return 0;
}