题解：AT_abc417_c [ABC417C] Distance Indicators

weifengzhaomi · 2025-08-03 08:11:26 · 题解

C 题什么时候那么水了...

思路

首先，题目要我们求满足以下两个条件的数对。

我们把第二个式子转化一下：

那么，题目就变成了：有多少个 i,j 满足 j - a_j = i + a_i。

注意，这里的 i,j 是不分先后顺序的。

为什么呢，因为，我们假设有一组 x,y 满足 x - a_x = y + a_y ，那么，不可能 y - a_y = x + a_x 是合法的。

所以，题目的第一个条件不用考虑，所以，先求出所有 i - a_i 的数量，在加上所有 i + a_i 的个数。

剩下的就是注意爆 int。

#include<bits/stdc++.h>
using namespace std;
#define int long long
unordered_map<int,int> mp;
int n,a[200010],ans;
signed main(){
    cin >> n;
    for (int i = 1;i <= n;i++) scanf("%lld",&a[i]),mp[i - a[i]]++;
    for (int i = 1;i <= n;i++) ans += mp[i + a[i]];
    cout << ans << endl;
}