题解：AT_abc417_c [ABC417C] Distance Indicators

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

思路

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

1 \le i < j \le n

j - i = a_j + a_i

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

j - a_j = i + a_i

那么，题目就变成了：有多少个

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。

CPP

#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;
}

题解：AT_abc417_c [ABC417C] Distance Indicators

文章操作

思路

相关推荐

评论

题解：AT_abc417_c [ABC417C] Distance Indicators