复杂 (Feed)

短代码(一个马后炮)

没赶上报名截止日期,一直 not invited。就很难过。

E 的题目描述是这样的。

Description

tz学姐做题很忙,有一些简单的问题需要你帮忙解决:给定三个序列A,B,C和一个整数X, 现在需要找到三个数Ai,Bj,Ck,满足Ai+Bj+Ck = X.

Input

第1行三个整数 L, N, M;

第2行L个整数代表序列A

第3行M个整数代表序列B

第4行N个整数代表序列C

第5行1个整数S代表有S个X。

接下来的S行每行一个整数X

1<=L, N, M<=500, 1<=S<=1000. 所有整数均在32位整数范围内

Output

对于S个询问计算X对应的公式是否能被满足。 如能满足,输出 “YES”, 否则输出 “NO”。

Sample Input

1
2
3
4
5
6
7
8
3 3 3
1 2 3
1 2 3
1 2 3
3
1
4
10

Sample Output

1
2
3
NO
YES
NO

我当时给出的代码是这样的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int l,m,n;
cin>>l>>m>>n;
int a[l],b[m],c[n];
for(int&p:a)cin>>p;
for(int&p:b)cin>>p;
for(int&p:c)cin>>p;
sort(c,c+n);
cin>>n;
for(int p;cin>>p;){
for(int q:a)
for(int r:b)
if(binary_search(c,c+n,p-q-r)) {
cout<<"YES\n";
goto l;
}
cout<<"NO\n";
l:1;
}
}
//292

由于我不能提交,无法判断它是否超时了。查了一下网上的做法,是把 ab 加起来存到另一个数组里,然后对这个新的数组排序查找。

仔细分析一下就是:

我的方法,排序用了 O(n*log n),查找 O(n**2*log n)

另一个做法,排序 O(n**2*log n),查找 O(n*log n)

看上去好像正好抵消了没什么区别。问题在于查找是多次查找,我们希望每次查找的时间尽量短。

所以改过的代码是这样的:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int l,m,n,r=0;
cin>>l>>m>>n;
int a[l],b[m],c[n],S[l*m]; // GNU 扩展的变长数组
for(int&p:a)cin>>p;
// range-for 输入第二组数据,同时将输入的数据和第一组的每一个数字相累加,结果存到 `S` 里。
for(int&p:b) {
cin>>p;
for(int&q:a)S[r++]=p+q;
}
for(int&p:c)cin>>p;
sort(S,S+r);
cin>>n; // 丢弃个数信息,因为不需要
for(int p;cin>>p;){
for(int q:c)
if(binary_search(S,S+r,p-q)){
puts("YES");
goto l; // 直接跳到下次输入,不输出 NO
}
puts("NO");
l:1;
}
}
//311

排名表上最短是345。

但是有什么用呢。我又不能提交(以后一定要提前关注一下)。