UVA 1152 和为 0 的 4 个值 4 Values whose Sum is 0

和为 0 的 4 个值 4 Values whose Sum is 0

题面翻译

题目描述

给出四个数组 $A,B,C,D$ ，每个数组中有 $n$ 个整数。求有多少组 $i,j,k,l$ 满足 $A_i+B_j+C_k+D_l=0$ 。

输入格式

本题有多组测试数据。

第一行一个正整数 $T$ ，表示数据组数。

对于每组数据:

第一行一个整数 $n$ 。

接下来 $n$ 行，一行四个整数，分别表示 $A_i,B_i,C_i,D_i$ 。

输出格式

共 $2\times T$ 行。

对于每组数据：

第一行一个整数，表示该组测试数据的答案。

接下来输出一个空行。

数据范围

$1\le n\le 4000$ 。数组中所有数的绝对值不大于 $2^{28}$ 。

题目描述

PDF

输入输出样例

输入

1
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

1
2
3
4
5
6
7
8
9
10

输出

5
1

分析

题目让我们求 $A+B+C+D=0$，我们可以把将$C+D$移到右边，变成$A+B=-C-D$，这样我们就可以枚举所有的$A+B$，把它放入一个映射数组中，再枚举所有的$-C-D$，看该映射中有过多少次该值。

代码

#include

using namespace std;

#include//麻烦的头文件，为什么万能头里没有？
#include

using namespace __gnu_pbds;

gp_hash_table <int,int> g;//mapTLE了

int a[10000],b[10000],c[10000],d[10000];

int T;

int n;

int ans;

int main()
{
	cin>>T;
    
	while(T--)
	{
		ans=0;
		
		g.clear();
		
		cin>>n;
		
		for(int i=1;i<=n;i++)
		{
			cin>>a[i]>>b[i]>>c[i]>>d[i];
		}
		
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=n;j++)
			{
				int k=a[i]+b[j];
				
				g[k]++;
			}
		}
		
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=n;j++)
			{
				int k=c[i]+d[j];
				
				ans+=g[-k];
			}
		}
		
		cout<<ans<<endl;
		
		if(T>0)
		{
			cout<<endl;
		}
	}
    
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66