首页 > 代码库 > poj 2785 4 Values whose Sum is 0 哈希
poj 2785 4 Values whose Sum is 0 哈希
题意:
给4个集合ABCD,问有多少种从中各取一个数和为0的方案。
分析:
枚举前两个数建哈希表,枚举后两个数查找即可。
代码:
//poj 2785 //sep9 #include <iostream> using namespace std; const int maxN=4012; const int maxM=3999972; int a[maxN],b[maxN],c[maxN],d[maxN]; int hash[maxM+10]; int e; struct Edge { int val,tot,next; }edge[maxM]; void lookup1(int v) { int x=(v+3899974)%3999971; for(int i=hash[x];i!=-1;i=edge[i].next) if(edge[i].val==v){ ++edge[i].tot; return ; } edge[e].val=v;edge[e].tot=1;edge[e].next=hash[x]; hash[x]=e++; } int lookup2(int v) { int x=(v+3899974)%3999971; for(int i=hash[x];i!=-1;i=edge[i].next) if(edge[i].val==v) return edge[i].tot; return 0; } int main() { int i,j,n,sum; scanf("%d",&n); for(i=1;i<=n;++i) scanf("%d%d%d%d",&a[i],&b[i],&c[i],&d[i]); e=0; memset(hash,-1,sizeof(hash)); for(i=1;i<=n;++i) for(j=1;j<=n;++j){ sum=a[i]+b[j]; lookup1(sum); } int ans=0; for(i=1;i<=n;++i) for(j=1;j<=n;++j){ sum=c[i]+d[j]; ans+=lookup2(-sum); } printf("%d",ans); return 0; }
poj 2785 4 Values whose Sum is 0 哈希
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。