【HDU】2141 - Can you find it?（STL）

点击打开题目

Can you find it?

Time Limit: 10000/3000 MS (Java/Others) Memory Limit: 32768/10000 K (Java/Others) Total Submission(s): 23787 Accepted Submission(s): 6026

Problem Description

Give you three sequences of numbers A, B, C, then we give you a number X. Now you need to calculate if you can find the three numbers Ai, Bj, Ck, which satisfy the formula Ai+Bj+Ck = X.

Input

There are many cases. Every data case is described as followed: In the first line there are three integers L, N, M, in the second line there are L integers represent the sequence A, in the third line there are N integers represent the sequences B, in the forth line there are M integers represent the sequence C. In the fifth line there is an integer S represents there are S integers X to be calculated. 1<=L, N, M<=500, 1<=S<=1000. all the integers are 32-integers.

Output

For each case, firstly you have to print the case number as the form "Case d:", then for the S queries, you calculate if the formula can be satisfied or not. If satisfied, you print "YES", otherwise print "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

Author

wangye

Source

HDU 2007-11 Programming Contest

需要合并数组（昨天新数组少开100倍而无限 MLE 的事就不要再提了 = = ），然后从 c 中取数在新数组二分查找（lower_bound () ）查找就行。

代码如下：

#include <cstdio>
#include <map> 
#include <algorithm>
using namespace std;
int main()
{
	int la,lb,lc;
	int a[511],c[511];
	int num[250011];
	int ant;
	int Case = 1;
	while (~scanf ("%d %d %d",&la,&lb,&lc))
	{
		ant = 0;
		for (int i = 1 ; i <= la ; i++)
			scanf ("%d",&a[i]);
		for (int i = 1 ; i <= lb ; i++)
		{
			int t;
			scanf ("%d",&t);
			for (int j = 1 ; j <= la ; j++)
				num[ant++] = a[j] + t;
		}
		for (int i = 1 ; i <= lc ; i++)
			scanf ("%d",&c[i]);
		sort (num,num+ant);
		ant = unique(num,num+ant) - num;		//去重 
		printf ("Case %d:\n",Case++);
		int Q;
		int m;
		scanf ("%d",&m);
		while (m--)
		{
			scanf ("%d",&Q);
			bool ans = false;
			for (int i = 1 ; i <= lc ; i++)
			{
				int pos = lower_bound (num , num + ant , Q - c[i]) - num;
				if (num[pos] + c[i] == Q)
				{
					ans = true;
					break;
				}
			}
			if (ans)
				printf ("YES\n");
			else
				printf ("NO\n");
		}
	}
	return 0;
}