|
4 Values whose Sum is 0
Description
The SUM problem can be formulated as follows: given four lists A, B, C, D of integer values, compute how many quadruplet (a, b, c, d ) ∈ A x B x C x D are such that a + b + c + d = 0 . In the following, we assume that all lists have the same size n .
Input
The first line of the input file contains the size of the lists n (this value can be as large as 4000). We then have n lines containing four integer values (with absolute value as large as 228 ) that belong respectively to A, B, C and D .
Output
For each input file, your program has to write the number quadruplets whose sum is zero.
Sample Input 6 -45 22 42 -16 -41 -27 56 30 -36 53 -37 77 -36 30 -75 -46 26 -38 -10 62 -32 -54 -6 45 Sample Output 5 Hint
Sample Explanation: Indeed, the sum of the five following quadruplets is zero: (-45, -27, 42, 30), (26, 30, -10, -46), (-32, 22, 56, -46),(-32, 30, -75, 77), (-32, -54, 56, 30).
Source |
|||||||||
题意：
给你四列数。每列里找一个数使得他们的和为0.问一共有多少这样的数。
思路：
把前两列的数任意组合的和hash。在任意组合后两列。然后去查hash表看能否使值为0.
详细见代码：
#include<algorithm>
#include<iostream>
#include<string.h>
#include<sstream>
#include<stdio.h>
#include<math.h>
#include<vector>
#include<string>
#include<queue>
#include<set>
#include<map>
//#pragma comment(linker,"/STACK:1024000000,1024000000")
using namespace std;
const int INF=0x3f3f3f3f;
const double eps=1e-8;
const double PI=acos(-1.0);
const int maxn=4010;
const int up=536870912;
const int mod=13000007;
const int sz=maxn*maxn;
typedef __int64 ll;
int maze[5][maxn];
int h[sz],f[sz];
void Insert(int x)
{
int key=(x+up)%mod;
while(f[key]&&h[key]!=x)
key=(key+1)%sz;
if(!f[key])
h[key]=x;
f[key]++;
}
int getf(int x)
{
int key=(x+up)%mod;
while(f[key]&&h[key]!=x)
key=(key+1)%sz;
return f[key];
}
int main()
{
int n,i,j;
ll ans;
while(~scanf("%d",&n))
{
memset(f,0,sizeof f);
for(j=0;j<n;j++)
for(i=0;i<4;i++)
scanf("%d",&maze[i][j]);
for(i=0;i<n;i++)
for(j=0;j<n;j++)
Insert(maze[0][i]+maze[1][j]);
ans=0;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
ans+=getf(-maze[2][i]-maze[3][j]);
printf("%I64d\n",ans);
}
return 0;
}