原题传送门: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): 10636 Accepted Submission(s): 2786
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
Recommend
分析:这道题目一共有三个序列集L N M 很显然直接暴力三个for肯定超时,就算两个for for 然后第三个用二分,这也是超时的。那么能用一个for和一个二分解决吗,显然是可以的。首先我们班L,N两个序列集合并为一个。定义一个新的 数组用来存储所有L,N集中和的情况,就是for for(A[n++] = L[i]+N[i]),然后再用遍历A集合,每一步在M集合中二分搜索是否有符合x-A[i]的值(利用这个公式就可以转换下了C = X-(A+B)),如果有就YES 木有就NO;
如果你这么天真地想,恭喜你你又得超时了。既然二分可以提高搜索速度,我们为什么不把A拿来二分搜索呢?A中的元素最多会有25W个啊!!如果二分就是10^3级别的。。搜索次数,大大减小时间。如果拿M来二分,你只能从500到20左右。
OJ也证明了这一点,代码如下:
//搜索 HDU2141 #include<cstdio> #include<algorithm> using namespace std; #define MAXN 510 int AL[MAXN]; int AN[MAXN]; int A[MAXN*MAXN]; int AM[MAXN]; int L,M,N,x,s,k,temp,n; bool res; bool binSearch(int target,int len){ int low = 0; int high = len - 1; int mid; while(low<high) { mid = (low+high)/2; if(A[mid] == target)return true; else if(target>A[mid]) low = mid+1; else high = mid; } return false; } int main() { k = 1; while(scanf("%d%d%d",&L,&N,&M)==3) { n = 0; res = false; for(int i=0;i<L;i++) scanf("%d",AL+i); for(int i=0;i<N;i++) scanf("%d",AN+i); for(int i=0;i<M;i++) scanf("%d",AM+i); for(int i=0;i<L;i++){ for(int j=0;j<N;j++){ A[n++]= AL[i]+AN[j]; } } sort(A,A+n); sort(AM,AM+M); scanf("%d",&s); printf("Case %d:\n",k++); while(s--){ scanf("%d",&x); for(int i=0;i<M;i++){ res = binSearch(x-AM[i],n); if(res){ printf("YES\n"); break; } } if(!res){ printf("NO\n"); } } } return 0; }
相关推荐
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
杭电ACMhdu1163
HDU1059的代码
hdu1001解题报告
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
hdu2101AC代码
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
搜索 dfs 解题代码 hdu1241
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
自己做的HDU ACM已经AC的题目
hdu 1166线段树代码
HDU最全ac代码
hdu动态规划算法集锦
ACM HDU题目分类,我自己总结的大概只有十来个吧
HDU ACM 2005第几天 C++ http://acm.hdu.edu.cn/listproblem.php?vol=11 2005题 第几天?
hdu题目分类
HDU图论题目分类