CF1868B2 Candy Party (Hard Version) 题解

Problem - 1868B2 - Codeforces

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");
}