P8809 [蓝桥杯 2022 国 C] 近似 GCD

翟翟 · 2023-01-17 12:00:44 · 题解

解法一

枚举区间左端点和右端点，扫描区间，看不是 g 的倍数的数是否小于等于 1 个，若是，则 ans+1。

代码略。

时间复杂度：\mathcal O(n^3)，期望得分 20 ~ 40 pts。

解法二

在解法一的基础上，进行优化。

我们把不是 g 的倍数的数标记成 1 ，把是 g 的倍数的数标记成 0。则问题被转化为求区间和小于等于 1 的区间个数。我们便可在边扫描边处理，当区间和大于 1 时，就退出当前循环。（这种思想最终可以演化为解法四）。

代码略。

或者使用前缀和。（这种思想最终可以演化为解法三）。

#include<cstdio>
int n,g,a[100001],x;
long long ans;
int main(){
    scanf("%d%d",&n,&g);
    for(int i=1;i<=n;++i){
        scanf("%d",&x);
        if(x%g)a[i]=1;
        a[i]+=a[i-1];
    }
    for(int i=1,j;i<n;++i){
        for(j=i+1;j<=n;++j)
            if(a[j]-a[i-1]>1)
                break;
        ans+=j-i-1;
    }
    printf("%lld\n",ans);
    return 0;
}

时间复杂度：\mathcal O(n^2)，期望得分 40 ~ 70 pts。

解法三

计 a_i 为数组前 i 个数的前缀和。

在解法二前缀和的基础上进行二分。 找到第一个大于 a_i+1 的 a_j 的位置。

#include<cstdio>
int n,g,a[100001],x;
long long ans;
int upper(int l,int r,int x){
    int mid;
    for(;l<=r;){
        mid=(l+r)>>1;
        if(a[mid]<=x)l=mid+1;
        else r=mid-1;
    }
    return l;
}
int main(){
    scanf("%d%d",&n,&g);
    for(int i=1;i<=n;++i){
        scanf("%d",&x);
        if(x%g)a[i]=1;
        a[i]+=a[i-1];
    }
    for(int i=1;i<n;++i)
        ans+=upper(i+1,n,a[i-1]+1)-i-1;
    printf("%lld\n",ans);
    return 0;
}

时间复杂度：\mathcal O(n log n)，期望得分 100 pts。

解法四

在解法二枚举的基础上用双指针乱搞一波，但也要前缀和。

时间复杂度：\mathcal O(n)，期望得分 100 pts。

代码略。