CF2147E Maximum OR Popcount题解

· · 题解

CF2147E Maximum OR Popcount

安利一下我的博客。

思路

考虑求出最终或和中有 0,1,\dots ,31 个 1 时的最小操作次数。设原来的或和中有 cnt 个 1，我们要求达到 k 个 1。若 k\le cnt，答案显然为 0。若 k> cnt，则我们还需要将 k-cnt 个 0 变为 1。这里我们贪心将最低的 k-cnt 个 0 变为 1。这样是对的。若将更高位的 0 变为 1，那么我们需要将某个 a_i 改为形如 ?\dots ??100\dots00 的形式，这样还不如少操作一次变为 ?\dots ??011\dots11。若我们将某个 0 变为 1 时使某个原本存在的 1 变为 0，那么总的 1 的个数不变，还不如不改。

接着考虑第 j 位若为 0 应如何操作使其变为 1，我们贪心使得该次操作代价最小，最小代价为 \min (2^j-a_i \bmod 2^{j+1},2^j)。解释一下，最小代价中 a_i \bmod 2^{j+1} 可以看作将 a_i 的最低 j 位取出，显然操作低位不会影响高位。注意每个 a_i 都只能够操作一次，如果这里操作了，后续就不能再操作 a_i 了。对 2^j 取最小值是因为我们可以直接把之前的某个第 j 位为 0 的 a_i 加上 2^j 使其第 j 位变为 1 。以上的贪心是对的。因为如果我们当前不去操作 a_i 取更劣的 a_k，那么 a_k\to 2^j 的代价等同于 a_k\to a_i\to 2^j，不如这里先将 a_i 变为 2^j，后续需要 a_i 时再用 a_j 加到 a_i 即可。

代码

实现方法很多我的应该是最劣的。时间复杂度 O(n\log_{}^2{V}+q\log_{}{V} ) （V 是值域），应该可以更快。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
struct js
{
    int w,id;
};
bool operator <(js x,js y)
{
    return x.w<y.w;
}
int t,n,q,a[N],ans[35];
vector<js> s[35];
int cnt1[35],cnt2[35];
bool bj[N];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>t;
    while(t--)
    {
        cin>>n>>q;
        memset(cnt1,0,sizeof(cnt1));
        memset(cnt2,0,sizeof(cnt2));
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
            for(int j=0;j<=30;j++)
            {
                s[j].push_back({(1<<j)-a[i]%(1<<(j+1)),i});
                cnt1[j]+=((1<<j)&a[i])>0;
            }
        }
        int cnt=0;
        for(int j=0;j<=30;j++) 
        {
            s[j].push_back({1<<j,0});
            sort(s[j].begin(),s[j].end()); 
            if(cnt1[j]) cnt++;
        }
        int now=0;
        for(int i=0;i<=31;i++)
        {
            memset(bj,0,sizeof(bj));
            for(int j=0;j<=30;j++) cnt2[j]=cnt1[j];
            if(i<=cnt) ans[i]=0;
            else
            {
                while(now<=30&&cnt1[now]) now++; 
                int res=0;
                for(int j=now;j>=0;j--)
                {
                    if(!cnt2[j])
                    for(int k=0;k<s[j].size();k++)
                        if(!s[j][k].id||!bj[s[j][k].id])
                        {
                            bj[s[j][k].id]=1,res+=s[j][k].w;
                            for(int p=j-1;p>=0;p--)
                                cnt2[p]-=(a[s[j][k].id]&(1<<p))>0;
                            break;
                        }
                }
                now++,ans[i]=res;
            }
        }
        while(q--)
        {
            int x;
            cin>>x;
            int res=0;
            for(int i=0;i<=31;i++)
                if(ans[i]<=x) res=i;
                else break; 
            cout<<res<<"\n";
        }
        for(int i=0;i<=30;i++) s[i].clear();
    }
    return 0;
}