【CF1698C】3SUM Closure

发布时间 2023-12-17 18:59:26作者: Alric

题目大意:

判断一个数组是否满足其中任意三个元素之和均为数组的元素


如果一个元素出现的次数大于三,那么我们将这个元素的数量减到三,答案不会变。

另外,我们发现,如果数组至少中有三个正数,或者至少有三个负数,那么答案一定为NO。

如果上面的条件不满足,那么现在这个数组里的元素最多只有7个(2个正数,2个负数,3个0),这时用三重循环暴力枚举数组中的三个元素即可解决问题。

#include<bits/stdc++.h>
#define mid ((l+r)>>1)
using namespace std;
typedef long long ll;
ll n,a[200000+10];
int main(){
	int T;
	cin >> T;
	while(T--){
		bool ans=true;
		map<ll,ll> vis;
		ll cntp=0,cntm=0;
		cin >> n;
		for(ll i=1;i<=n;i++){
			cin >> a[i],vis[a[i]]=true;
			if(a[i]>0)cntp++;
			else if(a[i]<0)cntm++;
		}
		if(cntp>=3)ans=false;
		if(cntm>=3)ans=false;
		if(ans==false){
			cout << "NO" << endl;
			continue;
		}
		sort(a+1,a+1+n);
		vector<ll> c;
		c.push_back(a[1]),c.push_back(a[2]),c.push_back(a[3]);
		for(ll i=4;i<=n;i++)
			if((a[i]==a[i-1]&&a[i]==a[i-2]&&a[i]==a[i-3])==false)
				c.push_back(a[i]);
		for(ll i=0;i<c.size();i++)
			for(ll j=i+1;j<c.size();j++)
				for(ll k=j+1;k<c.size();k++)
					if(vis[c[i]+c[j]+c[k]]==false)
						ans=false;
		cout << (ans?"YES":"NO") << endl;
	}
	return 0;
}