POJ 2549:Subsets(哈希表)

【题目链接】 http://poj.org/problem?id=2549

【题目大意】

  给出一个数集,从中选择四个元素,使得a+b+c=d,最小化d

【题解】

  我们对a+b建立Hash_table,之后枚举c和d,寻找c-d且不由c和d构成的hash值是否存在
  如果存在,那么d就可以用来更新答案

【代码】

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <climits>
using namespace std;
const int N=1024,mod=1<<18;
int n,x[N],head[mod],cnt;
struct data{int a,b,sum,nxt;}g[N*N];
inline int hash(int x){return abs(x)&(mod-1);}
void insert(int a,int b,int sum){
int key=hash(sum);
for(int i=head[key];i!=-1;i=g[i].nxt){
if(g[i].sum==sum&&g[i].a==a&&g[i].b==b)return;
}g[cnt].a=a;g[cnt].b=b;g[cnt].sum=sum;
g[cnt].nxt=head[key]; head[key]=cnt++;
}
bool search(int a,int b,int sum){
int key=hash(sum);
for(int i=head[key];i!=-1;i=g[i].nxt){
if(g[i].sum!=sum||g[i].a==a||g[i].a==b||g[i].b==a||g[i].b==b)continue;
return 1;
}return 0;
}
void init(){cnt=0;memset(head,-1,sizeof(head));}
int main(){
while(scanf("%d",&n)&&n){
init();
for(int i=0;i<n;i++)scanf("%d",&x[i]);
for(int i=0;i<n;i++)for(int j=i+1;j<n;j++)insert(i,j,x[i]+x[j]);
int flag=0,ans=INT_MIN;
for(int i=0;i<n;i++)for(int j=0;j<n;j++){
if(i==j)continue;
if(search(i,j,x[i]-x[j])){
flag=1;ans=max(ans,x[i]);break;
}
}if(flag)printf("%d\n",ans);
else puts("no solution");
}return 0;
}
上一篇:Chrome谷歌浏览器插件-小结


下一篇:JS笔记一:动态修改css样式