CF1868B1 Candy Party (Easy Version)

## 思路 首先想要均分糖果，那么必须满足糖果总数 $sum$ 是人数 $n$ 的倍数。 然后我们再取平均值，令 $s=\frac{sum} n$。 因为每个人必须收到一次糖果且只能送出一次糖果，所以对于每一个 $a_i$，我们首先需要满足 $a_i-s$ 可以被表示为 $2^x-2^y$。 令 $k=|a_i-s|$。 以二进制的方式来看，$\operatorname{lowbit}(k)$ 应该就是其中一个二次幂，是给出的还是收到的糖果数要看 $a_i$ 和 $s$ 的大小关系，那么 $k+\operatorname{lowbit}(k)$ 就应该是另外一个二次幂。 所以，如果 $k+\operatorname{lowbit}(k)$ 不是二次幂，就可以肯定无解。 那么我们再统计每个人需要接受和送出的糖果数的个数，如果接受和送出的糖果数的个数也不相等，那么就无解，否则，有解。 其实还有个特殊情况，那就是原本就有的糖与平均数相同，但是思考一下就会发现不影响结果。 我们只需要把原本就有的糖与平均数相同的人放在给糖过程中间，过一下手就好，比如 $a$ 要给 $b$ 一颗糖，而 $k$ 刚好拥有的糖就是平均数，那么只需要让 $a$ 给 $k$ 一颗糖，然后再由 $k$ 给 $b$ 一颗糖就好，可以发现这样增加一个转手的过程不影响答案，并且也满足了 $k$ 的需求，所以原本就有的糖与平均数一样不需要考虑，可以直接忽略 ## AC code ```cpp #include<bits/stdc++.h> using namespace std; inline long long lowbit(long long x){return x&(-x);} long long T,n,a[200005],sum,flag,k,low; map<long long,long long>m1,m2; inline bool sol() { scanf("%lld",&n),m1.clear(),m2.clear(),flag=sum=0;//多测记得清空 for(long long i=1;i<=n;++i) scanf("%lld",&a[i]),sum+=a[i]; if(sum%n) return 1; sum/=n; for(long long i=1;i<=n;++i) { a[i]-=sum;k=abs(a[i]);low=lowbit(k);k+=low; if(k!=lowbit(k)) return 1;//直接使用lowbit判断是不是二次幂 else if(a[i]>0) ++m1[k],++m2[low]; else if(a[i]<0) ++m1[low],++m2[k]; } for(auto i=m1.begin(),j=m2.begin();i!=m1.end()&&j!=m2.end();++i,++j) if(flag||i->first!=j->first||i->second!=j->second) return 1;//接受和送出的糖果数的个数是否一样 return 0; } int main() { scanf("%lld",&T); while(T--) if(sol()) printf("NO\n"); else printf("YES\n"); return 0; }   ```