当前位置: 代码迷 >> 综合 >> poj 2785 4 Values whose Sum is 0 哈希
  详细解决方案

poj 2785 4 Values whose Sum is 0 哈希

热度:75   发布时间:2024-01-19 06:09:15.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;
} 


  相关解决方案