[哈希]Sumsets uva10125 - c++编程基础

Problem C - 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.

Input

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.

Output

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

Sample Input

Output for Sample Input

12
no solution

题意：在给出的一组数组里面找出最大的数d使得数组里面另外三个数a，b，c使得a+b+c=d。

解法：使用暴力的话，时间复杂度o(n4)，最后一个二分的话是o(n3lgn)，数量级非常大。但是据说直接使用暴力也能过。

可以把公式变为a+b=d-c，然后把a+b的结果存下来，然后验证是否存在d-c等于a+b，使用哈希来判断。话说哈希函数还是不太会选择，这个哈希函数都是参照别人的。

#include
  
   
#include
   
     using namespace std; const int maxsize=500510; int head[maxsize],next[maxsize],n; int arry[1010]; class SUM { public: int sum,x,y; }st[maxsize]; int hash(int num) { int seed = (num >> 1) + (num << 1); return (seed & 0x7FFFFFFF) % 500503; } int insert(int s) { int h=hash(st[s].sum); int u=head[h]; while(u) { if(st[u].sum==st[s].sum) return 0; u=next[u]; } next[s]=head[h]; head[h]=s; return 1; } int search(int x,int y) { int h=hash(arry[x]-arry[y]); int u=head[h]; while(u) { if(st[u].sum==(arry[x]-arry[y])&&x!=st[u].x&&y!=st[u].y&&x!=st[u].y&&y!=st[u].x) return 1; u=next[u]; } return 0; } int main() { while(cin>>n&&n) { memset(head,0,sizeof(head)); int i,j,k; int num=1,maxn=-0x7FFFFFFF; for(i=0;i
    
     >arry[i]; for(i=0;i