[数据结构与算法]codeforces 1520 D. Same Differences（1200，水）

链接：https://codeforces.ml/problemset/problem/1520/D

题意：

给定一个数组，判断满足i<j 且?aj?ai=j?i的有几对；

题解：

式子进行变形，ai-i=aj-j；然后把所有结果放进容器，用组合数算答案；记得开LL；

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<int>s;
int main()
{
	int t;
	cin >> t;
	while (t--)
	{
		int n;
		cin >> n;
		s.clear();
		for (int i = 1; i <= n; i++)
		{
			int a;
			cin >> a;
			s.push_back(a - i);
		}
		sort(s.begin(), s.end());
		ll ans = 0;
		int key = s[0];
		ll cnt = 1;
		for (int i = 1; i < n; i++)
		{
			if (key == s[i])
			{
				cnt++;
			}
			else if(key != s[i])
			{
				if (cnt > 2)
				{
					ll x = 1;
					int num = cnt - 2;
					for (int j = cnt; j >cnt-2; j--)
					{
						x *= j;
					}
					ans += x / 2;
				}
				else if (cnt == 2)ans += 1;
				cnt = 1;
				key = s[i];
			}
			if (i == n - 1)
			{
				if (cnt > 2)
				{
					ll x = 1;
					int num = cnt - 2;
					for (int j = cnt; j > cnt - 2; j--)
					{
						x *= j;
					}
					ans += x / 2;
				}
				else if (cnt == 2)ans += 1;
			}
		}
		cout << ans << endl;
	}
}