Luogu P9509『STA - R3』Aulvwc 题解
简化一下题意，对于原集合 $S$，就是找原集合的两个子集 $S_1,S_2$，使得 $S_1 \cup S_2 = S,S_1 \cap S_2 = \empty$，$S_1,S_2$ 的平均数等于 $S$ 的平均数
注意到特殊性质中的 $\sum a_i = 0$，这个很好写，分成一个正集合和一个负集合，每个跑一个可行性背包 $f,g$，$f_i,g_i$ 表示 $S_1,S_2$ 中能否存在 $i$，如果 $f_i = g_i，i \in [1,$ $\sum a_j \over 2$ $(a_j > 0))$，那么$S_1,S_2$ 的平均数等于 $S$ 的平均数
考虑把整体情况转化，把 $a_i$ 减掉平均数，那么 $\sum a_i = 0$，这样就成了特殊性质。按照特殊性质的方法处理就行。
但时间复杂度是 $O(n^2k)$($k$ 是值域，题中为 $5\times 10^3$)，大约是个 $5 \times 10^9$，会炸，考虑用 bitset 优化可行性背包，f = f|=(f<<a_i)，时间复杂度优化到了 $10^8$ 左右，可以通过。
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;
}
|
