【C++】競程筆記（枚舉習題練習）

https://zerojudge.tw/ShowProblem?problemid=c435

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    int max_left = a[0];
    int ans = INT_MIN; // INT_MIN 是 int 資料型態的最小值 -2^31
    for (int j = 1; j < n; j++) {
        ans = max(ans, max_left - a[j]);
        max_left = max(max_left, a[j]);
    }

    cout << ans << endl;
    return 0;
}

找最大差值。 $a[i] - a[j]$ ，但 $i<j$ 。

解題思路：定義一個變數 max_left = a[0]，然後用他去紀錄當前位置 $j$ 左邊的最大值（即 $a[0]$ 到 $a[j-1]$ 的最大值），而對於每個 $j$ ，計算 max_left - a[j] 的最大值。

而變數 $ans$ 則是用來記錄所有計算出的 max_left - a[j] 的最大值。

處理完當前的 $j$ 後，將 max_left 指定為 max(max_left, a[j])，以繼續用於下一個位置 $j+1$ 。

最後的時間複雜度為 $O(n)$ 。

大致上有三種情況要去考慮：

遞減數列： $\{5,4,3,2,1\}$ ，最大差值就是 $a[0] - a[4] = 4$ 。

遞增數列： $\{1,2,3,4,5\}$ ：

j = 1, 1 - 2 = -1, ans = -1, max_left = 2
…
j = 4, 4 - 5 = -1, ans = -1
最終 ans = -1, 所以最大差值就 -1。

相同元素的數列： $\{10000, 10000, 10000\}$ ：

j = 1, 10000 - 10000 = 0, ans = 0
j = 2, 10000 - 10000 = 0, ans = 0
最終 ans = 0, 所以最大差值 = 0。

https://codeforces.com/problemset/problem/1352/E

#include <bits/stdc++.h>
using namespace std;

int main() {
    // Optimize I/O
    ios::sync_with_stdio(false);
    cin.tie(0);

    int t;
    cin >> t;
    for (int test = 0; test < t; test++) {
        int n;
        cin >> n;
        
        vector<int> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
        
        // Compute prefix sums
        vector<long long> prefix(n + 1, 0); // {0, 0, ..., n+1 numbers 0}
        for (int i = 1; i <= n; i++) {
            prefix[i] = prefix[i - 1] + a[i - 1];
        }
        
        vector<bool> achievable(n + 1, false);
        for (int i = 0; i < n - 1; i++) {
            for (int j = i + 1; j < n; j++) {
                long long sum = prefix[j + 1] - prefix[i];
                if (sum > n) break; // No need to check larger sums
                achievable[sum] = true;
            }
        }
        
        // Count special elements
        int count = 0;
        for (int i = 0; i < n; i++) {
            if (achievable[a[i]]) { // a[i] ≤ n by problem constraint
                count++;
            }
        }
        
        cout << count << "\n";
    }
    
    return 0;
}

題目大意：

給定一個序列 $a_{1}, a_{2}, \cdots , a_{n}$ ，若有一個長度至少為 $2$ 的區間總和 $a_{l} + a_{l+1} + \cdots + a_{r} = a_{i}$ ，則 $a_{i}$ 是 special element。求序列內有幾個 special elements。