位位运算

思路

观察一下题中所说的“将其中一个数变为 \(a\) \(and\) \(b\)，另一个变成 \(a\) \(or\) \(b\)”，这个操作事实上是将\(a\)和\(b\)对应二进制位不同的\(0\)和\(1\)交换。如\(10\)和\(12\)，对应二进制分别为\(1010\)和\(1100\)，\(a|b=1110\)，\(a\) & \(b=1000\)，实质上是把\(a\)和\(b\)中对应位上的\(1\)挪到一边。

题目要求使所有数的平方和最大，显然在\(a、b\)在操作前后它们的和不变，要使平方和最大，就要使差最大。所以我们要尽可能把\(1\)集中到几个数上。做法是先把数排个序，从高位往低位扫，每次找到从左往右第一个第\(i\)位为\(0\)的数和从右往左第一个第\(i\)位为\(1\)的数，把它们的第\(i\)位交换即可。对每一位都进行这样的操作，最终得到的数组就是构成最佳答案的数组。

可能会有人对操作中的“交换第\(i\)位”有疑惑：我们对两个数操作的时候是把所有能移动的位都交换了，但在这里只移了一位，这样不会出问题吗？其实我们在这里虽然移了\(1\)位，但在之后的操作中一定会把剩下的位移动，因为我们是按位操作的。

代码

#include<bits/stdc++.h>
#define MAXN 100010
#define int long long
using namespace std;
int read()
{
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x*f;
}
inline void write(int x)
{
	if(x<0){putchar('-');x=-x;}
	if(x>9)write(x/10);
	putchar(x%10+'0');
}
bool cmp(int a,int b)
{
    return a>b;
}
int n,num[MAXN],vis[MAXN],ans=0;
int wei(int x)
{
    int ans=0;
    while(x)
    {
        x>>=1;
        ans++;
    }
    return ans;
}
string to_b(int x)
{
    string ans;
    while(x)
    {
        ans+=(x%2+'0');
        x>>=1;
    }
    if(ans.length()==0)ans+='0';
    reverse(ans.begin(),ans.end());
    return ans;
}
signed main()
{
    n=read();
    for(int i=1;i<=n;i++)
        num[i]=read();
    sort(num+1,num+n+1,cmp);
    int len=wei(num[1]);
    for(int i=len-1;i>=0;i--)
    {
        int l=1,r=n;
        while(1)
        {
            while(l<r&&(num[l]&(1<<i)))l++;
            while(l<r&&(!(num[r]&(1<<i))))r--;
            if(l>=r)break;
            num[l]|=(1<<i);
            num[r]-=(1<<i);
        }
    }
    for(int i=1;i<=n;i++)
        ans+=num[i]*num[i];
    write(ans);
    return 0;
}