Can you find it?(二分 二分+STL set map)

Can you find it?

Time Limit : 10000/3000ms (Java/Other)   Memory Limit : 32768/10000K (Java/Other)
Total Submission(s) : 25   Accepted Submission(s) : 7
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
题意：分别有a,b,c三个数组，给出一个数，看这个数能不能再a,b,c,里面分别找出一个数求和得到
题解：先把两个数组加起来，另外一个数组用二分；
代码：
 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<algorithm>
 4 using namespace std;
 5 __int64 D[1000010],A[510],B[510],C[510],L,N,M;//D数组要开大；；； 
 6 int erfen(__int64 *a,__int64 c,__int64 d){ 
 7     int l,r,mid;
 8     l=0;r=L*N-1;//////// 
 9     while(l<=r){
10         mid=(l+r)/2;
11         if(a[mid]+c<d)l=mid+1;
12         else r=mid-1;
13         if(a[mid]+c==d)return 1;//这点弄错了，交了几十遍。。。。。 
14     }
15     return 0;
16 }
17 int search(__int64 *a,__int64 *b,__int64 c){
18     for(int i=0;a[i];i++){
19         if(erfen(b,a[i],c))return 1;
20     }
21     return 0;
22 }
23 void merge(__int64 *a,__int64 *b,__int64 *c){
24     int t=0;
25     for(int i=0;a[i];i++){
26         for(int j=0;b[j];j++){
27             c[t++]=a[i]+b[j];
28         }
29     }
30 }
31 int main(){
32     __int64 S,flot=0,X;
33     while(~scanf("%I64d%I64d%I64d",&L,&N,&M)){flot++;
34         for(int i=0;i<L;++i)scanf("%I64d",&A[i]);
35         for(int i=0;i<N;++i)scanf("%I64d",&B[i]);
36         for(int i=0;i<M;++i)scanf("%I64d",&C[i]);
37         merge(A,B,D);
38         sort(D,D+L*N);//这里也错了好多次，是相乘 
39             //for(int i=0;i<L+N;i++)printf("%d ",D[i]);
40         scanf("%I64d",&S);
41         printf("Case %I64d:
",flot);
42         while(S--){
43             scanf("%I64d",&X);
44             if(search(C,D,X))puts("YES");
45             else puts("NO");
46         }
47     }
48     return 0;
49 }

 stl:

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<algorithm>
 4 using namespace std;
 5 __int64 D[1000010],A[510],B[510],C[510],L,N,M;//D数组要开大；；； 
 6 /*int erfen(__int64 *a,__int64 c,__int64 d){ 
 7     int l,r,mid;
 8     l=0;r=L*N-1;//////// 
 9     while(l<=r){
10         mid=(l+r)/2;
11         if(a[mid]+c<d)l=mid+1;
12         else r=mid-1;
13         if(a[mid]+c==d)return 1;//这点弄错了，交了几十遍。。。。。 
14     }
15     return 0;
16 }*/
17 int search(__int64 *a,__int64 *b,__int64 c){
18     for(int i=0;a[i];i++){
19         if(*lower_bound(b,b+L*N,c-a[i])==c-a[i])return 1;/*lower_bound返回的是b数组中第一个大于等于c-a[i]元素的的地址 
20         upper(begin,end,index)找到大于某值的第一次出现； 
21         */
22     }
23     return 0;
24 }
25 void merge(__int64 *a,__int64 *b,__int64 *c){
26     int t=0;
27     for(int i=0;a[i];i++){
28         for(int j=0;b[j];j++){
29             c[t++]=a[i]+b[j];
30         }
31     }
32 }
33 int main(){
34     __int64 S,flot=0,X;
35     while(~scanf("%I64d%I64d%I64d",&L,&N,&M)){flot++;
36         for(int i=0;i<L;++i)scanf("%I64d",&A[i]);
37         for(int i=0;i<N;++i)scanf("%I64d",&B[i]);
38         for(int i=0;i<M;++i)scanf("%I64d",&C[i]);
39         merge(A,B,D);
40         sort(D,D+L*N);//这里也错了好多次，是相乘 
41             //for(int i=0;i<L+N;i++)printf("%d ",D[i]);
42         scanf("%I64d",&S);
43         printf("Case %I64d:
",flot);
44         while(S--){
45             scanf("%I64d",&X);
46             if(search(C,D,X))puts("YES");
47             else puts("NO");
48         }
49     }
50     return 0;
51 }

 map和set做全都MLE了，无奈了，别人的都对的；

set代码:

 1 #include<stdio.h>
 2 #include<set>
 3 using namespace std;
 4 const int MAXN=505;
 5 int A[MAXN],B[MAXN],C[MAXN];
 6 int main(){
 7     int L,N,M,S,X,flot=0,ok;
 8     while(~scanf("%d%d%d",&L,&N,&M)){set<int>num;
 9         for(int i=0;i<L;++i)scanf("%d",&A[i]);
10         for(int i=0;i<N;++i)scanf("%d",&B[i]);
11         for(int i=0;i<M;++i)scanf("%d",&C[i]);
12         for(int i=0;i<L;i++)for(int j=0;j<N;j++)num.insert(A[i]+B[j]);
13         scanf("%d",&S);
14         printf("Case %d:
",flot++);
15         while(S--){ok=0;
16             scanf("%d",&X);for(int i=0;C[i];i++){
17         if(num.find(X-C[i])!=num.end()){ok=1;break;}
18         }
19             if(ok)puts("YES");
20             else puts("NO");
21         }
22     }
23     return 0;
24 }

map代码：

 1 #include<stdio.h>
 2 #include<map>
 3 using namespace std;
 4 const int MAXN=505;
 5 int A[MAXN],B[MAXN],C[MAXN];
 6 int main(){
 7     int L,N,M,S,X,flot=0,ok;
 8     while(~scanf("%d%d%d",&L,&N,&M)){map<int,bool>num;
 9         for(int i=0;i<L;++i)scanf("%d",&A[i]);
10         for(int i=0;i<N;++i)scanf("%d",&B[i]);
11         for(int i=0;i<M;++i)scanf("%d",&C[i]);
12         for(int i=0;i<L;i++)for(int j=0;j<N;j++)num[A[i]+B[j]]=1;
13         scanf("%d",&S);
14         printf("Case %d:
",flot++);
15         while(S--){ok=0;
16             scanf("%d",&X);for(int i=0;C[i];i++){
17         if(num.count(X-C[i])){ok=1;break;}
18         }
19             if(ok)puts("YES");
20             else puts("NO");
21         }
22     }
23     return 0;
24 }
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/handsomecui/p/4689111.html