简化一下题意，对于原集合 S，就是找原集合的两个子集 S1,S2，使得 S1∪S2=S,S1∩S2=∅，S1,S2 的平均数等于 S 的平均数
注意到特殊性质中的 ∑ai=0，这个很好写，分成一个正集合和一个负集合，每个跑一个可行性背包 f,g，fi,gi 表示 S1,S2 中能否存在 i，如果 fi=gi，i∈[1, 2∑aj (aj>0))，那么S1,S2 的平均数等于 S 的平均数
考虑把整体情况转化，把 ai 减掉平均数，那么 ∑ai=0，这样就成了特殊性质。按照特殊性质的方法处理就行。
但时间复杂度是 O(n2k)(k 是值域，题中为 5×103)，大约是个 5×109，会炸，考虑用 bitset 优化可行性背包，f = f|=(f<<a_i)，时间复杂度优化到了 108 左右，可以通过。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| #include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10;
int n,a[N];
bitset<2500000> fp,fn;
void solve(){
int sum=0,agv=0;
fp=fn=0;
vector<int> nn,pp;
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i],agv+=a[i];
if(agv%n!=0){
puts("No");
return;
}
agv/=n;
for(int i=1;i<=n;i++){
a[i]-=agv;
if(a[i]==0){
puts("Yes");
return;
}
(a[i]>0?pp:nn).push_back(abs(a[i]));
sum+=(a[i]>0?a[i]:0);
}
fp[0]=fn[0]=1;
for(int x:pp) fp|=(fp<<x);
for(int x:nn) fn|=(fn<<x);
fp[sum]=fn[sum]=fp[0]=fn[0]=0;
puts(((fp&fn)!=0?"Yes":"No"));
}
signed main(){
cin.tie(0)->ios::sync_with_stdio(0);
int q;cin>>q;
while(q--) solve();
return 0;
}
|
