Candy Party (Hard Version) - 洛谷
-
相信大家已经看过 Simple Version ，这题和上题不同之处就在于如果 \(b_i = 2^x\) ，他可以被分解成 \(2^x\) 或 \(2^{x+1}-2^x\) ，我们不妨起初固定一种方案，如果不满足条件后再把一部分换回去。
-
我们强制钦定起初都使用 \(2^{x+1}-2^x\) 的方法记录，记 \(cnt,add,del\) 分别表示 \(x\) 的次数(负数表示给出)， \(x\) 最多可以再被多选几次， \(x\) 最多可以再被给出几次
-
如果 \(cnt_i\) 为奇数的话一定无解，因为 \(2^x \Leftrightarrow 2^{x+1}-2^x\) 时次数的变化一定是 \(2\) 的倍数。如果 \(add,del\) 出现了不够的情况说明无解
-
最终复杂度 \(O(n \log V)\)
const int maxn=2e5+50;
int n,a[maxn],b[maxn];
int cnt[maxn],add[maxn],del[maxn];
int lowbit(int x){return (x&-x);}
void mian(int TwT){
read(n);For(i,1,n)read(a[i]);
ll ave=0;For(i,1,n)ave+=a[i];if(ave%n){puts("NO");return;}ave/=n;
For(i,1,n){
if(a[i]==ave)continue;b[i]=abs(a[i]-ave);
int x=lowbit(b[i]),y=b[i]+x;
if(lowbit(y)!=y){puts("NO");return;}
if(a[i]-ave>0)--cnt[__lg(x)],++cnt[__lg(y)];
else ++cnt[__lg(x)],--cnt[__lg(y)];
if(lowbit(b[i])==b[i]){
if(a[i]-ave>0)++add[__lg(b[i])];
else ++del[__lg(b[i])];
}
}
For(i,0,31){
if(cnt[i]&1){puts("NO");return;}
if(cnt[i]<0){
cnt[i]=-cnt[i];
if(add[i]*2<cnt[i]){puts("NO");return;}
cnt[i+1]-=cnt[i]>>1;
}
else{
if(del[i]*2<cnt[i]){puts("NO");return;}
cnt[i+1]+=cnt[i]>>1;
}
}
puts("YES");
}