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,里面分别找出一个数求和得到
题解：先把两个数组加起来，另外一个数组用二分；
代码：
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
__int64 D[],A[],B[],C[],L,N,M;//D数组要开大；；；
int erfen(__int64 *a,__int64 c,__int64 d){
int l,r,mid;
l=;r=L*N-;////////
while(l<=r){
mid=(l+r)/;
if(a[mid]+c<d)l=mid+;
else r=mid-;
if(a[mid]+c==d)return ;//这点弄错了，交了几十遍。。。。。
}
return ;
}
int search(__int64 *a,__int64 *b,__int64 c){
for(int i=;a[i];i++){
if(erfen(b,a[i],c))return ;
}
return ;
}
void merge(__int64 *a,__int64 *b,__int64 *c){
int t=;
for(int i=;a[i];i++){
for(int j=;b[j];j++){
c[t++]=a[i]+b[j];
}
}
}
int main(){
__int64 S,flot=,X;
while(~scanf("%I64d%I64d%I64d",&L,&N,&M)){flot++;
for(int i=;i<L;++i)scanf("%I64d",&A[i]);
for(int i=;i<N;++i)scanf("%I64d",&B[i]);
for(int i=;i<M;++i)scanf("%I64d",&C[i]);
merge(A,B,D);
sort(D,D+L*N);//这里也错了好多次，是相乘
//for(int i=0;i<L+N;i++)printf("%d ",D[i]);
scanf("%I64d",&S);
printf("Case %I64d:\n",flot);
while(S--){
scanf("%I64d",&X);
if(search(C,D,X))puts("YES");
else puts("NO");
}
}
return ;
}
stl:
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
__int64 D[],A[],B[],C[],L,N,M;//D数组要开大；；；
/*int erfen(__int64 *a,__int64 c,__int64 d){
int l,r,mid;
l=0;r=L*N-1;////////
while(l<=r){
mid=(l+r)/2;
if(a[mid]+c<d)l=mid+1;
else r=mid-1;
if(a[mid]+c==d)return 1;//这点弄错了，交了几十遍。。。。。
}
return 0;
}*/
int search(__int64 *a,__int64 *b,__int64 c){
for(int i=;a[i];i++){
if(*lower_bound(b,b+L*N,c-a[i])==c-a[i])return ;/*lower_bound返回的是b数组中第一个大于等于c-a[i]元素的的地址
upper(begin,end,index)找到大于某值的第一次出现；
*/
}
return ;
}
void merge(__int64 *a,__int64 *b,__int64 *c){
int t=;
for(int i=;a[i];i++){
for(int j=;b[j];j++){
c[t++]=a[i]+b[j];
}
}
}
int main(){
__int64 S,flot=,X;
while(~scanf("%I64d%I64d%I64d",&L,&N,&M)){flot++;
for(int i=;i<L;++i)scanf("%I64d",&A[i]);
for(int i=;i<N;++i)scanf("%I64d",&B[i]);
for(int i=;i<M;++i)scanf("%I64d",&C[i]);
merge(A,B,D);
sort(D,D+L*N);//这里也错了好多次，是相乘
//for(int i=0;i<L+N;i++)printf("%d ",D[i]);
scanf("%I64d",&S);
printf("Case %I64d:\n",flot);
while(S--){
scanf("%I64d",&X);
if(search(C,D,X))puts("YES");
else puts("NO");
}
}
return ;
}
map和set做全都MLE了，无奈了，别人的都对的；
set代码:
#include<stdio.h>
#include<set>
using namespace std;
const int MAXN=;
int A[MAXN],B[MAXN],C[MAXN];
int main(){
int L,N,M,S,X,flot=,ok;
while(~scanf("%d%d%d",&L,&N,&M)){set<int>num;
for(int i=;i<L;++i)scanf("%d",&A[i]);
for(int i=;i<N;++i)scanf("%d",&B[i]);
for(int i=;i<M;++i)scanf("%d",&C[i]);
for(int i=;i<L;i++)for(int j=;j<N;j++)num.insert(A[i]+B[j]);
scanf("%d",&S);
printf("Case %d:\n",flot++);
while(S--){ok=;
scanf("%d",&X);for(int i=;C[i];i++){
if(num.find(X-C[i])!=num.end()){ok=;break;}
}
if(ok)puts("YES");
else puts("NO");
}
}
return ;
}
map代码：
#include<stdio.h>
#include<map>
using namespace std;
const int MAXN=;
int A[MAXN],B[MAXN],C[MAXN];
int main(){
int L,N,M,S,X,flot=,ok;
while(~scanf("%d%d%d",&L,&N,&M)){map<int,bool>num;
for(int i=;i<L;++i)scanf("%d",&A[i]);
for(int i=;i<N;++i)scanf("%d",&B[i]);
for(int i=;i<M;++i)scanf("%d",&C[i]);
for(int i=;i<L;i++)for(int j=;j<N;j++)num[A[i]+B[j]]=;
scanf("%d",&S);
printf("Case %d:\n",flot++);
while(S--){ok=;
scanf("%d",&X);for(int i=;C[i];i++){
if(num.count(X-C[i])){ok=;break;}
}
if(ok)puts("YES");
else puts("NO");
}
}
return ;
}