POJ2549【hash分离链接法】

复杂度n^2*HASH;

#include<cstdio>#include<string.h>#include<algorithm>using namespace std;const int mod=5e5+10;const int N=5e5+10;struct Node{    int x,y;};Node q[N];int Ha[mod],nex[mod],s[1010],res,n;bool flag;void solve(int x,int y){    int key=(x-y+mod)%mod;    int i=Ha[key];    while(i!=-1)    {        while((q[i].x+q[i].y)==(x-y)&&q[i].x!=x&&q[i].x!=y&&q[i].y!=y&&q[i].y!=x)        {            res=x;            flag=true;            return;        }        i=nex[i];    }}int main(){    while(scanf("%d",&n)&&n)    {        for(int i=0;i<n;i++) scanf("%d",&s[i]);        int tot=0;        sort(s,s+n);        memset(Ha,-1,sizeof(Ha));        for(int i=0;i<n-1;i++)            for(int j=i+1;j<n;j++)            {                q[tot].x=s[j];q[tot].y=s[i];                int key=(s[i]+s[j]+mod)%mod;                nex[tot]=Ha[key];                Ha[key]=tot;                tot++;            }        res=-1000000000;        flag=false;        for(int i=n-1;i>=1;i--)            for(int j=i-1;j>=0;j--)            {                if(flag) break;                solve(s[i],s[j]);            }        if(res!=-1000000000)            PRintf("%d/n",res);        else            puts("no solution");    }    return 0;}