题解：AT_abc417_c [ABC417C] Distance Indicators

· · 题解

推式子后的结论题。

我们把式子变形：j-i=A_i+A_j 变为 A_i+i=j-A_j，其中 A_i+i 和 j-A_j 都是可以很快速得到的。

于是我们考虑用一个桶记录每一个数字出现的频次，见代码：

#include <cstdio>
int a[200005], tong[400005];
int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) scanf("%d", a + i), ++tong[a[i] + i];
    long long ans = 0;
    for (int i = 1; i <= n; ++i) if (i - a[i] >= 0) ans += tong[i - a[i]];
    printf("%lld", ans);
}

下面是对这个代码的解释：

  1. 题目要求 i < j，上面的方法会不会导致出现 i \geq j 的情况出现？

    不会的。题目保证 1 \leq A_i，因此：

    i-A_i < j(i < j)

    也就是说，上面的累加过程只会匹配到在 i 前面的数字，这样就可以保证题目要求能完成。

  2. 桶要开多大？考虑极端情况 2 \times 10^5 + 2 \times 10^5=4 \times 10^5。
  3. 要开 long long。
  4. 代码的时间复杂度显然为 O(N)，空间复杂度为 O(N+W)（W 为值域）。