姑且算是复健，也姑且算是被卡住很久的题目，也姑且算是我自己想出来的题目。

Problem

有 $n$ 个不大于 $2^{20}$ 的整数，你可以进行任意次操作，每次操作选择两个数 $a,b$ 让他们分别变成 $a\&b, a|b$，问经过任意次操作后的最大平方和。

Solution

考虑这个操作实际上是对于两个数不同的位置，一个数的 $0$ 位全部将另一个数上的 $1$ 位全部抢夺了过去。

那么考虑这两个数，相同的部位为 $z$ ，不相同的部位分别为 $x,y$ ，则有 $a=z+x, b=z+y$。

产生的贡献为 $(z+x+y)^2+z^2-(z+x)^2-(z+y)^2=2xy$，恒为正。

一个简单的贪心策略即得出，进行无数次操作直到无法再次进行有意义的操作。

联想到类似珠排序的过程。将每一位的 $1$ 叠加起来然后坠落，得到的序列便无法再进行有意义的操作。

此时的和即为最大。

Code

#include<bits/stdc++.h>
using namespace std;

int bit[21];
typedef long long ll;
ll ans;

int main() {
    int n; scanf("%d", &n);
    ll a;
    for(int i=0; i<n; i++) {
        scanf("%d", &a);
        for(int j=0; j<21; j++)
            if(a&(1<<j)) bit[j]++;
    }
    bool con=1;
    while(con) {
        con=0, a=0;
        for(int i=0; i<21; i++)
            if(bit[i]) bit[i]--, a|=1<<i, con=1;
        ans+=a*a;
    }
    printf("%lld\n", ans);
    return 0;
}

本文链接：https://pst.iorinn.moe/archives/moj-5.html
许可： https://pst.iorinn.moe/license.html
若无特别说明，博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆