自动搬运

查看原文

来自洛谷，原作者为

	falling_cloud 便舍此间繁华尽 留待梦中重游时

搬运于2025-08-24 22:46:57，当前版本为作者最后更新于2023-07-25 19:16:24，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

首先发现题目要求使其最大的式子的每一个二进制位计算是独立的，单独拆出二进制位的第 $i$ 位，设 $x$ 为该位为 $1$ 的数字个数。由于仅当选取的两个数中的一个数第 $i$ 位为 $0$，另一个数第 $i$ 位为 $1$ 时，产生 $2^i$ 的贡献，所以对于第 $i$ 位，总的贡献为 $x\times (n-x)\times 2^i$。

这时考虑对于某一位进行翻转带来的贡献，设原本有 $x_k$ 个数第 $k$ 位为 $0$，$y_k(=n-x_k)$ 个数第 $k$ 位为 $1$，贡献为 $x_ky_k$，在对第 $k$ 位进行一次 $0$ 翻转为 $1$ 的操作后，贡献变为 $(x_k+1)(y_k-1)=x_ky_k+y_k-x_k-1$，贡献差为 $y_k-x_k-1$。可以发现，这个贡献是具有单调性的。所以可以直接用优先队列维护。

实现方面细节不算很多，时间复杂度为 $O(P \log K)$。

#include <bits/stdc++.h>
#define ll long long
#define endl '\n'
using namespace std;
const int N = 1e5 + 5;
int a[N],sum1[50]={0},sum2[50]={0};
queue <int> q1[50],q2[50];
struct pi
{
	int x;	ll w;
	bool operator > (const pi &xx) const{return w>xx.w;}
	bool operator < (const pi &xx) const{return w<xx.w;}
};
priority_queue <pi,vector<pi>,less<pi> > q;
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);	cout.tie(0);
	int n,k,p,i,j,x,y,z;
	cin>>n>>k>>p;
	k--;
	for(i=1;i<=n;i++)	cin>>a[i];
	for(i=k;i>=0;i--)
		for(j=1;j<=n;j++)
			if((a[j]>>i)&1)	sum1[i]++,q1[i].push(j);
			else			sum2[i]++,q2[i].push(j);
	for(i=0;i<=k;i++)
	{
		if(sum1[i]>=sum2[i])	
			q.push((pi){i,1ll*(sum1[i]-sum2[i]-1)*(1<<i)});
		else
			q.push((pi){i,1ll*(sum2[i]-sum1[i]-1)*(1<<i)});
	}
	for(i=1;i<=p;i++)
	{
		x=q.top().x;
		y=q.top().w;
		q.pop();
		if(sum1[x]>=sum2[x])
		{
			cout<<q1[x].front()<<" "<<x<<endl;
			q2[x].push(q1[x].front());
			q1[x].pop();
			sum1[x]--,sum2[x]++;
			if(sum1[x]>=sum2[x])	
				q.push((pi){x,1ll*(sum1[x]-sum2[x]-1)*(1<<x)});
			else
				q.push((pi){x,1ll*(sum2[x]-sum1[x]-1)*(1<<x)});
		}
		else
		{
			cout<<q2[x].front()<<" "<<x<<endl;
			q1[x].push(q2[x].front());
			q2[x].pop();
			sum1[x]++,sum2[x]--;
			if(sum1[x]>=sum2[x])	
				q.push((pi){x,(1ll*sum1[x]-sum2[x]-1)*(1<<x)});
			else
				q.push((pi){x,(1ll*sum2[x]-sum1[x]-1)*(1<<x)});
		}
	}
	return 0;
}