poj2549 Sumsets

发表于   |  

描述

Given S, a set of integers, find the largest d such that a + b + c = d where a, b, c, and d are distinct elements of S.

输入

Several S, each consisting of a line containing an integer 1 <= n <= 1000 indicating the number of elements in S, followed by the elements of S, one per line. Each element of S is a distinct integer between -536870912 and +536870911 inclusive. The last line of input contains 0.

输出

For each S, a single line containing d, or a single line containing “”no solution””.

样例输入

5
2
3
5
7
12
5
2
16
64
256
1024
0

样例输出

12
no solution

来源

Waterloo local 2001.06.02

Solution

这题是枚举中的中途相遇法
a+b+c=d转化为a+b=d-c 然后对其一边哈希

看图。。。说多了都是泪。。

1.TLE 用了map
2.WA 改成hash没判重
3.WA 不知道哪里错 改成二分继续错
4.WA 知道了要判重 代码打错w和ww搞混
5.TLE 在insert的时候不必要的去重浪费时间

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#define MAXN 1000+10
#define MAXM 1000000+10
#define MOD 1000007
#define get(x) (x)
using namespace std;
int n,m,T,cnt,a[MAXN];
//这段原来不是这样写的，不过反正都一样
inline int gethash(int x)
{
	if(x<0) x=-x; 
	return (x) & (MOD-1);
}

struct Hash{
	int x,y,w;
} data[MAXM];
int fir[MOD+10],nex[MAXM];
void insert(int x,int y,int ww){
	int w=gethash(ww);

	cnt++;
	data[cnt].x=x;
	data[cnt].y=y;
	data[cnt].w=ww;
	nex[cnt]=fir[w];
	fir[w]=cnt;
	return;	
}
bool find(int x,int y,int ww){
	int	w=gethash(ww);
	if (!fir[w]) return false;
	for (int i=fir[w];i;i=nex[i]){
		if (data[i].w!=ww) continue;
		if (x==data[i].x || y==data[i].x || x==data[i].y || y==data[i].y) continue;
		return true;
	} 
	return false;
}
int main(){
	freopen(""1.in"",""r"",stdin);
	freopen(""1.out"",""w"",stdout);	
	while (scanf(""%d"",&n)!=EOF){
		memset(nex,0,sizeof nex);
		memset(data,0,sizeof data);
		memset(fir,0,sizeof fir);
		cnt=0;
		if (!n) break;
		for (int i=1;i<=n;i++){
			scanf(""%d"",&a[i]);
		}
		sort(1+a,1+n+a);
		for (int i=1;i<=n;i++)
			for (int j=i+1;j<=n;j++)
				insert(j,i,a[j]+a[i]);
	
		bool bo=false;
		for (int i=n;i>=1;i--){
			for (int j=1;j<=n;j++){ 
				if (j!=i) {
					if (find(i,j,a[i]-a[j])){
						printf(""%d\n"",a[i]);
						bo=true;
						break;	
					}
				}
			}
			if (bo) break;
		}
		if (!bo) printf(""no solution\n"");
	}
}