题解：AT_abc417_c Distance Indicators

yszkddzyh · 2025-08-02 22:23:57 · 题解

观察式子：j - i = A_i + A_j，移项可得：i + A_i = j - A_j，发现此时等式左边只与 i 有关，右边只与 j 有关。

考虑枚举 i，每次将答案加上满足 i + A_i = j - A_j 的 j 的数量。

那么我们就需要先开一个 map，记为 cnt，在输入的时候对于每一个元素，进行 cnt[i - a[i]]++ 的操作。然后在枚举到每一个 i 的时候，进行 ans += cnt[i + a[i]] 统计答案。

题目说了 i < j，我们这样统计会不会统计进 i = j 的情况？其实不会，题目保证了 A_i \not = 0，因此不会有 i + A_i = i - A_i 的情况。

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N = 2e5 + 5;
int n, a[N];
map <int, int> cnt;

int main(){

    ios :: sync_with_stdio(false);
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i], cnt[i - a[i]]++;
    ll ans = 0;
    for(int i = 1; i <= n; i++)
        ans += cnt[i + a[i]];
    cout << ans;

    return 0;
}