2792.md

集合固定元素和 2792: 集合加法

给定两个正整数可能有重复元素的集合，求分别取一元素和为定值的元素对数。

题目来源

2792: 集合加法

总时间限制: 3000ms 内存限制: 65536kB

描述

给出2个正整数集合A = {pi | 1 <= i <= a}，B = {qj | 1 <= j <= b}和一个正整数s。问题是：使得pi + qj = 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

可采用暴力遍历的算法，将集合A中的元素分别与B中的元素求和试探计数即可。

#include <iostream>
#include <vector>
using namespace std;
int main() {
	int n, i, j, k, a, b, s, num;
	cin >> n;
	for (i = 0; i < n; ++i) {
		cin >> s;
		cin >> a;
		vector<int> A, B;
		for (j = 0; j < a; ++j) {
			cin >> num;
			if (num < s) {
				A.push_back(num);
			}
		}
		cin >> b;
		for (j = 0; j < b; ++j) {
			cin >> num;
			if (num < s) {
				B.push_back(num);
			}
		}
		int sum = 0;
		for (j = 0; j < A.size(); ++j) {
			for (k = 0; k < B.size(); ++k) {
				if (A[j] + B[k] == s) {
					sum++;
				}
			}
		}
		cout << sum << endl;
	}
	return 0;
}

2792.cpp 代码长度：561B 内存：1152kB 时间：352ms 通过率：95% 最小内存：1024kB 最短时间：14ms

对于集合元素个数未知的情况，可以采用动态内存分配的方式或者使用vector，最后二重循环比较遍历即可。

有任何的改进意见欢迎大家在微信平台公众号主页面留言或者发表issue。