【noiOJ】p1794

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

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 using namespace std;
 6 int n1,n,m;
 7 int i,j,t;
 8 int nowx,ans,x;
 9 int a[10000+10],b[10000+10],ha[10000+10];
10 int main()
11 {
12     int left,right,mid;
13     scanf("%d",&n1);
14     for (i=1;i<=n1;i++)
15     {
16         memset(a,0,sizeof(a));
17         memset(b,0,sizeof(b));
18         memset(ha,0,sizeof(ha));
19         ans=0; t=1;
20         scanf("%d",&x);
21         scanf("%d",&n);
22         for (j=1;j<=n;j++)
23             scanf("%d",&a[j]);
24         scanf("%d",&m);
25         for (j=1;j<=m;j++)
26             scanf("%d",&b[j]);
27         sort(a+1,a+n+1);
28         sort(b+1,b+m+1);
29         for (j=2;j<=m;j++)
30         if (b[j]!=b[j-1])
31         {
32             ha[j-1]=t;
33             t=1;
34         }
35         else
36             t++;
37         ha[m]=t;
38         for (j=1;j<=n;j++)
39         {
40             nowx=x-a[j];
41             left=0; right=m;
42             while (right-left>1)
43             {
44                 mid=(left+right)>>1;
45                 if (b[mid]<=nowx)
46                     left=mid;
47                 else
48                     right=mid;                    
49             }
50             if (b[left]==nowx && ha[left]!=0)
51                 ans+=ha[left];
52             if (b[right]==nowx)
53                 ans+=ha[right];
54         }
55         printf("%d
",ans);
56     }
57 }

—Anime Otaku Save The World.