CF2147E

xujindong_ · 2025-09-23 15:54:19 · 题解

对于 ans=0\sim31，求使 \operatorname{popcount} 增加到 ans 的最小操作数。显然，根据二进制的性质，我们会让前若干个 0 变成 1。假设我们让 0\sim i 位变成 1，不难感受到一个贪心：从 i 位枚举到 0 位，若当前位为 0，选择代价 2^i-a_j\bmod2^i 最小的 a_j 增加使这一位变成 1。可以归纳证明每一步都是不劣的，假设处理第 i 位时我们选择让 a_k 增加，因为 a_j\bmod2^i\geq a_k\bmod2^i，在贪心策略里我们可以将 a_k 增加到 a_j 的初始值。

现在直接模拟，复杂度 O(n\log^2V+q\log\log V)。

#include<bits/stdc++.h>
using namespace std;
int t,n,m,a[100005],temp[100005];
long long ans[32];
int main(){
  ios::sync_with_stdio(0),cin.tie(0),cin>>t;
  while(t--){
    cin>>n>>m;
    int s=0;
    for(int i=1;i<=n;i++)cin>>a[i],s|=a[i];
    memset(ans,0x3f,sizeof(ans)),ans[__builtin_popcount(s)]=0;
    for(int i=0;i<=30;i++){
      if(s>>i&1)continue;
      long long num=0;
      for(int j=1;j<=n;j++)temp[j]=a[j];
      for(int j=i;j>=0;j--){
        int now=0,pos=1,maxn=0;
        for(int k=1;k<=n;k++)now|=temp[k];
        if(now>>j&1)continue;
        for(int k=1;k<=n;k++)if((temp[k]&((1<<j)-1))>=maxn)pos=k,maxn=temp[k]&((1<<j)-1);
        num+=(1<<j)-maxn,temp[pos]+=(1<<j)-maxn;
      }
      s|=1<<i,ans[__builtin_popcount(s)]=num;
    }
    for(int i=30;i>=0;i--)ans[i]=min(ans[i],ans[i+1]);
    for(int i=1,b;i<=m;i++)cin>>b,cout<<upper_bound(ans,ans+32,b)-ans-1<<'\n';
  }
  return 0;
}

还可以更快。先预处理，对每个位 i 将 a 按照 \bmod2^i 排序。这可以 O(n\log V) 完成，因为按 \bmod 2^{i+1} 排序后，我们将第 i+1 位为 0 和为 1 的两个数组归并。接下来枚举 ans=0\sim31，过程中对每个 i，我们需要找到第一个未访问的数。这随着 ans 增加是单调不降的，此部分可以 O(\log^2V) 完成。复杂度 O(n\log V+T\log^2V+q\log\log V)。

#include<bits/stdc++.h>
using namespace std;
int t,n,m,a[100005],b[32][100005],mask;
long long ans[32];
bool vis[100005];
bool cmp(int x,int y){
  return (a[x]&mask)>(a[y]&mask);
}
int main(){
  ios::sync_with_stdio(0),cin.tie(0),cin>>t;
  while(t--){
    int s=0;
    memset(ans,0x3f,sizeof(ans)),cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i],s|=a[i];
    ans[__builtin_popcount(s)]=0;
    for(int i=0;i<=31;i++)for(int j=1;j<=n;j++)b[i][j]=j;
    mask=(1ll<<31)-1,sort(b[31]+1,b[31]+n+1,cmp);
    for(int i=30;i>=0;i--){
      for(int j=1;j<=n;j++)b[i][j]=b[i+1][j];
      int mid=1;
      while(mid<=n&&a[b[i][mid]]>>(i+1)&1)mid++;
      mask=(2ll<<i)-1,inplace_merge(b[i]+1,b[i]+mid,b[i]+n+1,cmp);
    }
    int p[32];
    for(int i=0;i<=31;i++)p[i]=1;
    for(int i=0;i<=30;i++){
      if(s>>i&1)continue;
      for(int j=1;j<=n;j++)vis[j]=0;
      long long num=0;
      for(int j=i;j>=0;j--){
        while(p[j]<=n&&vis[b[j][p[j]]])p[j]++;
        if(p[j]<=n&&~a[b[j][p[j]]]>>j&1)vis[b[j][p[j]]]=1,num+=(1<<j)-(a[b[j][p[j]]]&((1<<j)-1));
        if(p[j]>n)num+=1<<j;
      }
      s|=1<<i,ans[__builtin_popcount(s)]=num;
    }
    for(int i=30;i>=0;i--)ans[i]=min(ans[i],ans[i+1]);
    for(int i=1,b;i<=m;i++)cin>>b,cout<<upper_bound(ans,ans+32,b)-ans-1<<'\n';
  }
  return 0;
}