题解：P9509『STA - R3』Aulvwc

www.luogu.com.cn

https://www.luogu.com.cn/problem/P9509

简化一下题意，对于原集合 $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$ 左右，可以通过。

cpp

#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; 
}

题解：P9509『STA - R3』Aulvwc

评论