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;}