uva 1152 4 values whose sum is zero —

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.

 #include<cstdio>

 #include<cstring>

 int abs(int x)

 {

     if (x>=) return x;

     return -x;

 }

 const int m=;

 int a[],b[],c[],d[],first[],next[],num[];

 int main()

 {

     int i,j,k,n,p,q,x,y,z,t,ans;

     scanf("%d",&t);

     while (t--)

     {

         memset(a,,sizeof(a));

         memset(b,,sizeof(b));

         memset(c,,sizeof(c));

         memset(d,,sizeof(d));

         memset(first,,sizeof(first));

         memset(next,,sizeof(next));

         memset(num,,sizeof(num));

         ans=;

         scanf("%d",&n);

         for (i=;i<=n;i++)

           scanf("%d%d%d%d",&a[i],&b[i],&c[i],&d[i]);

         for (i=;i<=n;i++)

           for (j=;j<=n;j++)

           {

               x=a[i]+b[j];

               p=abs(x%m);

               next[(i-)*n+j]=first[p];

               first[p]=(i-)*n+j;

               num[(i-)*n+j]=x;

           }

         for (i=;i<=n;i++)

           for (j=;j<=n;j++)

           {

               x=-c[i]-d[j];

               p=abs(x%m);

               for (k=first[p];k;k=next[k])

                 if (x==num[k]) ans++;

           }

         printf("%d\n",ans);

         if (t) printf("\n");

     }

 }

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

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

巴特西

uva 1152 4 values whose sum is zero ——yhx

最新文章

热门文章