ABC128F

cosf · 2024-03-19 20:45:04 · 题解

ABC128F

校内模拟赛做到这题，很快切了。

令 d = a - b。则它跳到的点一定是两个等差数列：

显然，它走的顺序是 0, a, d, a + d, 2d, \dots，结束在 a+kd，也就是说，a+kd 就是 n-1。

我们可以枚举 d，显然符合要求的 a 只有 O(\frac{n}{d}) 个，并且，它们是 n - 1, n - 1 - d, \dots, n - 1 - kd。

如果 a=n-1，显然答案就是 0，否则，可以从 a' = a + d 递推得来。

观察等差数列，发现多了的两项就是 kd 和 a。只要这两个和原来的数列中没有重复，就可以更新答案。

判断重复：只要 (k-1)d, kd, a 中没有相同即可。证明略。

代码

#include <iostream>
using namespace std;

#define MAXN 100005

using ll = long long;

int n;

ll val[MAXN];

int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> val[i];
    }
    ll res = 0;
    for (int d = 1; d < n; d++) // a - b
    {
        ll sr = 0;
        ll cr = 0;
        int k = -d;
        for (int j = n - 1; j > d; j -= d) // a
        {
            if (j == k)
            {
                break;
            }
            k += d;
            if (j == k)
            {
                break;
            }
            sr += val[j];
            if (k > -1)
            {
                sr += val[k];
            }
            cr = max(cr, sr);
        }
        res = max(res, cr);
    }
    cout << res << endl;
    return 0;
}