Description
老师在黑板上写了四个数列a,b,c,d，数列a,b,c,d分别有i,j,k,l个数，突然间老师很生气的把正在睡觉的豆子喊了起来，问：“这是你第x次上课睡觉了！现在给你个赎罪的机会，你从每个数列中选择一个数，有多少种选法使他们的和为x？”，豆子实在太慌乱了，小伙伴们能告诉豆子正确答案吗？Input 第一行有四个整数i,j,k,l(1<=i,j,k,l<=500)，第二行有i个数a1,a2...ai，第三行有j个数b1,b2...bj，第四行有k个数c1,c2...ck，第五行有l个数d1,d2...dl。第六行有一个数m,接下来m行询问，每行有一个数字x。(m<=10),(|x|<10^10),(|a|,|b|,|c|,|d|<=10^8)Output 输出有m行，每行输出一个x对应的答案。Sample Input2 2 2 21 23 45 67 8371617Sample Output014HINT时间给了3s，还是挺多的，枚举+二分就可以了。
写了三个，一直在优化时间最后终于优化到1s以内了O(∩_∩)O~~。
第一个1800ms。。
#include#include #include #include #include #include #include #include using namespace std;const int oo = 0x3f3f3f3f;const int maxn = 1e4+7;const int mod = 998244353;typedef long long LL;int a[maxn], b[maxn], c[maxn], d[maxn];LL ans;int main(){ int i, j, q, w, e, r, m, x, k; while(~scanf("%d %d %d %d", &q, &w, &e, &r)) { ans = 0; for(i = 0; i < q; i ++) scanf("%d", &a[i]); for(i = 0; i < w; i++)scanf("%d", &b[i]); for(i = 0; i < e; i++) scanf("%d", &c[i]); for(i = 0; i < r; i++)scanf("%d", &d[i]); sort(a, a+q); sort(b, b+w); sort(c, c+e); sort(d, d+r); scanf("%d", &m); while(m--) { scanf("%d", &x); ans = 0; for(i = 0; i < q; i ++) { if(a[i] > x) break; for(j = 0; j < w; j ++) { if(a[i]+b[j] > x) break; for(k = 0; k < e; k++) { if(a[i]+b[j]+c[k] > x) break; int v = x-a[i]-b[j]-c[k]; if(binary_search(d, d+r, v))ans++; } } } printf("%lld\n", ans); } } return 0;} /************************************************************** Problem: 1785 User: 2759894160 Language: C++ Result: Accepted Time:1858 ms Memory:1032 kb****************************************************************/
第二个 1600ms。。 只少了200不过聊胜于无，
#include#include #include #include #include #include #include #include using namespace std;const int oo = 0x3f3f3f3f;const int maxn = 1e4+7;const int mod = 998244353;typedef long long LL;int a[maxn], b[maxn], c[maxn], d[maxn];LL ans;void init(int &m, int o[], int n, int val){ m = lower_bound(o, o+n, val)-o; if(o[m] > val || m == n) m--;}int main(){ int i, j, q, w, e, r, m, x, k; int z, s, v; while(~scanf("%d %d %d %d", &q, &w, &e, &r)) { for(i = 0; i < q; i ++) scanf("%d", &a[i]); for(i = 0; i < w; i++)scanf("%d", &b[i]); for(i = 0; i < e; i++) scanf("%d", &c[i]); for(i = 0; i < r; i++)scanf("%d", &d[i]); sort(a, a+q); sort(b, b+w); sort(c, c+e); sort(d, d+r); scanf("%d", &m); while(m--) { scanf("%d", &x); ans = 0; init(z, a, q, x); init(s, b, w, x); init(v, c, e, x); for(i = 0; i <= z; i ++) { if(a[i] > x) break; for(j = 0; j <= s; j ++) { if(a[i]+b[j] > x) break; for(k = 0; k <= v; k++) { if(a[i]+b[j]+c[k] > x) break; int v = x-a[i]-b[j]-c[k]; if(binary_search(d, d+r, v))ans++; } } } printf("%lld\n", ans); } } return 0;} /************************************************************** Problem: 1785 User: 2759894160 Language: C++ Result: Accepted Time:1667 ms Memory:1032 kb****************************************************************/
第三个， 本来把后三个数组的所有和放到了一个新的数组里面， 不过500*500*500太大， 于是计划破产， 就放了2个500*500 500*500的。。（700ms 优雅的暴力）
#include#include #include #include #include #include #include #include using namespace std;const int oo = 0x3f3f3f3f;const int maxn = 1e6+7;const int mod = 998244353;typedef long long LL;int a[maxn], b[maxn], c[maxn], d[maxn];int fir[maxn], sec[maxn];LL ans;int main(){ int i, j, q, w, e, r, m, x, k, cnt, cnt1; while(~scanf("%d %d %d %d", &q, &w, &e, &r)) { cnt = cnt1 = ans = 0; for(i = 0; i < q; i ++) scanf("%d", &a[i]); for(i = 0; i < w; i++)scanf("%d", &b[i]); for(i = 0; i < e; i++) scanf("%d", &c[i]); for(i = 0; i < r; i++)scanf("%d", &d[i]); for(i = 0; i < q; i++) for(j = 0; j < w; j++) fir[cnt++] = a[i]+b[j]; for(i = 0; i < e; i++) for(j = 0; j < r; j++) sec[cnt1++] = c[i]+d[j]; sort(fir, fir+cnt); sort(sec, sec+cnt1); scanf("%d", &m); while(m--) { scanf("%d", &x); ans = 0; for(i = 0; i < cnt; i++) { int v = x-fir[i]; int l, r; if(binary_search(sec, sec+cnt1, v)) { l = lower_bound(sec, sec+cnt1, v)-sec; r = upper_bound(sec, sec+cnt1, v)-sec; ans += r-l; } } printf("%lld\n", ans); } } return 0;} /************************************************************** Problem: 1785 User: 2759894160 Language: C++ Result: Accepted Time:704 ms Memory:24312 kb****************************************************************/