uva 1152 4 values whose sum is zero —

uva 1152 4 values whose sum is zero ——yhx

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) 2 AB C D are such that a+b+c+d = 0. In the following, we
assume that all lists have the same size n.
Input
The input begins with a single positive integer on a line by itself indicating the number of the cases
following, each of them as described below. This line is followed by a blank line, and there is also a
blank line between two consecutive inputs.
The rst line of the input le 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 test case, your program has to write the number quadruplets whose sum is zero.
The outputs of two consecutive cases will be separated by a blank line.

 1 #include<cstdio>
 2 #include<cstring>
 3 int abs(int x)
 4 {
 5     if (x>=0) return x;
 6     return -x;
 7 }
 8 const int m=1098469;
 9 int a[4010],b[4010],c[4010],d[4010],first[1100000],next[17000000],num[17000000];
10 int main()
11 {
12     int i,j,k,n,p,q,x,y,z,t,ans;
13     scanf("%d",&t);
14     while (t--)
15     {
16         memset(a,0,sizeof(a));
17         memset(b,0,sizeof(b));
18         memset(c,0,sizeof(c));
19         memset(d,0,sizeof(d));
20         memset(first,0,sizeof(first));
21         memset(next,0,sizeof(next));
22         memset(num,0,sizeof(num));
23         ans=0;
24         scanf("%d",&n);
25         for (i=1;i<=n;i++)
26           scanf("%d%d%d%d",&a[i],&b[i],&c[i],&d[i]);
27         for (i=1;i<=n;i++)
28           for (j=1;j<=n;j++)
29           {
30               x=a[i]+b[j];
31               p=abs(x%m);
32               next[(i-1)*n+j]=first[p];
33               first[p]=(i-1)*n+j;
34               num[(i-1)*n+j]=x;
35           }
36         for (i=1;i<=n;i++)
37           for (j=1;j<=n;j++)
38           {
39               x=-c[i]-d[j];
40               p=abs(x%m);
41               for (k=first[p];k;k=next[k])
42                 if (x==num[k]) ans++;
43           }
44         printf("%d
",ans);
45         if (t) printf("
");
46     }
47 }

枚举a+b，把所有值存起来，然后枚举-c-d，在a+b中查找。

具体查找方法是哈希，除k取余法即可。