Sumsets

给定数集 \(S\)，求互不相等的四个数满足 \(a+b+c=d(a,b,c,d\in S)\) 中 \(d\) 的最大值。

转化为 \(a+b=d-c\)，然后是套路的 meet in the middle。

使用手写 Hash_Table 可以少一个 log，但是常数略大。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;

const int N = 1010;
const int M = 1e6 + 10;
const int MOD = 999991;
const int INF = 1 << 30;
int n, s[N];

int read(){
	int x = 0, f = 1; char c = getchar();
	while(c < '0' || c > '9') f = (c == '-') ? -1 : 1, c = getchar();
	while(c >= '0' && c <= '9') x = x * 10 + c - 48, c = getchar();
	return x * f;
}

struct Hash_Table{
	int cnt, head[M];
	struct Table{int nxt, val, a, b;} ed[M];
	
	int Get(int x){return abs(x) % MOD + 1;}
	
	void clear(){
		cnt = 0;
		memset(head, 0, sizeof(head));
	}
	
	void insert(int v, int a, int b){
		int u = Get(v);
		ed[++ cnt] = (Table){head[u], v, a, b};
		head[u] = cnt;
	}
	
	bool query(int v, int c, int d){
		int u = Get(v);
		for(int i = head[u]; i; i = ed[i].nxt)
			if(ed[i].val == v){
				int a = ed[i].a, b = ed[i].b;
				if(a != c && a != d && b != c && b != d) return true;
			}
		return false;
	}
} Hash;

int main(){
	while(n = read()){
		for(int i = 1; i <= n; i ++) s[i] = read();
		Hash.clear();
		for(int a = 1; a < n; a ++)
			for(int b = a + 1; b <= n; b ++)
				Hash.insert(s[a] + s[b], a, b);
		int ans = - INF;
		for(int c = 1; c <= n; c ++)
			for(int d = 1; d <= n; d ++)
				if(c != d && Hash.query(s[d] - s[c], c, d))
					ans = max(ans, s[d]);
		if(ans == - INF) puts("no solution");
		else printf("%d\n", ans);
	}
	return 0;
}