POJ 2549：Subsets（哈希表）

【题目链接】 http://poj.org/problem?id=2549

【题目大意】

　　给出一个数集，从中选择四个元素，使得a+b+c=d，最小化d

【题解】

　　我们对a+b建立Hash_table,之后枚举c和d，寻找c-d且不由c和d构成的hash值是否存在
　　如果存在，那么d就可以用来更新答案

【代码】

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <climits>

using namespace std;

const int N=1024,mod=1<<18;

int n,x[N],head[mod],cnt;

struct data{int a,b,sum,nxt;}g[N*N];

inline int hash(int x){return abs(x)&(mod-1);}

void insert(int a,int b,int sum){

    int key=hash(sum);

    for(int i=head[key];i!=-1;i=g[i].nxt){

        if(g[i].sum==sum&&g[i].a==a&&g[i].b==b)return;

    }g[cnt].a=a;g[cnt].b=b;g[cnt].sum=sum;

    g[cnt].nxt=head[key]; head[key]=cnt++;

}

bool search(int a,int b,int sum){

    int key=hash(sum);

    for(int i=head[key];i!=-1;i=g[i].nxt){

        if(g[i].sum!=sum||g[i].a==a||g[i].a==b||g[i].b==a||g[i].b==b)continue;

        return 1;

    }return 0;

}

void init(){cnt=0;memset(head,-1,sizeof(head));}

int main(){

    while(scanf("%d",&n)&&n){

    	init();

        for(int i=0;i<n;i++)scanf("%d",&x[i]);

        for(int i=0;i<n;i++)for(int j=i+1;j<n;j++)insert(i,j,x[i]+x[j]);

        int flag=0,ans=INT_MIN;

        for(int i=0;i<n;i++)for(int j=0;j<n;j++){

            if(i==j)continue;

            if(search(i,j,x[i]-x[j])){

                flag=1;ans=max(ans,x[i]);break;

            }

        }if(flag)printf("%d\n",ans);

        else puts("no solution");

    }return 0;

}