AT_abc255_e 题解

思路

朴素做法

首先我们考虑一定可以有一个点是幸运数，于是我们可以考虑遍历每一个 \(S_i\)，钦定 \(a_i\) 是一个幸运数，然后我们就可以反推出 \(a_1\) 的值。然后我们统计 \(a_1\) 重复被计算出的次数。因为只要有一个 \(a_i\) 被确定了，整个序列就确定了。也就是说，\(a_1\) 的重复次数就是我们要求的最多的幸运数个数，因为他们都是同一个序列。如果我们这样做，时间复杂度是 \(\mathcal{O}(n^2m)\)，很显然无法通过本题。

优化做法

我们考虑如何优化这个算法。我们回顾一下计算 \(a_1\) 值的过程。我们假设已经确定了 \(a_x\) 的值：

• 如果 \(x\) 是奇数，那么很显然 \[ \begin{align} a_x &= S_{x - 1}-S_{x-2}+S_{x-3}-\cdots+S_{1}-a_1\\ a_1 &= (-1)^{x-1}\left(a_x - \left(S_{x - 1}-S_{x-2}+S_{x-3}-\cdots+S_{1}\right)\right) \end{align} \]
• 如果 \(x\) 是偶数，那么仍然很显然的是式子是 \[ \begin{align} a_x &= S_{x-1}-S_{x-2}+S_{x-3}-\cdots-S_1+a_1\\ a_1 &= (-1)^{x-1}\left(a_x - \left(S_{x-1}-S_{x-2}+S_{x-3}-\cdots-S_1\right)\right) \end{align} \]

很显然，由于 \(S_i\) 不会改变，\(\pm a_1\) 之前的一长串式子也不会改变，因此我们可以考虑预处理 \(\pm a_1\) 前面的式子，然后 \(\mathcal{O}(1)\) 求值。

让我们设 \(f_{i,\,0}\) 为此时 \(S_i\) 系数为负的情况，\(f_{i,\,1}\) 为此时 \(S_{i}\) 系数为正的情况。聪明的你可能发现了，\(f_{i,\,0}\) 在最终计算时不需要的，但是在预处理的过程中，这是必要的。很容易推出状态转移方程 \[ \begin{array}{c} f_{i,\,0}=f_{i-1,\,1}-S_i\\ f_{i,\,1}=f_{i-1,\,0}+S_i \end{array} \] 则对于选定的 \(a_x\)，其对应的 \(a_1=(-1)^{x-1}(a_x - f_{x-1,\,0})\)。

我们可以 \(\mathcal{O}(n)\) 预处理，然后采用朴素做法的思路统计答案，总复杂度为 \(\mathcal{O}(nm)\)，可以通过。

代码

#include <iostream>
#include <map>

#define int long long

using namespace std;

int n, m, s[100009], x[20], f[100009][2];
map<int, int> mp;

signed main() {
    cin >> n >> m;
    for (int i = 1; i < n; i++) {
        cin >> s[i];
    }
    for (int i = 1; i <= m; i++) {
        cin >> x[i];
    }
    for (int i = 1; i <= n; i++) {
        f[i][0] = f[i - 1][1] + s[i];
        f[i][1] = f[i - 1][0] - s[i];
    }
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            mp[(j & 1 ? 1 : -1) * (x[i] - f[j - 1][0])] += 1;
        }
    }
    int ans = 0;
    for (auto &[i, j]: mp) {
        ans = max(ans, j);
    }
    cout << ans;
}