短代码(一个马后炮)

Posted on发表于 , ,

没赶上报名截止日期，一直 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

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

仔细分析一下就是：

我的方法，排序用了 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。

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