P9277 [AGM 2023 资格赛] 反转 题解

· · 题解

首先发现题目要求使其最大的式子的每一个二进制位计算是独立的，单独拆出二进制位的第 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;
}