给出一个整数集合s，找到集合中最大的d，让等式a+b+c=d成立，
其中，a,b,c,d是集合S中不同的元素。
http://noi.openjudge.cn/ch0305/1551/
有多组数据，每组数据第一行为n(1<=n<=1000),表示S中有n个数据，接下来n行，每行一个整数（-536870912~+536870911），最后n=0时结束
每组数据输出一行，输出d
如果无解则输出 no solution。
枚举a+b，将结果用hash记录，再枚举d-c，用hash查找。 O(n2)
开始ans设为0,结果就WA了,调了一个小时都没调出来。
#include<bits/stdc++.h> #define ll long long using namespace std; const int mac=1025; const int inf=5e5+5; const ll MOD=1e5+3; int n; ll a[inf],ans; ll val[inf]; int first[inf],cnt,nex[inf],X[inf],Y[inf]; inline void init(){ // memset(HASH,0,sizeof(HASH)); memset(first,-1,sizeof(first)); memset(nex,0,sizeof(nex)); memset(val,0,sizeof(val)); memset(a,0,sizeof(a)); memset(X,0,sizeof(X)); memset(Y,0,sizeof(Y)); cnt=0; ans=-9876543219; } inline int calc(ll s){ int remp=((s<<1)+(s>>1))%MOD; return remp<0 ? -remp:remp; } inline void H(ll sum,int x,int y){ int temp=calc(sum); val[++cnt]=sum; X[cnt]=x, Y[cnt]=y; nex[cnt]=first[temp]; first[temp]=cnt; return; } bool query(ll x,int q,int r){ int temp=calc(x); for(int i=first[temp];i!=-1;i=nex[i]){ if(val[i]==x && X[i]!=q && X[i]!=r && Y[i]!=q && Y[i]!=r &&a[Y[i]]+a[X[i]]+a[r]==a[q] ){ return 1; } } return 0; } int main(){ // freopen("2373.in","r",stdin); while(~scanf("%d",&n) && n!=0){ init(); for(int i=1;i<=n;i++){ scanf("%lld",&a[i]); } sort(a+1,a+n+1); for(int i=1;i<n;i++){ for(int j=i+1;j<=n;j++){ H(a[i]+a[j],i,j); } } bool flag=0; for(int i=n;i>=1;i--){ for(int j=1;j<=n;j++){ if(i==j) continue; if(query(a[i]-a[j],i,j)){ ans=max(a[i],ans); flag=1; break; } } } if(flag) printf("%lld\n",ans); else printf("no solution\n"); } return 0; }