cf1490

这。。。这就是div3嘛

A：Dense array

对每个间隔统计即可

per(){
    int n;cin>>n;
    for(int i=1;i<=n;++i){
      cin>>in[i];
    }
    int ans=0;
    for(int i=2;i<=n;++i){
      int ma=max(in[i-1],in[i]);
      int mi=min(in[i-1],in[i]);
      int cnt=0;
      while(mi*2<ma){
        cnt++;
        mi*=2;
      }
      ans+=cnt;
    }
    cout<<ans<<endl;
  }

B:Balanced Remainders

从0到1到2，再到0到1，如果多了就向后推，几次后就平了。。

per(){
    int n;cin>>n;
    int tmp;
    int n0=0,n1=0,n2=0;
    for(int i=1;i<=n;++i){
       cin>>tmp;
       if(tmp%3==1)n1++;
       else if(tmp%3==0)n0++;
       else n2++;
    }
    int num=n/3;
    int ans=0;
    if(n0>num){
      n1+=n0-num;
      ans+=n0-num;
      n0=num;
    }
    if(n1>num){
      n2+=n1-num;
      ans+=n1-num;
      n1=num;
    }
    if(n2>num){
      n0+=n2-num;
      ans+=n2-num;
      n2=num;
    }
    if(n0>num){
      n1+=n0-num;
      ans+=n0-num;
      n0=num;
    }
    if(n1>num){
      n2+=n1-num;
      ans+=n1-num;
      n1=num;
    }
    cout<<ans<<endl;
  }

C:Sum of Cubes

范围很小，把1-10000打表，同时计入map中，然后遍历之，查$n-i^3$是否在map中。

const int maxn=1005;
ll in[12000];
int main()
{
  std::ios::sync_with_stdio(false);std::cin.tie(0);
  map<ll,int> ma;
  for(ll i=1;i<=10000;++i){
    ma[i*i*i]=1;
    in[i]=i*i*i;
  }
  //cout<<ma[7993*7993*7993]<<endl;
  per(){
    ll n;cin>>n;
    int tag=0;
    for(ll i=1;i<=10000;++i){
      if(n<=in[i])break;
      if(ma[n-in[i]]==1){
        tag=1;break;
      }
    }
    if(tag){
      cout<<"YES"<<endl;
    }else cout<<"NO"<<endl;
  }
}

D:Permutation Transformation

建树，建st表然后递归即可

int f[maxn][maxn],in[maxn];
//f[i][j]表示[i,i+x^j-1]范围最大值
void STinit(int n){
  for(int i=1;i<=n;++i){
    f[i][0]=in[i];
  }
  int t=log(n)/log(2)+1;
  for(int j=1;j<t;j++){//长度2^j的区间最值分为2^{j-1}的两段
    for(int i=1;i<=n-(1<<j)+1;i++ ){
      f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
    }
  }
}
//两个区间覆盖l-r即可,中间重合无妨
int STQ(int l,int r){
  int k=log(r-l+1)/log(2);
  return max(f[l][k],f[r-(1<<k)+1][k]);
}
int ans[maxn];
void dfs(map<int,int>&ma,int l,int r,int lv){
  if(l==r){
    ans[r]=lv;
    return;
  }
  int nr=ma[STQ(l,r)];
  ans[nr]=lv;
  if(l<=nr-1)dfs(ma,l,nr-1,lv+1);
  if(r>=nr+1)dfs(ma,nr+1,r,lv+1);
  return ;
}
int main()
{
  std::ios::sync_with_stdio(false);std::cin.tie(0);
  per(){
    int n;cin>>n;
    map<int,int> ma;
    for(int i=1;i<=n;++i){
      cin>>in[i];
      ma[in[i]]=i;
    }
    STinit(n);
    dfs(ma,1,n,0);
    for(int i=1;i<=n;++i){
      cout<<ans[i]<<' ';
    }cout<<endl;
  }
  return 0;
}

E:Accidental Victory

input时将index和数字关联起来，然后处理数字。将其从小到大排序，求前缀和，然后遍历，如果前面加起来都没这个数大，此处中断，找到最后的一个中断位置即可，其后是能赢的。注意输出时要排序。

struct ui{ll val;int pos;bool operator<(const ui b)const{return this->val<b.val;}};
const int maxn=2e5+10;
ui in[maxn];
ll d[maxn];
int main()
{
  std::ios::sync_with_stdio(false);std::cin.tie(0);
  per(){
    int n;cin>>n;
    map<ll,int> ma;
    for(int i=1;i<=n;++i){
      cin>>in[i].val;
      in[i].pos=i;
    }
    sort(in+1,in+1+n);
    d[0]=0;int lp=-1;
    for(int i=1;i<=n;++i){
      d[i]=d[i-1]+in[i].val;
      if(d[i-1]<in[i].val)lp=i;
    }
    vector<int> ans;
    for(int i=lp;i<=n;++i){
      ans.push_back(in[i].pos);
    }
    sort(ans.begin(),ans.end());
    cout<<ans.size()<<endl;
    for(auto i:ans)cout<<i<<' ';
      cout<<endl;
  }
}

F:Equalize the Array

你不可能将少的变多，但可以将5次的变4次，所以排序，前缀和。
遍历，可能的答案是次数大于等于当前次数的数字个数乘当前次数。求最大值，然后用n减即可。
(排序范围搞错，wa#2*5)

struct ui{int times;int num;bool operator<(const ui b)const{return this->times>b.times;}};
const int maxn=2e5+1000;
ui in[maxn];
int main()
{
  std::ios::sync_with_stdio(false);std::cin.tie(0);
  per(){
    int n;cin>>n;
    int tmp;
    map<int,int> ma;
    for(int i=1;i<=n;++i){
      cin>>tmp;
      ma[tmp]++;
    }

    int tot=0;
    int sz=ma.size();
    map<int,int> mb;
    for(auto i:ma){
      mb[i.second]++;
    }
    for(auto i:mb){
      in[++tot]={i.first,i.second};
    }
    sort(in+1,in+1+tot);
    int ans=-1;
    int now=0;
    for(int i=1;i<=tot;++i){
      now+=in[i].num;
      ans=max(ans,now*in[i].times);
    }
    cout<<n-ans<<endl;
  }
}