题目大意

灵梦当前拥有的樱点可以使用一个变量 $c$ 存储，初始时为 $0$。当樱点在某个瞬间恰好变为了 $k$，灵梦就会展开樱之结界，同时 $c$ 变为 $0$。

现在她把路程依次划分为了 $n$ 个关卡，其中第 $i$ 关上，灵梦一共可以获得 $a_i$ 点樱点。这些樱点是均匀分布在这关的路程上的。也就是说，随着这段路程的进行，灵梦的樱点个数会依次增加，每次增加 $1$ 个单位（$c\gets c+1$），恰好在这段路程结束的瞬间会收集到这关中第 $a_i$ 点樱点。

灵梦提出了 $m$ 个要求。第 $i$ 个要求 $b_i$ 表示灵梦希望在第 $b_i$ 段路程结束的瞬间，恰好展开樱之结界（如果在这段路程的中途展开但是结束的瞬间没有展开，那就不算达成了要求）。

灵梦可以选择在某个关卡开头放 bomb，跳过整个关卡的樱点收集。这样的机会有且仅有一次（当然，灵梦可以选择不使用 bomb）。

现在需要求出，在最优的选择下，灵梦最多可以达成多少个要求。

思路

70分

直接模拟一遍不 bomb 的值，这样就能求出来每一个关卡时 $c$ 的值，之后枚举 bomb 的关卡然后直接 $i-1$ 的答案加上从 $c_{i-1}$ 开始模拟。

时间复杂度为 $O(n^2)$。

100分

我们从暴力发现，$x$(bomb 关卡) 之前的值是不会改变的。那么我们只需要求 $x$ 右边的 $b$ 之中的关卡的 $f_i\equiv a_x (\bmod k)$ 即可，$f$ 为 $a$ 的前缀和。

我们记录两个数组 $l,r$ 分别为当前 $x$ 的左边与右边在 $b$ 的区间里 $f_i\bmod k$ 的个数。那么针对每一个 bomb 的区间的值就是 $l_0+r_{a_x\bmod k}$。

我们先正着把 $l$ 求出来，再倒着 bomb，有些类似双指针的思想。我们一旦看到了一个 $b$ 之中的关卡，就把 $l_{f_i\bmod k}-1$，因为向 $1$ 退了一格自然也是要去掉的。之后我们做计算。然后相反，由于从 $r$ 的角度相当于前进了一格，所以要 $+1$。我们不可以先 $+1$ 因为 $r$ 是要在区间后的，还没有计算完毕当然不能前进。

代码

#include <iostream>

using namespace std;
typedef long long ll;
const ll MAXN = 3e5 + 5;
ll n, m, k, a[MAXN];
ll f[MAXN], l[MAXN], r[MAXN];
bool ask[MAXN];

int main() {
   scanf("%lld%lld%lld", &n, &m, &k);
   for (int i = 1; i <= m; ++i) {
       ll b;
       scanf("%lld", &b);
       ask[b] = true;
   }
   for (int i = 1; i <= n; ++i) {
       scanf("%lld", &a[i]);
       f[i] = f[i - 1] + a[i];
       if (ask[i]) {
           l[f[i] % k]++;
       }
   }
   ll ans = l[0];
   for (ll i = n; i >= 1; --i) {
       if (ask[i]) {
           l[f[i] % k]--;
       }
       ans = max(ans, l[0] + r[a[i] % k]);
       if (ask[i]) {
           r[f[i] % k]++;
       }
   }
   cout << ans << endl;
   return 0;
}
复制代码

总结

这道题目仍然可以从暴力上找规律。本身还是“以不变应万变”的思考方式。先找到题目不变的部分（本题为不 bomb），然后将变化的部分添加进思考中与不变的结论结合通常就可以找到答案了。