ARC170B - Arithmetic Progression Subsequence

wflengxuenong · 2024-01-22 19:32:56 · 题解

• 题目大意

给定一个长度为n的序列，如果区间 [L,R] 中存在 L \leq i<j<k\leq R ,使得 a_i-a_j=a_j-a_k 成立，则这个区间为好区间。问共有多少个好区间。

• 题目分析

为了不重不漏的统计，我们限定右端点 k ,去找符和要求的左端点 left 。 找出符要求的 i,j,k ,可以发现 a_i,a_j,a_k 构成等差数列，数据的范围是 1...10 ,符合要求的的情况为 1，5，9 ; 10， 6，2 等。可以推导出公差的范围为 -4..4 .

已知 a_k ,枚举公差，找到符合要求的前两项的值，设数组 mp[i][j] 存储符合要求的最近数值。找到以 k 为结束点的最近 left。

如何去维护 mp[i][j] 呢？对于当前点 k 来说，只会改变与 mp[i][a_k] 相关的数据，mp[i][a_k]=( i 出现的最后位置 ) 。因此我们还需要用一个桶记录这个位置。

再维护一个 left 的前缀 max\_left ,那么答案就是不断累加从 1号结点到 max\_left 的值，也就是 ans+=max\_left 。

时间复杂度为 O(N \times 10) 。

• 参考代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n;
int a[100005];
int mp[11][11],l[11];
signed main(){

    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];

    int ans=0,lf=0,mlf=0;
    //对每一个右端点q，找其符合要求的最近左端点lf，和前缀最大左端mlf点比较  ans+=mlf
    for(int k=1;k<=n;k++) {
        for(int d=-4;d<=4;d++){//枚举公差 
            if(a[k]+2*d>=1&&a[k]+2*d<=10)lf=max(lf,mp[a[k]+2*d][a[k]+d]);
            mlf=max(mlf,lf);
        }
        ans+=mlf;
        for(int i=1;i<=10;i++){
            if(l[i])mp[i][a[k]]=l[i];
        }
        l[a[k]]=k;  
    }

    cout<<ans<<endl;
}