A5558.子问题 题解

前言

这个题的数据还没改，原题是求有多少对数满足加起来等于 $k$。

思路

方法 1

暴力枚举不重复的每一对数，然后判断每一对数加起来是否等于 $k$。时间复杂度 $O(n^{2})$，期望得分 $100 pts$。

方法 2

第二组数不变，排序第一组数，然后枚举第二组数，在第一组数中二分查找，找能与枚举到的那个数的数量。时间复杂度 $O(n \log n)$，期望得分 $100pts$。

方法 3

用一个桶，记录第一组数的每一个数与哪个数加起来等于 $k$，然后在输入第二组数的时候判断桶的这个地方被标记多少次。时间复杂度 $O(n)$，期望得分 $100pts$。

代码

需要注意：

古之有数，其名为 $k$。$k$ 之大，一个 int （可能）装不下。

方法 1 代码

无任何优化和改变：

#include <iostream>
#include <vector>
using namespace std;
int main(){
	long long n,k;
	cin >> n >> k;
	vector<long long> a;
	for (int i=0;i<n;++i){
		long long t;
		cin >> t;
		a.emplace_back(t);
	}
	int ans=0;
	for (int i=0;i<n;++i){
		long long t;
		cin >> t;
		for (const auto &item : a){
			if (t+item==k){
				++ans;
			}
		}
	}
	cout<<ans<<endl;
	return 0;
}

方法 2 代码

使用了 STL 函数：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
	long long n,k;
	cin >> n >> k;
	vector<long long> a;
	for (int i=0;i<n;++i){
		long long t;
		cin >> t;
		a.emplace_back(t);
	}
	sort(a.begin(),a.end());
	int ans=0;
	for (int i=0;i<n;++i){
		long long t;
		cin >> t;
		auto it1=lower_bound(a.begin(),a.end(),k-t),
			 it2=upper_bound(a.begin(),a.end(),k-t);
		ans+=distance(it1,it2);
	}
	cout<<ans<<endl;
	return 0;
}

方法 3 代码

使用了 unordered_map 当作桶：

#include <iostream>
#include <unordered_map>
using namespace std;
int main(){
	long long n,k;
	cin >> n >> k;
	unordered_map<long long,int> m;
	for (int i=0;i<n;++i){
		long long t;
		cin >> t;
		++m[k-t];
	}
        int ans=0;
	for (int i=0;i<n;++i){
		long long t;
		cin >> t;
		ans+=m[t];
	}
	cout<<ans<<endl;
	return 0;
}