uva 10125 - Sumsets好题

#include<cstdlib>#include<iostream>#include<cstdio>#include<cmath>#include<set>#include<cstring>#include <algorithm>#define M 5368#define N 1000010#define inf 0x7f7f7f7fusing namespace std;int head[N],next[N];int a[1000],sum[N],st[N][2];int hash(int u){//    u=((u<<1)+(u>>1))/2;//    return (u & 0x7fffffff)%N;    if(a<0)        a=-a;    return a%N;}void insert(int k){    int h=hash(sum[k]);    next[k]=head[h];    head[h]=k;}int find(int x,int y,int s){    int h=hash(s);    h=head[h];//容易忘掉！！wa    while(h!=-1)    {        if(s==sum[h]&&st[h][0]!=x&&st[h][0]!=y&&st[h][1]!=x&&st[h][1]!=y)            return 1;        h=next[h];    }    return 0;}int main(){#ifndef ONLINE_JUDGE    freopen("ex.in","r",stdin);#endif    int n;    while(scanf("%d",&n))    {        memset(head,-1,sizeof(head));        if(!n)            break;        for(int i=0; i<n; i++)            scanf("%d",&a[i]);        sort(a,a+n);        int k=0;        for(int i=0; i<n; i++)            for(int j=i+1; j<n; j++)//降为o(n^2)            {                sum[k]=a[i]+a[j];                insert(k);                st[k][0]=i;                st[k++][1]=j;            }        int flag=1;        for(int i=n-1; i>=0; i--)        {            for(int j=0; j<n; j++)                if(i==j)                    continue;                else if(find(i,j,a[i]-a[j]))                {                    flag=0;                    printf("%d\n",a[i]);                    break;                }            if(!flag)                break;        }        if(flag)            printf("no solution\n");    }    return 0;}