专栏文章

CF2147E

xxujindong_
CF2147E题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mint7y34
此快照首次捕获于
2025/12/02 07:58
3 个月前
此快照最后确认于
2025/12/02 07:58
3 个月前
查看原文
对于 ans=0∼31ans=0\sim31，求使 popcount⁡\operatorname{popcount} 增加到 ansans 的最小操作数。显然，根据二进制的性质，我们会让前若干个 00 变成 11。假设我们让 0∼i0\sim i 位变成 11，不难感受到一个贪心：从 ii 位枚举到 00 位，若当前位为 00，选择代价 2i−aj mod 2i2^i-a_j\bmod2^i 最小的 aja_j 增加使这一位变成 11。可以归纳证明每一步都是不劣的，假设处理第 ii 位时我们选择让 aka_k 增加，因为 aj mod 2i≥ak mod 2ia_j\bmod2^i\geq a_k\bmod2^i，在贪心策略里我们可以将 aka_k 增加到 aja_j 的初始值。
现在直接模拟，复杂度 O(nlog⁡2V+qlog⁡log⁡V)O(n\log^2V+q\log\log V)。
CPP
#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;
}
还可以更快。先预处理，对每个位 ii 将 aa 按照  mod 2i\bmod2^i 排序。这可以 O(nlog⁡V)O(n\log V) 完成，因为按  mod 2i+1\bmod 2^{i+1} 排序后，我们将第 i+1i+1 位为 00 和为 11 的两个数组归并。接下来枚举 ans=0∼31ans=0\sim31，过程中对每个 ii，我们需要找到第一个未访问的数。这随着 ansans 增加是单调不降的，此部分可以 O(log⁡2V)O(\log^2V) 完成。复杂度 O(nlog⁡V+Tlog⁡2V+qlog⁡log⁡V)O(n\log V+T\log^2V+q\log\log V)。
CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...