題干：

又到了數學題的時刻了，給出三個數組A,B,C,然后再給出一個數X，現在我想知道是否能找到三個數滿足等式A[i]+B[j]+C[k]=X，你能幫助我么？？

Input

本題有多組數據，每組數據第一行輸入三個數n,?m,?h,分別表示數組A，B，C內的的元素個數（0<n,m,h<=500）

接下來三行分別輸入數組A,B,C的元素

接下來輸入一個數Q,表示Q次詢問?(1<=Q<=1000)

接下來Q行每行一個數字Xi(Xi在32位整型范圍內)

Output

對于每組數據，首先輸出“Case?d:”,d表示第d組數據，接下輸出Q行，表示每次查詢結果，如果能夠找到滿足等式的三個數則輸出YES，反之輸出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

解題報告：

? ? 這里說一下，，用STL的二分會TLE，手寫binarysearch就可以AC。

AC代碼：（700多ms貌似）

#include<bits/stdc++.h> #define ll long long using namespace std; int n,m,h,q; ll a[505],b[505],c[505]; ll bb[250005];bool bs(int R,ll ans) {int l,r,mid;l=1,r=R;mid=(l+r)>>1;while(l<=r){mid=(l+r)>>1;if(bb[mid]==ans)return true;else if(bb[mid]>ans)r=mid-1;else if(bb[mid]<ans)l=mid+1;}return false; }int main() {int iCase = 0;ll x;while(~scanf("%d%d%d",&n,&m,&h)) {int top = 0,flag;for(int i = 1; i<=n; i++) scanf("%lld",&a[i]);for(int i = 1; i<=m; i++) scanf("%lld",&b[i]);for(int i = 1; i<=h; i++) scanf("%lld",&c[i]);//打表 for(int i = 1; i<=n; i++) {for(int j = 1; j<=m; j++) {bb[++top] = a[i] + b[j];}}sort(bb+1,bb+top+1);int tot = unique(bb+1,bb+top+1) - bb-1;scanf("%d",&q);printf("Case %d:\n",++iCase);while(q--) {scanf("%lld",&x);flag = 0;for(int i = 1; i<=h; i++) {if(bs(tot,x-c[i]) == 1) {printf("YES\n");flag = 1;break;}}if(!flag) printf("NO\n"); }}return 0 ;}

開O2優化了以后520ms飄過：

#pragma GCC optimize(2) #include<bits/stdc++.h> #define ll long long #pragma GCC optimize(1) using namespace std; int n,m,h,q; ll a[505],b[505],c[505]; ll bb[250005];//bool bs(int R,ll ans) //{ // int l,r,mid; // l=1,r=R;mid=(l+r)>>1; // while(l<=r) // { // mid=(l+r)>>1; // if(bb[mid]==ans) // return true; // else if(bb[mid]>ans) // r=mid-1; // else if(bb[mid]<ans) // l=mid+1; // } // return false; //}int main() {int iCase = 0;ll x;while(~scanf("%d%d%d",&n,&m,&h)) {int top = 0,flag;for(int i = 1; i<=n; i++) scanf("%lld",&a[i]);for(int i = 1; i<=m; i++) scanf("%lld",&b[i]);for(int i = 1; i<=h; i++) scanf("%lld",&c[i]);//打表 for(int i = 1; i<=n; i++) {for(int j = 1; j<=m; j++) {bb[++top] = a[i] + b[j];}}sort(bb+1,bb+top+1);int tot = unique(bb+1,bb+top+1) - bb-1;scanf("%d",&q);printf("Case %d:\n",++iCase);while(q--) {scanf("%lld",&x);flag = 0;for(int i = 1; i<=h; i++) {if(binary_search(bb+1,bb+tot+1,x-c[i]) == 1) {printf("YES\n");flag = 1;break;}}if(!flag) printf("NO\n"); }}return 0 ;}

這題也可以Hash

半年前的博客？？忽然找到了，趕緊發一下。

總結

以上是生活随笔為你收集整理的【HRBUST - 1996】数学等式 （HASH 或 二分）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。