t1794:集合加法

• 查看
• 提交
• 统计
• 提问

总时间限制: 

3000ms

内存限制: 

65536kB

描述

给出2个正整数集合A = {p_i | 1 <= i <= a}，B = {q_j | 1 <= j <= b}和一个正整数s。问题是：使得p_i+ q_j = s的不同的(i, j)对有多少个。

输入

第1行是测试数据的组数n，后面跟着n组测试数据。

每组测试数据占5行，第1行是和s (1 <= s <= 10000)，第2行是一个正整数a (1 <= a <= 10000)，表示A中元素的数目。第3行是a个正整数，每个正整数不超过10000，表示A中的元素。第4行是一个正整数b (1 <= b <= 10000)，表示B中元素的数目。第5行是b个正整数，每个正整数不超过10000，表示B中的元素。

注意：这里的集合和数学书上定义的集合有一点点区别——集合内可能包含相等的正整数。

输出

n行，每行输出对应一个输入。输出应是一个非负整数。

样例输入

2

99

2

49 49

2

50 50

11

9

1 2 3 4 5 6 7 8 9

10

10 9 8 7 6 5 4 3 2 1

样例输出

4

9

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 using namespace std;

 int n1,n,m;

 int i,j,t;

 int nowx,ans,x;

 int a[+],b[+],ha[+];

 int main()

 {

     int left,right,mid;

     scanf("%d",&n1);

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

     {

         memset(a,,sizeof(a));

         memset(b,,sizeof(b));

         memset(ha,,sizeof(ha));

         ans=; t=;

         scanf("%d",&x);

         scanf("%d",&n);

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

             scanf("%d",&a[j]);

         scanf("%d",&m);

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

             scanf("%d",&b[j]);

         sort(a+,a+n+);

         sort(b+,b+m+);

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

         if (b[j]!=b[j-])

         {

             ha[j-]=t;

             t=;

         }

         else

             t++;

         ha[m]=t;

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

         {

             nowx=x-a[j];

             left=; right=m;

             while (right-left>)

             {

                 mid=(left+right)>>;

                 if (b[mid]<=nowx)

                     left=mid;

                 else

                     right=mid;

             }

             if (b[left]==nowx && ha[left]!=)

                 ans+=ha[left];

             if (b[right]==nowx)

                 ans+=ha[right];

         }

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

     }

 }