题目大意

给定 \(n\)个非负整数，每次你可以选择两个数\(a,b\) ，将其中一个数变为 \(a\ and\ b\)，另一个变为 \(a\ or\ b\)，你可以进行多次操作，任何时候都可以停止，请最大化所有数的平方和。

输入格式
第一行包含一个正整数 \(n\)。

第二行包含 \(n\)个用空格分开的非负整数 \(a_i\)。

输出格式
一行一个非负整数表示最后最大化的所有数的平方和。

【输入样例】

5
1 2 3 4 5

【输出样例】

99

【样例解释】

一组最优方案是变成 \(7,0,7,0,1\)，答案是 \(99\)。

对于\(100\%\)的数据，\(N\le10^5,a_i\le10^6\)

基本思路

位运算当然要在二进制下考虑啦。我们先随便拉两个数出来\((101010)_2\) 和\((110101)_2\) 最后操作完就是 \((111111)_2\) 和\((100000)_2\) 那么我们就发现了这个操作就是将一个数所有可以挪过去的 \(1\) 挪过去。

上过初中的都知道，\(a^2+b^2\le (a+b)^2\),所以我们把所有数摞起来，把所有 \(1\) 尽量往一个数上推就可以了。

核心代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10;
int n,a,cnt[30];
ll ans;
int main(){
	freopen("andor.in","r",stdin);
	freopen("andor.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a;
		for(int j=0;j<=25;j++){
			if(a&(1<<j))
				cnt[j]++;
		}
	}
	for(int i=1;i<=n;i++){
		a=0;
		for(int j=0;j<=25;j++){
			if(cnt[j]>0){
				cnt[j]--;
				a|=(1<<j);
//				cout<<j<<":"<<a<<endl;
			}
		}
		ans+=1ll*a*a;
	}
	cout<<ans;
	return 0;
}