AT_abc369_c 题解

ikunTLE · 2024-09-01 16:33:43 · 题解

题目传送门

思路

开一个变量表示当前等差数列的长度，设其为 X。设记录答案的变量为 S。

对于第 i 个点，若 A_i-A_{i-1}=A_{i-1}-A_{i-2}，说明等差数列长度增加，即 X\gets X+1。否则将 X 变为 2，因为任意 2 个数都会组成一个等差数列，并用等差数列求和公式更改 S 的值，即 S\gets S+\frac{X^2+X}{2}。

AC CODE

#include<bits/stdc++.h>
using namespace std;
int read(){int x=0;char f=1,ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}
const int N=2e5+10;
int a[N];
int main(){
    int n=read();
    if(n==1)
        return printf("1\n"),0;
    for(int i=1;i<=n;++i)
        a[i]=read();
    int cnt=1;
    long long ans=n;
    for(int i=2;i<=n;++i)
        if(i>2&&a[i]-a[i-1]==a[i-1]-a[i-2])
            ++cnt;
        else{
            ans+=(long long)cnt*(cnt-1)/2;
            cnt=2;
        }
    ans+=(long long)cnt*(cnt-1)/2;
    printf("%lld\n",ans);
    return 0;
}