本文主要是介绍uva10125 Sumsets，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
看似简单的题，其实要求考虑的非常严密
首先如果枚举a,b,c再判断d的话肯定超时，即使用hash存d也一样，解决办法是根据a+b=d-c先把所有d-c的值用hash存起来，再枚举所有a+b,这样枚举量就减小到1000*999了。
然后，每组a,b和每组c,d都必须考虑，不能先排序再枚举1000*999/2，因为d不一定是四个数字中最小的。
最后，当a+b==d-c时，还必须判断他们互不相等。
#include<cstdio>
#include<cstring>
#include<algorithm>
#define HASHSIZE 10000003
#define MAX 5000000
using namespace std;
int s[1000],head1[HASHSIZE],next1[MAX],s1[MAX][2];int hash(int value)
{if(value<0)value=-value;return (value)%HASHSIZE;
}void insert(int i,int j,int t)
{int sum=s[j]-s[i];int hashvalue=hash(sum);int u=head1[hashvalue];while(u!=-1){u=next1[u];}next1[t]=head1[hashvalue];head1[hashvalue]=t;
}
int find(int i,int j)
{int all=s[i]+s[j];int hashvalue=hash(all);int u=head1[hashvalue];while(u!=-1){if(s[s1[u][1]]-s[s1[u][0]]==all&&s[s1[u][1]]!=s[i]&&s[s1[u][1]]!=s[j]&&s[s1[u][0]]!=s[i]&&s[s1[u][0]]!=s[j])return s[s1[u][1]];u=next1[u];}return -1000000000;
}
int main()
{int n,i,j,t,flag,help,large;while(scanf("%d",&n)&&n){flag=0;large=-1000000000;memset(head1,-1,HASHSIZE*4);for(i=0;i<n;i++){scanf("%d",&s[i]);}//sort(s,s+n);t=0;for(i=0;i<n;i++){for(j=0;j<n;j++){if(i==j)continue;s1[t][0]=i;s1[t][1]=j;insert(i,j,t);t++;}}for(i=0;i<n;i++){for(j=0;j<n;j++){if(i==j)continue;if((help=find(i,j))!=-1000000000){flag=1;if(help>large)large=help;}}}if(flag==0)printf("no solution\n");elseprintf("%d\n",large);}return 0;
}
这篇关于uva10125 Sumsets的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
