# 0-17 vector

講義不是我寫的，網址在此 https://emanlaicepsa.github.io/2020/10/21/0-index/
我只是將自己寫的練習題程式碼記錄下來。由於 Python 基本上都是用串列解題，不像 C++ 有 array 及 vector 的差別，所以底下的練習題只有 C++ 程式碼。
最後更新日期：2024年10月7日

## [TOJ: 114 / 我閉著眼](https://toj.tfcis.org/oj/pro/114/)

### C++ 程式碼

執行時間最久約為 1 ms，使用記憶體最多約為 308 kB，通過測試。

#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    vector<vector<int>> grid (5, vector<int> (6));  // 盤面資料
    for(int r=0; r<5; r++)
        for(int c=0; c<6; c++)
            cin >> grid[r][c];
    
    bool flag = false;  // 是否有找到解
    for(int r=0; r<5; r++) {  // 依序檢查第 0 ~ 4 列
        if (flag) break;  // 如果已找到解，中止迴圈
        for(int c=0; c<3; c++) {  // 依序檢查第 0 ~ 2 欄
            int now = grid[r][c];  // 現在的格子數字
            if (now == grid[r][c+1] && now == grid[r][c+2]) {  // 檢查右側兩欄
                flag = true; break;  // 如果數字皆等於 now，找到解，中止迴圈
            }
        }
    }
    for(int c=0; c<6; c++) {  // 依序檢查第 0 ~ 5 欄
        if (flag) break;  // 如果已找到解，中止迴圈
        for(int r=0; r<2; r++) {  // 依序檢查第 0 ~ 1 列
            int now = grid[r][c];  // 現在的格子數字
            if (now == grid[r+1][c] && now == grid[r+2][c]) {  // 檢查下方兩列
                flag = true; break;  // 如果數字皆等於 now，找到解，中止迴圈
            }
        }
    }
    cout << (flag ? "Yes" : "No") << "\n";  // 如果找到解印出 Yes，否則印出 No
    return 0;
}

## [TOJ: 119 / B. Brainwash](https://toj.tfcis.org/oj/pro/119/)

### C++ 程式碼

執行時間最久約為 37 ms，使用記憶體最多約為 1384 kB，通過測試。

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n; cin >> n;
    vector<int> data (n+1, 0);
    for(int i=1; i<=n; i++) cin >> data[i];
    int t; cin >> t;
    bool flag = true;
    for(int i=0; i<t; i++) {
        int a, b; cin >> a >> b;
        if (!flag) continue;
        if (abs(a-b) > 8) {
            cout << "I QUIT!\n";
            for(int j=1; j<=n; j++) cout << data[j] << " \n"[j == n];
            flag = false;
        } else {
            int c = data[a];
            data[a] = data[b];
            data[b] = c;
        }
    }
    if (flag) {
        cout << "SORTED!\n";
        for(int j=1; j<=n; j++) cout << data[j] << " \n"[j == n];
    }
    return 0;
}

## [TOJ: 120 / C. Counting Stars](https://toj.tfcis.org/oj/pro/120/)

### C++ 程式碼

執行時間最久約為 71 ms，使用記憶體最多約為 3192 kB，通過測試。

#include <iostream>
#include <algorithm>
#include <vector>
typedef long long LL;
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int N; cin >> N;
    vector<LL> psum (N+1, 0);
    for(int i=1; i<=N; i++) {
        LL n; cin >> n;
        psum[i] = psum[i-1] + n;
    }
    int Q; cin >> Q;
    for(int i=0; i<Q; i++) {
        int le, ri; cin >> le >> ri;
        if (le > ri) swap(le, ri);
        cout << psum[ri] - psum[le-1] << "\n";
    }
    return 0;
}

## [TOJ: 501 / pD. 團ㄎㄧㄤ遊戲](https://toj.tfcis.org/oj/pro/501/)

### C++ 程式碼

執行時間最久約為 14 ms，使用記憶體最多約為 1044 kB，通過測試。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n; cin >> n;
    vector<int> m (2*n+1, 0);
    for(int i=1; i<=n; i++) {
        cin >> m[i]; m[i+n] = m[i];
    }
    int ans = 0, now = 0;
    for(int i=1; i<=2*n; i++) {
        now = min(now+1, m[i]);
        ans = max(ans, now);
    }
    cout << min(ans, n) << "\n";
    return 0;
}

------

###### tags:`演算法`、`APCS`、`Python`、`C++`