题解：P16741 [GKS 2019 #G] Book Reading

· · 题解

题目大意：

给你三个整数 N、M、Q，分别表示一本书书的总页数、被撕掉的页数和读者数量，在给你被撕掉的页码以及读者读书的关键字（具体见这里），求所有读者能阅读的总页数。

思路：

第一想法就是定义一个数组存每一页的是否被撕的状态，最后在遍历并累加。于是你写下了如下代码：

#include<bits/stdc++.h>
using namespace std;
int T;
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>T;
    for(int t=1;t<=T;t++){
        int n,m,q,p[100005],r[100005],ans=0;
        bool zt[100005];
        memset(zt,1,sizeof(zt));
        cin>>n>>m>>q;
        for(int i=1;i<=m;i++){
            cin>>p[i];
            zt[p[i]]=0;
        }
        for(int i=1;i<=q;i++){
            cin>>r[i];
            for(int j=r[i];j<=n;j+=r[i]){
                if(zt[j]==1){
                    ans++;
                }
            }
        }
        cout<<"Case #"<<t<<": "<<ans<<"\n";
        ans=0;
    }
}

然后你就得到了这个。

那么，该如何优化呢？

我们采用类似动规的方法，定义一个数组 S，它的作用是储存当前数在 1 到 N 范围内的倍数中被撕掉的页数。 然后我们便能得到表达式：

ans=(n \div r)-s_r

最后再累加即可。

AC code（代码仅供学习参考使用）：

#include<bits/stdc++.h>
using namespace std;
int T;
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>T;
    for(int t=1;t<=T;t++){
        long long n,m,q,p[100005],ans=0,s[100005];
        bool zt[100005];
        memset(zt,1,sizeof(zt));
        memset(s,0,sizeof(s));
        cin>>n>>m>>q;
        for(int i=1;i<=m;i++){
            cin>>p[i];
            zt[p[i]]=0;
        }
        for(int i=1;i<=n;i++){
            for(int j=i;j<=n;j+=i){
                if(zt[j]==0) s[i]++;
            }
        }
        for(int i=1;i<=q;i++){
            long long r;
            cin>>r;
            ans+=(n/r)-s[r];
        }
        cout<<"Case #"<<t<<": "<<ans<<"\n";
        ans=0;
    }
}

点个赞再走吧！