AT_abc417_c 题解

蒟蒻第一次打AT比赛,写一发题解纪念一下

看见这次的A题和B题,以为AT的题目都很水,于是看见C题一下扑哧笑了,直接无脑枚举

#include <bits/stdc++.h>
using namespace std
int n,a[100100];
int main(){
  cin>>n;
  for(int i=1;i<=n;i++)cin>>a[i];
  int sum=0;
  for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
      if(j-i==a[i]+a[j])sum++;
  cout<<sum;
  return 0;
}

准备做D题,一看,欸?RE了…想了半天正解,没有思路,果断放弃

最后二十分钟,机房大佬突然来点播思路,一下明白了

题目问$j-i=a_i+a_j$,进行移项,可以得出$a_i+i=j-a_j$

数据范围$a_i≤2e5$,而$a_i+i$顶多是$4e5$,可以利用桶先统计$a_i+i$的个数,然后再枚举$j-a_j$,每次答案总数累加桶中的$j-a_j$对应的$a_i+i$的个数,最后输出答案,将$O(n^2)$的复杂度优化到$O(n)$

下附代码

#include <bits/stdc++.h>
using namespace std;
long long s[1001000];
long long a[1001000],n;
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
		s[a[i]+i]++;
	}
	long long sum=0;
	for(int j=1;j<=n;j++)sum+=s[j-a[j]];
	cout<<sum<<endl;
	return 0;
}

注:AT的题目一定要输出行末回车,而且这道题不要忘记long long(十年OI一场空,__________)

完结撒花!