【二分】HDU 2141 Can you find it?
KIDx 的解题报告
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2141
题意很简单
很好的一道二分+降维思想的题！
#include <iostream>#include <algorithm>using namespace std;#define eps 1e-8#define PI 3.14159265#define POW2(x) x*x#define POW3(x) x*x*x#define POW4(x) x*x*x*xint a[505], b[505], c[505], bc[250005];int main(){int L, N, M, i, j, S, x, cc = 1, l, r, mid, k;while (~scanf ("%d%d%d", &L, &N, &M)){k = 0;for (i = 0; i < L; i++)scanf ("%d", a+i);for (i = 0; i < N; i++)scanf ("%d", b+i);for (i = 0; i < M; i++)scanf ("%d", c+i);for (i = 0; i < N; i++)for (j = 0; j < M; j++)bc[k++] = b[i] + c[j];sort (bc, bc+k);scanf ("%d", &S);printf ("Case %d:\n", cc++);while (S--){scanf ("%d", &x);for (i = 0; i < L; i++){int tp = x - a[i];l = 0, r = k - 1;while (l < r){mid = (l+r) / 2;if (bc[mid] == tp){puts ("YES");goto end;}else if (bc[mid] > tp)r = mid;else l = mid + 1;}}puts ("NO");end:;}} return 0;}