首页 > 代码库 > poj 2549 --- 传说中的用“桶”防止HASH冲突
poj 2549 --- 传说中的用“桶”防止HASH冲突
http://poj.org/problem?id=2549
维基百科有3Sum算法:https://en.wikipedia.org/wiki/3SUM
sort(S); for i=0 to n-3 do a = S[i]; k = i+1; l = n-1; while (k<l) do b = S[k]; c = S[l]; if (a+b+c == 0) then output a, b, c; // Continue search for all triplet combinations summing to zero. k = k + 1 l = l - 1 else if (a+b+c > 0) then l = l - 1; else k = k + 1; end end end
这里用HASH 解:
1、排序,求任意两个数的和;将和与(i,j)通过Hash数组做映射,处理hash冲突用图论中的邻接表---学数据结构的时候老师讲过的桶式哈希
2、枚举两数(p,q)之差,通过HASH找到(i,j),保证p,q,i,j都不等即可
40多ms
#include <cstdio> #include <cstring> #include <algorithm> #include <string> #include <iostream> #include <cmath> #include <map> #include <set> #include <queue> using namespace std; #define ls(rt) rt*2 #define rs(rt) rt*2+1 #define ll long long #define ull unsigned long long #define rep(i,s,e) for(int i=s;i<e;i++) #define repe(i,s,e) for(int i=s;i<=e;i++) #define CL(a,b) memset(a,b,sizeof(a)) #define IN(s) freopen(s,"r",stdin) #define OUT(s) freopen(s,"w",stdin) const int SIZE = 536870911; const int MOD = 9973; const int MAXN = 1000 + 100; ll s[MAXN]; struct Node { int i; int j; int next; }rec[1100005]; int Hash[1100005];//头结点 inline ll Abs(ll x) { return x>0?x:(-x); } int main() { //IN("poj2549.txt"); int n,cnt; while(~scanf("%d",&n) && n) { CL(Hash,0xff); for(int i=0;i<n;i++) scanf("%lld",&s[i]); sort(s,s+n); cnt=0; for(int i=0;i<n-1;i++) for(int j=i+1;j<n;j++) { rec[cnt].i=i; rec[cnt].j=j; ll sum=Abs(s[i]+s[j])%MOD; rec[cnt].next=Hash[sum]; Hash[sum]=cnt; cnt++; } int ok=0; ll ans=0; for(int i=n-1;i>0;i--) { if(ok)break; for(int j=0;j<i;j++) { if(ok)break; ll sum=Abs(s[i]-s[j])%MOD; for(int v=Hash[sum];v!=-1;v=rec[v].next) { int h=rec[v].i; int k=rec[v].j; if(s[h]+s[k]==s[i]-s[j] && rec[v].i!=i && rec[v].i!=j && rec[v].j!=j && rec[v].j!=i) { ok=1; ans=s[i]; break; } } } } if(ok)printf("%lld\n",ans); else printf("no solution\n"); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。