题意: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.
即给出一个A数组,B数组,C数组,和S个询问,每个询问给出一个X值,问是否存在符合条件的等式。
分析:可以用hash存下a数组和b数组中所有元素的和,然后可以用hash或者二分的方法查找是否存在x-ck即可。
View Code
#include#include #include using namespace std;const int maxn = 505;const int mod = 600000;const int INF = (1<<30);struct node{ int key; int count;}h[mod];int a[maxn];int b[maxn];int c[maxn];void add(int p){ int k = p%mod; if (k < 0) k += mod; while (h[k].count != 0) { if (h[k].key == p) { h[k].count++; break; } k = (k+1)%mod; } if (h[k].count == 0) { h[k].count++; h[k].key = p; }}bool find(int p){ int k = p%mod; if (k < 0) k += mod; while (h[k].count!=0) { if (h[k].key == p) return true; k = (k+1)%mod; } return false;}int main(){ int i, j,k; int l, n, m, s; int p; int ca = 1; while (scanf("%d %d %d",&l,&m,&n)!=EOF) { memset(h,0,sizeof(h)); for (i=0; i p || a[l-1]+b[m-1]+c[n-1]