from NOIP2016模拟题34

Description

给定一个长度$n\le 10^6$的序列, 给定$A, B$

给出一个序列，要求你通过如下两个操作使得序列中所有数的最大公约数大于1，每个操作最多使用一次

1：删除一段连续的数，代价为删除的长度$*A $

2：将任意多个数+1或-1，代价为 $B *$数的个数

Analysis

由于删除也至少留下一个数

最后的gcd一定是a[1]-1,a[1],a[1]+1,a[n]-1,a[n],a[n]+1六个数中

某个数的质因数的倍数

Solution

考虑每个可能的质因数:

two_pointer搞出删除的区间

其他用修改操作

预处理出哪些数必须修改chg[i]

哪些数必须删除must[i]

若对当前two_pointer区间

修改要修改的数优于区间删除

就将左区间右移一下

two_pointer移的时候要保证合法

Code

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cmath>

#include <algorithm>

using namespace std;

typedef long long LL;

const int M=1000007;

inline int rd(){

    int x=0;bool f=1;char c=getchar();

    for(;!isdigit(c);c=getchar()) if(c=='-') f=0;

    for(;isdigit(c);c=getchar()) x=x*10+c-48;

    return f?x:-x;

}

int n;

int a[M];

int fac[M*12],cnt=0;

LL A,B;

LL chg[M];

LL must[M];

LL ans=9223372036854775807;

void solve(int p){

    int i,l,r;

    for(i=1;i<=n;i++){

        chg[i]=must[i]=0;

        if (a[i] % p == 0) continue;

        if((a[i]+1)%p==0||(a[i]-1)%p==0) chg[i]=1;

        else if(a[i]%p) must[i]=1;

    }

    for(i=1;i<=n;i++) chg[i]+=chg[i-1];

    for(i=1;i<=n;i++) must[i]+=must[i-1];

    for(l=1,r=1;r<=n;r++){//two_pointer求删除区间

        if(must[n]-must[r]) continue;//不合法

        if(l==1&&r==n) l=2;//不能全删

        while(l<=r&&must[l]==0&&(chg[r]-chg[l-1])*B<=(r-l+1)*A) l++;//更优且移动和合法

        ans=min(ans,(chg[l-1]+chg[n]-chg[r])*B+(r-l+1)*A);

    }

}

void split(int x){

    for(int i=2;i*i<=x;i++){

        if(x%i==0) fac[++cnt]=i;

        while(x%i==0) x/=i;

    }

    if(x>2) fac[++cnt]=x;

}

int main(){

    int i;

    n=rd(),A=rd(),B=rd();

    for(i=1;i<=n;i++) a[i]=rd();

    split(a[1]); split(a[1]-1); split(a[1]+1);

    split(a[n]); split(a[n]-1); split(a[n]+1);

    sort(fac+1,fac+cnt+1);

    cnt=unique(fac+1,fac+cnt+1)-(fac+1);

    for(i=1;i<=cnt;i++)

        solve(fac[i]);

    printf("%lld\n",ans);

    return 0;

}

巴特西

xsy 1845 - GCD

Description

Analysis

Solution

Code

最新文章

热门文章