【HRBUST - 1996】数学等式 （HASH 或 二分）

题干：

又到了数学题的时刻了，给出三个数组A,B,C,然后再给出一个数X，现在我想知道是否能找到三个数满足等式A[i]+B[j]+C[k]=X，你能帮助我么？？

Input

本题有多组数据，每组数据第一行输入三个数n, m, h,分别表示数组A，B，C内的的元素个数（0<n,m,h<=500）

接下来三行分别输入数组A,B,C的元素

接下来输入一个数Q,表示Q次询问 (1<=Q<=1000)

接下来Q行每行一个数字Xi(Xi在32位整型范围内)

Output

对于每组数据，首先输出“Case d:”,d表示第d组数据，接下输出Q行，表示每次查询结果，如果能够找到满足等式的三个数则输出YES，反之输出NO

Sample Input

3 3 3
1 2 3
1 2 3
1 2 3
3
1
4
10

Sample Output

Case 1:
NO
YES
NO

解题报告：

    这里说一下，，用STL的二分会TLE，手写binarysearch就可以AC。

AC代码：（700多ms貌似）

#include<bits/stdc++.h>
#define ll long long 
using namespace std;
int n,m,h,q;
ll a[505],b[505],c[505];
ll bb[250005];

bool bs(int R,ll ans)
{
	int l,r,mid;
	l=1,r=R;mid=(l+r)>>1;
	while(l<=r)
	{
		mid=(l+r)>>1;
		if(bb[mid]==ans)
			return true;
		else if(bb[mid]>ans)
			r=mid-1;
		else if(bb[mid]<ans)
			l=mid+1;
	}
	return false;
}

int main()
{
	int iCase = 0;
	ll x;
	while(~scanf("%d%d%d",&n,&m,&h)) {
		int top = 0,flag;
		for(int i = 1; i<=n; i++) scanf("%lld",&a[i]);
		for(int i = 1; i<=m; i++) scanf("%lld",&b[i]);
		for(int i = 1; i<=h; i++) scanf("%lld",&c[i]);
		//打表 
		for(int i = 1; i<=n; i++) {
			for(int j = 1; j<=m; j++) {
				bb[++top] = a[i] + b[j];
			}
		}
		sort(bb+1,bb+top+1);
		int tot = unique(bb+1,bb+top+1) - bb-1;
		scanf("%d",&q);
		printf("Case %d:\n",++iCase);
		while(q--) {
			scanf("%lld",&x);
			flag = 0;
			for(int i = 1; i<=h; i++) {
				if(bs(tot,x-c[i]) == 1) {
					printf("YES\n");flag = 1;break;
				}
			}
			if(!flag) printf("NO\n"); 
		}
	}
	return 0 ;
 } 

开O2优化了以后520ms飘过：

#pragma GCC optimize(2) 
#include<bits/stdc++.h>
#define ll long long 
#pragma GCC optimize(1)
using namespace std;
int n,m,h,q;
ll a[505],b[505],c[505];
ll bb[250005];

//bool bs(int R,ll ans)
//{
//	int l,r,mid;
//	l=1,r=R;mid=(l+r)>>1;
//	while(l<=r)
//	{
//		mid=(l+r)>>1;
//		if(bb[mid]==ans)
//			return true;
//		else if(bb[mid]>ans)
//			r=mid-1;
//		else if(bb[mid]<ans)
//			l=mid+1;
//	}
//	return false;
//}

int main()
{
	int iCase = 0;
	ll x;
	while(~scanf("%d%d%d",&n,&m,&h)) {
		int top = 0,flag;
		for(int i = 1; i<=n; i++) scanf("%lld",&a[i]);
		for(int i = 1; i<=m; i++) scanf("%lld",&b[i]);
		for(int i = 1; i<=h; i++) scanf("%lld",&c[i]);
		//打表 
		for(int i = 1; i<=n; i++) {
			for(int j = 1; j<=m; j++) {
				bb[++top] = a[i] + b[j];
			}
		}
		sort(bb+1,bb+top+1);
		int tot = unique(bb+1,bb+top+1) - bb-1;
		scanf("%d",&q);
		printf("Case %d:\n",++iCase);
		while(q--) {
			scanf("%lld",&x);
			flag = 0;
			for(int i = 1; i<=h; i++) {
				if(binary_search(bb+1,bb+tot+1,x-c[i]) == 1) {
					printf("YES\n");flag = 1;break;
				}
			}
			if(!flag) printf("NO\n"); 
		}
	}
	return 0 ;
 } 

这题也可以Hash

半年前的博客？？忽然找到了，赶紧发一下。