CF1520D Same Differences 题解

2024-09-08 05:07:12

Content

给定 \(n\) 个数 \(a_1,a_2,\dots,a_n\)，求有多少个二元组 \((i,j)\) 满足：

\(i<j\)。
\(a_j-a_i=j-i\)。

数据范围：\(t\) 组数据，\(1\leqslant a_i\leqslant n,\sum n\leqslant 2\times 10^5\)，\(1\leqslant t\leqslant 10^4\)。

Solution

很简单的一道题目。

我们将题目中的这个等式稍微移项一下就可以得到 \(a_i-i=a_j-j\)。然后这个题目就可以转化了。我们只需要边输入当前的 \(a_i\)，边加上 \(a_i-i\) 在前面 \(i-1\) 个数当中出现的次数，更新 \(a_i-i\) 出现的次数即可得到答案。计数器可以用 map 实现。

Code

int a[200007];

int main() {

	MT {

		map<int, int> vis;

		int n = Rint; ll ans = 0;

		F(int, i, 1, n) a[i] = Rint, ans += vis[a[i] - i], vis[a[i] - i]++;

		println(ans);

	}

    return 0;

}

最新文章

热门文章