转载

Can you find it?(哈希)

题目连接：http://acm.hdu.edu.cn/showproblem.php?pid=2141

Can you find it?

Time Limit: 10000/3000 MS (Java/Others) Memory Limit: 32768/10000 K (Java/Others)

Total Submission(s): 18192 Accepted Submission(s): 4601

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

题意：从三个集合中分别各取一个数，然后相加等于X

注意数据范围很大所以不可能暴力，先算出前两个集合中任意两个值得和保存到数组d中，然后对d进行去重操作，注意：去重函数unique(d,d+cc)返回的是最后一个元素所在的地址，要获得新数组的总元素个数要减去首地址及 int n = unique(d,d+cc) - d ;

这里要注意，两个数相加可能会超int，所以要用long long，而且在每次输入x的时候在对应的d数组中找是否存在x-c的时候必须用O(n)的算法，所以考虑到用哈希的方法，最慢的哈希也要比二分快。

 1 #include<cstdio>  2 #include<algorithm>  3 using namespace std;  4 #define ll long long  5 ll a[505],b[505],c[505],d[250010];  6   7 const int Mod = 500007;  8 int inf = 100000000;  9 ll mp[Mod]; 10 void insert(ll u) 11 { 12     ll v = u; 13     if(v<0) v*=-1; 14     int id = v%Mod; 15     while(mp[id]!=inf) {id++;id%=Mod;} 16     mp[id] = u; 17 } 18 bool find(ll u){ 19     ll v = u; 20     if(v<0) v*=-1; 21     int id = v%Mod; 22     while(mp[id] != inf){ 23         if(mp[id]==u) return true; 24         id++; 25         id%=Mod; 26     } 27     return false; 28 } 29 int main() 30 { 31     inf = inf*inf;//这里超int也没有关系，因为开始定义的int不够大 32     int n1 , n2 , n3 ,cas = 1; 33     while(~scanf("%d%d%d",&n1,&n2,&n3)) 34     { 35         for(int i =0 ; i < n1; i++) scanf("%lld",&a[i]); 36         for(int i =0 ;i < n2 ; i++) scanf("%lld",&b[i]); 37         for(int i =0 ;i < n3; i++) scanf("%lld",&c[i]); 38         int cc = 0; 39         for(int i =0 ;i < n1; i++) 40             for(int j = 0 ; j < n2 ; j++) 41                 d[cc++] = a[i]+b[j]; 42         sort(d,d+cc); 43         int n = unique(d,d+cc)-d; 44         for(int i = 0 ; i < Mod ;i++) mp[i] = inf; 45         for(int i =0 ;i < n; i++) insert(d[i]); 46         ll s; 47         scanf("%lld",&s); 48         printf("Case %d:/n",cas++); 49         for(int i = 0 ;i < s ;i++){ 50             ll x; 51             scanf("%lld",&x); 52             bool flag = false; 53             for(int j= 0 ; flag == false&&j<n3;j++) 54                 if(find(x-c[j]))flag = true; 55             if(flag) puts("YES"); 56             else puts("NO"); 57         } 58     } 59     return 0; 60 }