Codeforces Round ＃803 (Div. 2) C. 3SUM Closure

C 3SUM Closure

题意

给出一个序列,问从中任意选三个数的和是否也在这个序列中

错因

 -3 -1 1 1 没有讨论，也无法讨论，所以应该直接brute force，不进行分类讨论

分析

这题在数据比较小的时候边界很多,但是我们在数据量很少的时候直接三重循环暴力即可

所以我们只需要考虑数据量足够大的情况.
我们把的数据都暴力计算.

我们记录下数列中所有正数和负数的数量.

正数或者负数超过2个肯定是不可以的

正数和负数各有一个时,它们必须互为相反数才满足条件.

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
bool cabs(int x, int y){
	return abs(x) > abs(y);
}	
int a[2000009];
int main(){
	std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int t;
 	cin >> t;
 	while(t -- ) {
 		int n, c = 0, c2 = 0;
 		cin >> n;
 		for (int i = 0; i < n; i ++ ) {
 			cin >> a[i];
 			c += a[i] > 0;
 			c2 += a[i] < 0;
 		}
 		if(c > 2 || c2 > 2) {
 			cout << "no\n";
 			continue;
 		}
 		sort(a, a + n, cabs);//精髓的操作，秀
 		n = min(n, 9);
 		sort(a, a + n);
		bool tag = true;
		for (int i = 0; i < n; i ++ ) {
			for (int j = i + 1; j < n; j ++ ) {
				for (int k = j + 1; k < n; k ++ ) {
					int w = a[i] + a[j] + a[k];//这个地方得想到用二分查找的方式，或者用map等方式减少查找复杂度
					int nx = lower_bound(a, a + n, w) - a;
					if(nx == n || a[nx] != w) {
						tag = false;
					}
				}
			}
 		}
 		if(tag)cout << "yes\n";
 		else cout << "no\n";
 	}
	return 0;
}

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;

int main(){
	std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
 	int t;
 	cin >> t;
 	while(t -- ) {
 		int n, sum = 0;
 		int cnt[2] = {0, 0};
 		cin >> n;
		std::vector<int> a(n);
		for (int i = 0; i < n; i ++ ) {
			cin >> a[i];
			cnt[0] += a[i] > 0;
			cnt[1] += a[i] < 0;
			sum += a[i];
		}
 		if(n <= 10) {
 			set<int> s;
			for (int i = 0; i < n; i ++ )s.insert(a[i]);
 			bool ok = true;
 			for (int i = 0; i < n; i ++ ) {
 				for (int j = i + 1; j < n; j ++) {
 					for (int k = j + 1; k < n; k ++ ) {
 						if(!s.count(a[i] + a[j] + a[k])) {
 							ok = false;
 						}
 					}
 				}
 			}
 			if(ok) cout << "yes\n";
 			else cout << "no\n";
 		}
 		else {
 			if(cnt[0] + cnt[1] == 1) cout << "yes\n";
 			else if(cnt[0] > 1 || cnt[1] > 1 || sum) cout << "no\n";
 			else cout << "yes\n";
 		}
 	}   
	return 0;
}