首页 > 代码库 > HDU2141【hash】

HDU2141【hash】

2024-07-30 07:02:00   219人阅读

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 31 2 31 2 31 2 331410
 

 

Sample Output
Case 1:NOYESNO
 

 

Author
wangye
 

 

Source
HDU 2007-11 Programming Contest

 

分析：

用10^4打表  用10^2枚举

我的lower_bound一直挂  只能手写二分  不过还好

 

代码：

 1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 using namespace std; 6  7 const int maxn = 505; 8 int a[maxn], b[maxn], c[maxn], d[maxn * maxn]; 9 10 int cnt;11 bool check(int num) {12     int low = 0; int high = cnt - 1;13     while(low <= high) {14         int mid = ( low + high) >> 1;15         if(d[mid] >= num) {16             high = mid - 1;17         } else {18             low = mid + 1;19         }20     }21     if(d[high + 1] == num) return true;22     return false;23 }24 25 int main() {26     int l, n, m;27     int t = 1;28     while(EOF != scanf("%d %d %d",&l, &n, &m) ) {29         for(int i = 0; i < l; i++) scanf("%d",&a[i]);30         for(int i = 0; i < n; i++) scanf("%d",&b[i]);31         for(int i = 0; i < m; i++) scanf("%d",&c[i]);32         cnt = 0;33         for(int i = 0; i < l; i++) {34             for(int j = 0; j < n; j++) {35                 d[cnt++] = a[i] + b[j];36             }37         }38         sort(d, d + cnt);39         int s;40         int num;41         printf("Case %d:\n", t++);42         scanf("%d",&s);43         while(s--) {44             scanf("%d",&num);45             bool flag = false;46             for(int i = 0; i < m; i++) {47                 if(check(num - c[i]) ) {48                     flag = true;49                     break;50                 }51             }52             if(flag) puts("YES"); 53             else puts("NO");54         }55     }56 }
View Code

 

HDU2141【hash】


联系
我们