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 Input
2 2 2 2
1 2
3 4
5 6
7 8
3
7
16
17
Sample Output
0
1
4
HINT
时间给了3s，还是挺多的，枚举+二分就可以了。
写了三个，一直在优化时间最后终于优化到1s以内了O(∩_∩)O~~。
第一个1800ms。。
#include<cstdio>
#include<cstring>
#include<stack>
#include<vector>
#include<queue>
#include<cmath>
#include<cstdlib>
#include<algorithm>
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
", ans);
}
}
return 0;
}
/**************************************************************
Problem: 1785
User: 2759894160
Language: C++
Result: Accepted
Time:1858 ms
Memory:1032 kb
****************************************************************/
第二个 1600ms。。 只少了200不过聊胜于无，
#include<cstdio>
#include<cstring>
#include<stack>
#include<vector>
#include<queue>
#include<cmath>
#include<cstdlib>
#include<algorithm>
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
", 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<cstdio>
#include<cstring>
#include<stack>
#include<vector>
#include<queue>
#include<cmath>
#include<cstdlib>
#include<algorithm>
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
", ans);
}
}
return 0;
}
/**************************************************************
Problem: 1785
User: 2759894160
Language: C++
Result: Accepted
Time:704 ms
Memory:24312 kb
****************************************************************/