ABC128F Frog Jump题解

Iceturky · 2024-07-16 17:01:35 · 题解

文中 n 实际表示题目中的 n-1 。

设 d=A-B 。首先显然 d>0 。

观察性质，发现可以把整条路径拆成两条，从起点出发每隔 d 个都会经过，从终点往回走每隔 d 个也会经过，具体共经过几个点取决于 A 的取值。两条路径经过点数相同，点互不同。

然后枚举 d ，再枚举 A ，发现 A 需要满足 A\equiv n \pmod{d} 。而且 A\leq n ，所以 A 的取值个数只有 \frac{n}{d} 个。

发现不合法的方案满足 n\equiv 0\pmod{d}\land n-A\geq A 。后面条件的前者是第一条路径的结尾，后者是第二条路径的结尾，只要 d|n ，就可能出现两条路径涉及同一点的情况，路径是连续段，所以只需要判有无交即可。

代码好写，可以不需要用数组预处理前/后缀和，但是这样写比较简单。

因为在处理后缀和的时候可能会越界，所以开了两倍空间（因为这个调了好久/ll）

code

const int N=2e5+5;

int a[N];

int pre[N],suf[N];

signed main(){
    int n=read()-1;
    for(int i=0;i<=n;i++)
        a[i]=read();
    int ans=0;
    for(int d=1;d<=n;d++){
        for(int i=d;i<=n;i+=d)
            pre[i]=pre[i-d]+a[i];
        for(int i=n;i>=0;i-=d)
            suf[i]=suf[i+d]+a[i];
        for(int A=n%d+((n%d==0)+1)*d;A<=n;A+=d){
            if(n%d==0&&n-A>=A)
                continue;
            ans=max(ans,pre[n-A]+suf[A]);
        }
    }print(ans),pc('\n'); 
    return 0; 
}