题解：CF1868B2 Candy Party (Hard Version)

jiahongzhuo · 2026-04-28 08:22:33 · 题解

建议先看 B1 题解。
先求出总和，再求平均值，平均值不为整数直接判否，否则判 \lvert a_i-m \rvert 是否可以写成 2^x-2^y，此方法看 B1 题解，统计给与收二的整数次幂的个数，记作 f_i，给加受减。再统计出 \lvert a_i-m \rvert 本身为即为 2^x，如果 a_i<m ，s_i \to s_i+1 否则 t_i \to t_i+1 检查 f_i 如果不为 0 如果 f_i<0 则用 s_i 来补，不要忘了 f_{i+1} \to f_{i+1}-\frac{f_i}{2}，还需判断 \lvert s_i \rvert > \lvert \frac{f_i}{2} \rvert 且 \lvert f_i \rvert 是 2 的倍数。如果 f_i>0 同理拿 t_i 来补就做完了。

代码

#include <bits/stdc++.h> 
#define int long long  
using namespace std;    
int n,sum=0;    
int a[200005];
int p[35];
int f[35];
int s[35];
int t[35];
void solve(){
    memset(f,0,sizeof(f));
    memset(s,0,sizeof(s));
    memset(t,0,sizeof(t));
    if(sum%n!=0){
        cout<<"No"<<endl;
        return; 
    }
    int m=sum/n;
    for(int i=1;i<=n;i++){
        if(a[i]==m) {
            continue;
        }
        int k=abs(a[i]-m);
        if((k&-k)==k){
            int x=__lg(k);
            if(a[i]<m){
                s[x]++;
            }
            else{
                t[x]++;
            } 
        }
        int x=__lg(k)+1;
        int q=p[x]-k;
        int y=__lg(q);
        if(p[y]!=q){
            cout<<"No"<<endl;
            return;
        }
        if(a[i]<m){
            f[y]--; 
            f[x]++;     
        }
        else{
            f[y]++;
            f[x]--;     
        } 
    }   
    for(int i=0;i<=29;i++){
        if(f[i]==0){
            continue;
        } 
        int k=abs(f[i]);
        if(f[i]>0){
            if(t[i]==0){
                continue; 
            }
            if(k&1){
                cout<<"No"<<endl;
                return;
            }
            k/=2;
            if(k>abs(t[i])){
                cout<<"No"<<endl;
                return;         
            }
            k=f[i]/2;
            if(t[i]>0){
                f[i]+=-2*k;
                f[i+1]-=-k;
            }
            else{
                f[i]+=-2*k;
                f[i+1]-=-k;
            }           
        }
        else{
            if(s[i]==0){
                continue; 
            }
            if(k&1){
                cout<<"No"<<endl;
                return;
            }
            k/=2;
            if(k>abs(s[i])){
                cout<<"No"<<endl;
                return;         
            }
            k=f[i]/2;
            if(s[i]>0){
                f[i]+=-2*k;
                f[i+1]-=-k;
            }
            else{
                f[i]+=-2*k;
                f[i+1]-=-k;
            }           
        }
    }
    for(int i=1;i<=30;i++){
        if(f[i]!=0){
            cout<<"No"<<endl;
            return;         
        }
    }
    cout<<"Yes"<<endl;
}
signed main (){     
    p[0]=1;
    for(int i=1;i<=30;i++){
        p[i]=p[i-1]*2;
    }
    int aa;
    cin>>aa;
    while(aa--){
        sum=0; 
        cin>>n; 
        for(int i=1;i<=n;i++){
            cin>>a[i];
            sum+=a[i];
        }
        solve();
    }
}