Can you find it?(哈希)

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:
",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 }