Can you find it?(哈希)

2022-07-27 07:23:50

题目连接：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)的算法，所以考虑到用哈希的方法，最慢的哈希也要比二分快。

 #include<cstdio>

 #include<algorithm>

 using namespace std;

 #define ll long long

 ll a[],b[],c[],d[];

 const int Mod = ;

 int inf = ;

 ll mp[Mod];

 void insert(ll u)

 {

     ll v = u;

     if(v<) v*=-;

     int id = v%Mod;

     while(mp[id]!=inf) {id++;id%=Mod;}

     mp[id] = u;

 }

 bool find(ll u){

     ll v = u;

     if(v<) v*=-;

     int id = v%Mod;

     while(mp[id] != inf){

         if(mp[id]==u) return true;

         id++;

         id%=Mod;

     }

     return false;

 }

 int main()

 {

     inf = inf*inf;//这里超int也没有关系，因为开始定义的int不够大

     int n1 , n2 , n3 ,cas = ;

     while(~scanf("%d%d%d",&n1,&n2,&n3))

     {

         for(int i = ; i < n1; i++) scanf("%lld",&a[i]);

         for(int i = ;i < n2 ; i++) scanf("%lld",&b[i]);

         for(int i = ;i < n3; i++) scanf("%lld",&c[i]);

         int cc = ;

         for(int i = ;i < n1; i++)

             for(int j =  ; j < n2 ; j++)

                 d[cc++] = a[i]+b[j];

         sort(d,d+cc);

         int n = unique(d,d+cc)-d;

         for(int i =  ; i < Mod ;i++) mp[i] = inf;

         for(int i = ;i < n; i++) insert(d[i]);

         ll s;

         scanf("%lld",&s);

         printf("Case %d:\n",cas++);

         for(int i =  ;i < s ;i++){

             ll x;

             scanf("%lld",&x);

             bool flag = false;

             for(int j=  ; flag == false&&j<n3;j++)

                 if(find(x-c[j]))flag = true;

             if(flag) puts("YES");

             else puts("NO");

         }

     }

     return ;

 }

码农公寓

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

Can you find it?

相关文章