kickstart-2019-G-T1-BookReading

上周六和同学一起尝试了一下Google Kickstart的题目，开了开眼，涨了涨见识！
本文是G轮第一题BookReading的思路以及代码，留个纪念。

题目详情

Problem

Supervin is a librarian handling an ancient book with N pages, numbered from 1 to N. Since the book is too old, unfortunately M pages are torn out: page number P1, P2, …, PM.

Today, there are Q lazy readers who are interested in reading the ancient book. Since they are lazy, each reader will not necessarily read all the pages. Instead, the i-th reader will only read the pages that are numbered multiples of Ri and not torn out. Supervin would like to know the sum of the number of pages read by each reader.

Input

The first line of the input gives the number of test cases, T. T test cases follow. Each test case begins with a line containing the three integers N, M, and Q, the number of pages in the book, the number of torn out pages in the book, and the number of readers, respectively. The second line contains M integers, the i-th of which is Pi. The third line contains Q integers, the i-th of which is Ri.

Limits

Time limit: 40 seconds per test set.
Memory limit: 1GB.
1 ≤ T ≤ 100.
1 ≤ P1 < P2 < … < PM ≤ N.
1 ≤ Ri ≤ N, for all i.

Test set 1 (Visible)
1 ≤ M ≤ N ≤ 1000.
1 ≤ Q ≤ 1000.

Test set 2 (Hidden)
1 ≤ M ≤ N ≤ 105.
1 ≤ Q ≤ 105.

Sample

题意理解

图书管理员想知道大家一共读了多少页书，需要我们统计。
已知情况是书的总页数N，坏了的页数M，有Q个读者。
然后知道坏的M分别是那些页，知道读者每个人都要读那些页（实际上知道的是基数，这个读者会读这个基数的整数倍）。

解题思路

如果大家想看最终结果，可以直接翻到最后，然后前面的代码写的比较乱，后来经过王博指点，有了很大的改善。好的代码习惯还是要保持的。

暴力求解

一看题目很简单，对于每个人来说，如果书籍不坏，那么他可以读页数/基数页，然后看看坏了的页数中有几个是基数的倍数，减去就可以。然后我们最终的结果就是每个人的结果加和。
代码如下，写的很乱，而且第二个样例不出意外的超时了。

#include<iostream>
#include <vector>
using namespace std;
void solve(int case_num){
    int N,M,Q;
    cin>>N>>M>>Q;
    vector<int> torn;
    int res =0;
    //vector<int> reader;
    for(int i = 0;i<M;i++){
        int mi;
        cin >> mi;
        torn.emplace_back(mi);
    }
    for(int i =0;i<Q;i++){
        int ri;
        cin >> ri;
        int num = N/ri;
        int sortnum =0;
        for(int j = 0;j<M;j++){
            if(torn[j]%ri==0){
                sortnum++;
            }
        }
        res += (num - sortnum);
    }
    cout << "Case #" << case_num << ": " << res << endl;
    
}

int main(){
  int t;
  cin >> t;
  for (int i = 1; i <= t; ++i) {
    solve(i);
  }
  return 0;
}

动态规划求解

仔细想想，其实我们上面暴力的时间复杂度是O（MQ），当破坏的页数很多的时候，很多判断是无效的，没有意义的，比如某位读者只读2的倍数，那么我其实只要判断2，4，6，2n<=N这些页就可以。其他的页数完全可以不用判断，所以这个地方可以简化。于是是不是可以把每个基数对应的结果都算出来，然后当读读者的基数的时候，直接将其求和就可以呢？当然可以！于是就有了下面的代码。

#include<iostream>
#include <vector>
#include <cstring>
using namespace std;
typedef long long LL;
const int MAXN = 1e5+10;

int a[MAXN],ans[MAXN];

int main(){
  int t,x;
  scanf("%d",&t);
  for (int i = 1; i <= t; ++i) {
        int N,M,Q;
        scanf("%d %d %d",&N,&M,&Q);

        for(int i = 1;i<=N;i++){
            a[i] = 1;
        }
      
        for(int i = 1;i<=M;i++){
            scanf("%d",&x);
            a[x] = 0;
        }
        
        for(int i = 1; i<=N; i++){
            for(int j =i; j <= N; j+=i){
                 ans[i] += a[j];
            }
        }
        
        LL res =0;
        for( int i = 1; i <= Q; i++){
            scanf("%d",&x);
            res += ans[x];
        }
        printf("Case #%d: %lld\n",i,res);
        
        for(int i = 0;i<=N;i++){
            ans[i] = 0;
            a[i] =0;
        }
        
  }
  return 0;
}

进一步动态规划

上面的方法把所有的基数对应的结果都算出来了，但是其实中间的很多结果我们是用不到的，比如我们就两个读者，分别读2的倍数和3的倍数，而上面那个方法将1-N的所有结果都算出来了，最后只用了2和3对应的结果而已，这样就造成了浪费。所以我们是不是可以将结果进行保存，下次来了一个读者，看看之前有没有算过，如果算过，就直接用之前保存的结果，如果没有算过，那么就计算一下，然后保存起来呢？当然可以！于是就有了下面的代码。

#include<iostream>
#include <vector>
#include <cstring>
using namespace std;
typedef long long LL;
const int MAXN = 1e5+10;

int getPage(int N,int i,int arr[]){
    int res =0;
    for(int j = i; j<=N; j+=i){
        res += arr[j];
    }
    return res;
}

int a[MAXN],ans[MAXN];
int N,M,Q;

int main(){
  int t,x;
  scanf("%d",&t);
  for (int i = 1; i <= t; ++i) {
        scanf("%d %d %d",&N,&M,&Q);
        for(int i = 1;i<=N;i++){
            a[i] = 1;
        }
      
        for(int i = 1;i<=M;i++){
            scanf("%d",&x);
            a[x] = 0;
        }
        memset(ans, 0, sizeof ans);
      
        LL res =0;
        for( int i = 1; i <= Q; i++){
            scanf("%d",&x);
            if(ans[x]==0){
                ans[x] = getPage(N, x,a);
            }
            res += ans[x];
        }
        printf("Case #%d: %lld\n",i,res);

  }
  return 0;
}

本题收获

了解到了比较好的编码规范，以后会应用到实践中。
锻炼了自己分析问题的能力，提高算法的效率很重要，而其中的意识要逐渐培养。
认识到了c++灵活但是有时候太灵活，以后需要好好注意如何使用。
知道了kickstart的难度以及自己的水平。刷题路漫漫，以后请加油。