ABC369C Count Arithmetic Subarrays

原题链接：C - Count Arithmetic Subarrays

Tag：模拟

题目描述

给你一个由 \(N\) 个正整数 \(A=(A_1,A_2,\dots,A_N)\) 组成的序列。

求有多少对整数 \((l,r)\) 满足： - \(1\leq l\leq r\leq N\)。 - 子序列 \((A_l,A_{l+1},\dots,A_r)\) 构成等差数列。

注意：长度为 \(1\) 的序列总是等差数列。

数据说明：

• \(1\leq N \leq 2\times 10^5\)
• \(1\leq A_i \leq 10^9\)

分析

考虑到题目要求的是连续的等差数列， 我们可以直接维护一个 \(ans\) 数组， 初始化让 \(ans_0 = 1 , ans_1 = 2\)， 因为第一个数字本身和前两个数字一起都能组成等差数列。

之后我们向后遍历，每次根据 \(a_i - a_{i-1}\) 和 \(a_{i-1} - a_{i-2}\) 的关系更新 \(ans\) 数组。 最后直接输出 \(ans\) 数组中的最大值就是答案。

代码实现

void NeverSayNever() {
    int n; cin >> n;
    vector<int> vec(n);
    for(auto &x : vec) cin >> x;
    vector<int> ans(n);
    ans[0] = 1;
    ans[1] = 2;
    for (int i = 2; i < n; ++i) {
        if(vec[i] - vec[i-1] == vec[i-1] - vec[i-2]){
            ans[i] = ans[i-1] + 1;
        }else{
            ans[i] = 2;
        }
    }
    cout << std::accumulate(ans.begin(), ans.end(),0L) << endl;
}

日志

本页面创建于 2024/09/20 19:52