HDU 5400 Arithmetic Sequence：暴力枚舉優化版

另一種 O(n) 思路

預處理每個位置向左/向右最長等差段：
L1[i]：以 i 結尾、公差 d1 的最長段長度。
R2[i]：以 i 開頭、公差 d2 的最長段長度。
則以 i 為分界的雙公差區間數 = L1[i] * R2[i+1]。
單公差區間數直接累加 L1[i] 和 R2[i]。

代碼實現

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n, d1, d2;
    while (cin >> n >> d1 >> d2) {
        vector a(n+1);
        for (int i = 1; i <= n; ++i) cin >> a[i];
        vector L1(n+1), R2(n+1);
        L1[1] = 1;
        for (int i = 2; i <= n; ++i)
            L1[i] = (a[i] - a[i-1] == d1) ? L1[i-1] + 1 : 1;
        R2[n] = 1;
        for (int i = n-1; i >= 1; --i)
            R2[i] = (a[i+1] - a[i] == d2) ? R2[i+1] + 1 : 1;
        ll ans = 0;
        for (int i = 1; i <= n; ++i) ans += L1[i]; // d1段
        for (int i = 1; i <= n; ++i) ans += R2[i]; // d2段
        if (d1 != d2) {
            for (int i = 1; i < n; ++i)
                ans += (ll)L1[i] * R2[i+1]; // 雙公差段
        }
        cout << ans << '\n';
    }
    return 0;
}

優勢

• 邏輯極其清晰：預處理 + 一次累加。
• 無狀態機分支，不易出錯。
• 同樣 O(n) 時間、O(n) 空間。