MOJ#5 Max [贪心]

Author Avatar
ajcxsu 9月21日
  • 在其它设备中阅读本文章

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

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://acxblog.site/archives/moj-5.html
博客以 CC BY-NC-SA 4.0 协议进行许可。