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

1. 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。

2. 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。

解題思路：

首先可能會想到要直接枚舉所有可能的子陣列（從索引 $i$ 到 $j$，其中 $j \geq i+1$ ）並計算其和，時間複雜度為 $O(n^{3})$ （枚舉起點 $O(n)$ 、終點 $O(n)$ 、計算和 $O(n)$ ），因為題目限制 $n \leq 8000$ ，這樣會太慢。

所以可以使用 Prefix sum，前綴和去求區間和，那個 sum 就是在用前綴和求區間和了。

判斷式 `if (sum > n) break;` 是優化算法，如果總和加一加超過陣列長度的話，那基本上可以不用再檢查了，就直接 break。

最後是看 achievable 的布林值情況，如果 true 就計數，這邊 $O(n)$ 。

備註：後面的題目不知道為什麼 NTUCPC Guide 的連結打不開，所以就先這樣。喔對了，OwO 學長那題我解不出來，所以放棄 orz，link：https://zerojudge.tw/ShowProblem?problemid=c412