市長的隨筆

我也好想成為電神喔～

發布於 更新於 分類於 ， 文章字數： 424 所需閱讀時間 ≈ 2 分鐘

題目連結

j180: 戰備存糧 (Food)

我的想法

這題比較有趣，也有點像貪婪，涉及到每次食物下次減少時，倉庫的個數也要減少到最佳狀況（把倉庫減少當成守衛減少）。可以直接看我程式碼應該會比較好理解。

舉例

1
3 4

這筆測資食物總共有 12 個。

第一天減少 3 個（倉庫當前數量；守衛數量）：12 - 3 = 9

確認剩下的食物是否可以塞進小於等於當前倉庫數量的大小（每次減少 -1）：(3 - 1) * 4 = 8

9 <= 8 所以今天先不減小

第二天減少 3 個（倉庫當前數量；守衛數量）：9 - 3 = 6

確認剩下的食物是否可以塞進小於等於當前倉庫數量的大小（每次減少 -1）：(3 - 1) * 4 = 8

6 <= 8 所以今天倉庫數量減至 2

第三天減少 2 個（倉庫當前數量；守衛數量）：6 - 2 = 4

確認剩下的食物是否可以塞進小於等於當前倉庫數量的大小（每次減少 -1）：(2 - 1) * 4 = 4

4 <= 4 所以今天倉庫數量減至 1

最後四天相同做法（也可以判斷數量為 1 時，剩下食物個數加上前面 n 天之後，直接輸出 3 + 4 = 7 天，不過應該不影響答案）

參考解答

j180
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int a, b;
    vector<pair<int, int>> depositary;
    while (cin >> a) {
        if (a == -1) break;
        cin >> b;
        depositary.push_back(make_pair(a, b));
    }
    for (int i = 0; i < depositary.size(); i++) {
        int days = 0;
        int food = depositary[i].first * depositary[i].second;
        while (food != 0) {
            food -= depositary[i].first;
            days++;
            while (food <= (depositary[i].first - 1) * depositary[i].second) {
                depositary[i].first--;
            }
        }
        cout << days << "\n";
    }
    return 0;
}

發布於 更新於 分類於 ， 文章字數： 244 所需閱讀時間 ≈ 1 分鐘

題目連結

j179: 資料分類 (Classification)

我的想法

這題用到 #include <string> 裡的 stoi() 函式和 to_string() 函式。（如果你想自己寫出來這兩個函式也可以www）

然後其他照著題目敘述做應該可以吧！

stoi() 用法

use_stoi()
1
2
3
4
5
6
7
8
9
#include <iostream>
#include <string>
using namespace std;

int main() {
    string str = "01234";
    int a = stoi(str);
    cout << "a = " << a << "\n";
}
1
2
輸出：
a = 1234

to_string() 用法

use_to_string()
1
2
3
4
5
6
7
8
9
#include <iostream>
#include <string>
using namespace std;

int main() {
    int num = -1234;
    string str = to_string(num);
    cout << "str = " << str << "\n";
}
1
2
輸出：
str = -1234

參考解答

j179
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <iostream>
#include <string>
using namespace std;

string solve(string num, int len) {
    int n = stoi(num), a = 0, b = 0;
    switch (len) {
        case 4:
            a = n / 100;
            b = n % 100;
            if (a > 9) a = (a / 10) * (a % 10);
            if (b > 9) b = (b / 10) * (b % 10);
            if (a == 0) return to_string(b);
            num = to_string(a) + to_string(b);
            return num;
        case 3:
            a = (n / 100) * ((n / 10) % 10);
            b = ((n / 10) % 10) * (n % 10);
            num = to_string(a) + to_string(b);
            return num;
        case 2:
            a = n / 10;
            b = n % 10;
            num = to_string(a * b);
            return num;
        default:
            return "0";
    }
    return "0";
}

int main() {
    string num;
    cin >> num;

    while (num.size() != 1) {
        num = solve(num, num.size());
    }
    cout << num;
    return 0;
}

發布於 更新於 分類於 ， 文章字數： 73 所需閱讀時間 ≈ 1 分鐘

題目連結

j178: 手遊廣告 (Advertisement)

我的想法

水題。

參考解答

j178
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
using namespace std;

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

    int m, a;
    cin >> m >> a;
    int T[m];
    for (int i = 0; i < m; i++) {
        cin >> T[i];
    }
    for (int i = 0; i < m; i++) {
        if (a <= T[i]) break;
        a += T[i];
    }
    cout << a << "\n";

    return 0;
}

發布於 更新於 分類於 ， 文章字數： 199 所需閱讀時間 ≈ 1 分鐘

題目連結

d732: 二分搜尋法

我的想法

純純的二分搜尋

範例：找 8

1
2
3
1 2 3 4 5 6 7 8 9
↑       ↑       ↑
l       m       r

5 < 8 所以左邊往中點 +1 移動

1
2
3
1 2 3 4 5 6 7 8 9
          ↑ ↑   ↑
          l m   r

7 < 8 所以左邊往中點 +1 移動

1
2
3
4
1 2 3 4 5 6 7 8 9
              ↑ ↑
              l r
             (m)

8 = 8 所以結束二分搜

參考解答

d732
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <iostream>
using namespace std;

void solve(int *data, int n, int qq) {
    int left = 0;
    int right = n;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (data[mid] < qq) {
            left = mid + 1;
        } else if (data[mid] > qq) {
            right = mid - 1;
        } else {
            cout << mid + 1 << "\n";
            return;
        }
    }
    cout << 0 << "\n";
    return;
}

int main() {
    int n, k;
    cin >> n >> k;
    int data[n], q[k];
    for (int i = 0; i < n; i++) {
        cin >> data[i];
    }
    for (int i = 0; i < k; i++) {
        cin >> q[i];
    }
    for (int i = 0; i < k; i++) {
        solve(data, n, q[i]);
    }
    return 0;
}

發布於 更新於 分類於 ， 文章字數： 366 所需閱讀時間 ≈ 1 分鐘

題目連結

f832: 隕石 (Meteorite)

我的想法

貪婪演算法（Greedy），每一步都使用最佳的解，從而導致希望結果也是最佳的解。

就範例二而言

1
2
3
4 4
1 8 5 7
1 9 6 6

機器之間或隕石之間，又或者是機器與隕石間無任關聯，我們將他們排序

1
2
1 5 7 8
1 6 6 9

當機器可抓取的最大能力是 9，先找到能符合小於 9 的對大數字是 8（此時就是這一步的最佳解），sum += 8，並且換另一台機器。
當機器可抓取的最大能力是 6，先找到能符合小於 6 的對大數字是 5（此時就是這一步的最佳解），sum += 5，並且換另一台機器。
當機器可抓取的最大能力是 6，先找到能符合小於 6 的對大數字是 1（此時就是這一步的最佳解），sum += 1，並且換另一台機器。
沒石頭可以抓，輸出 sum，結束程式。

:::warning
總和會大於 2^32，故 sum 要使用 long long
:::

參考解答

f832
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <algorithm>
#include <iostream>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    long long rock[n], robot[m];
    for (int i = 0; i < n; i++) cin >> rock[i];
    for (int i = 0; i < m; i++) cin >> robot[i];
    sort(rock, rock + n);
    sort(robot, robot + m);

    long long sum = 0;
    int index_bot = m - 1;
    for (int i = n - 1; i >= 0 && index_bot >= 0; i--) {
        if (robot[index_bot] >= rock[i]) {
            sum += rock[i];
            index_bot--;
        }
    }
    cout << sum << "\n";
    return 0;
}

發布於 更新於 分類於 ， 文章字數： 182 所需閱讀時間 ≈ 1 分鐘

題目連結

a290: 新手訓練系列 ~ 圖論

我的想法

先將圖建好，再用 BFS 慢慢走訪，從訪問的起點開始，走過的地方都標記為 true ，若最後終點是 true，輸出 Yes!!!，否則 No!!!

參考解答

a290
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

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

    int N, M;
    while (cin >> N >> M) {
        vector<int> d[N];
        queue<int> q;
        bool check[800] = {false};
        for (int i = 0; i < M; i++) {
            int a, b;
            cin >> a >> b;
            a--;
            b--;
            d[a].push_back(b);
        }
        // 將能走的路徑都設為 true
        int A, B;
        cin >> A >> B;
        A--;
        B--;
        q.push(A);
        check[A] = true;
        while (!q.empty()) {
            int temp = q.front();
            q.pop();
            for (auto &i : d[temp]) {
                if (!check[i]) {
                    check[i] = true;
                    q.push(i);
                }
            }
        }
        // 訪問 B 點是否能走到
        if (check[B]) {
            cout << "Yes!!!\n";
        } else {
            cout << "No!!!\n";
        }
    }
    return 0;
}

發布於 更新於 分類於 ， 文章字數： 1.2k 所需閱讀時間 ≈ 4 分鐘

基本介紹

vector 是一個可以改變大小的容器，可以說是升級版的陣列，vector 更能夠高效地對記憶體進行管理及動態增長。

如何宣告

先引入標頭檔 #include <vector>

基礎宣告

基礎宣告範例
1
2
3
4
5
6
7
8
#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> vec;
    return 0;
}

vec 為存取 int 型別的 vector，且裡面沒有元素，所以 size 為 0。

設定初始值

我們可以使用其內建函式把元素丟進去

設定初始值範例
1
2
3
4
vecotr<int> vec;
vec.push_back(1);  // vec = {1};
vec.push_back(3);  // vec = {1, 3};
vec.push_back(5);  // vec = {1, 3, 5};

也可以直接寫成一行

設定初始值範例
1
vector<int> vec = {1, 3, 5};

或者

設定初始值範例
1
vector<int> vec({1, 3, 5});

若想要複製一份相同的 vector，可以這樣做

1
2
3
4
vector<int> vec_1 = {1, 3, 5};
vecotr<int> vec_2 = vec_1;
// 當然這句也可以寫成
vector<int> vec_2(vec_1);

也可以複製一份陣列

1
2
int data[3] = {1, 3, 5};
vector<int> vec(data, data+3);

還可以複製其中一段就好

1
2
vector<int> vec_1 = {1, 3, 5, 7, 9};
vector<int> vec_2(vec_1.begin() + 2, vec_1.end() - 1);  // vec_2 = {5, 7};

陣列也可以複製其中一段

1
2
int data[5] = {1, 3, 5, 7, 9};
vector<int> vec(data+2, data+4); // vec = {5, 7};

基礎使用

下方為 vector 可用的函式，有誤還請多指教

vector 函式 功能
begin(), end(), cbegin(), cend() 提供正向跌代器
rbegin(), rend(), crbegin(), crend() 提供反向跌代器
size() 返回 vector 大小
max_size() 返回 vector 最大大小（因為 vector 的大小是隨者元素的多寡而增加，所以數字極大）
resize() 配置 vector 大小，且補滿 0
capacity() 返回目前 vector 配置大小
empty() 判斷 vector 是否為空
reserve() 配置 vector 大小
shrink_to_fit() 釋放 vector 未使用的空間
at(), operator[] 取得元素
front() 返回第一個元素
back() 返回最後一個元素
data() 返回元素的指標
assign() 配置 (0~n) 的數值
push_back() 先複製一份要 push_back 的元素，再貼在 vector 後面
pop_back() 刪除最後一個元素
insert() 插入元素
erase() 刪除一個或一段元素
clear() 清空 vector 內的元素
swap() 交換兩個 vector 元素

查看更多可參考 cplusplus 官網

基礎操作

正向遍歷

1
2
3
4
vector<int> vec({1, 3, 5, 6});
for (auto it = vec.begin(); it < vec.end(); it++) {
    cout << *it << "\n";
}

反向遍歷

1
2
3
4
vector<int> vec({1, 3, 5, 6});
for (auto it = vec.rbegin(); it < vec.rend(); it++) {
    cout << *it << "\n";
}

size() 與 max_size() 差異

1
2
3
vector<int> vec({1, 3, 5, 6});
cout << "size: " << vec.size() << "\n";
cout << "max_size: " << vec.max_size() << "\n";
1
2
3
輸出：
size: 4
max_size: 4611686018427387903

size() 與 capacity() 差異

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
vector<int> vec({1});
cout << "vec size: " << vec.size() << "\n";
cout << "vec capacity: " << vec.capacity() << "\n";
vec.push_back(10);
cout << "vec size: " << vec.size() << "\n";
cout << "vec capacity: " << vec.capacity() << "\n";
vec.push_back(10);
cout << "vec size: " << vec.size() << "\n";
cout << "vec capacity: " << vec.capacity() << "\n";
vec.push_back(10);
cout << "vec size: " << vec.size() << "\n";
cout << "vec capacity: " << vec.capacity() << "\n";
vec.push_back(10);
cout << "vec size: " << vec.size() << "\n";
cout << "vec capacity: " << vec.capacity() << "\n";
vec.push_back(10);
cout << "vec size: " << vec.size() << "\n";
cout << "vec capacity: " << vec.capacity() << "\n";
vec.push_back(10);
cout << "vec size: " << vec.size() << "\n";
cout << "vec capacity: " << vec.capacity() << "\n";
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
輸出：
vec size: 1
vec capacity: 1
vec size: 2
vec capacity: 2
vec size: 3
vec capacity: 4
vec size: 4
vec capacity: 4
vec size: 5
vec capacity: 8
vec size: 6
vec capacity: 8
vec size: 7
vec capacity: 8

可以發現，使用 size() 時，元素個數及為 size，而使用 capacity() 時，回傳目前 vector 預先給予的空間大小，且如果超過預先給予的空間大小，空間會再給予 兩倍 的空間。

reserve() 預先配置 vector 如器大小

若想要預先給予固定的空間大小，可以使用 reserve()。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
vector<int> vec({1});
vec.reserve(3);
cout << "vec size: " << vec.size() << "\n";
cout << "vec capacity: " << vec.capacity() << "\n";
vec.push_back(10);
cout << "vec size: " << vec.size() << "\n";
cout << "vec capacity: " << vec.capacity() << "\n";
vec.push_back(10);
cout << "vec size: " << vec.size() << "\n";
cout << "vec capacity: " << vec.capacity() << "\n";
vec.push_back(10);
cout << "vec size: " << vec.size() << "\n";
cout << "vec capacity: " << vec.capacity() << "\n";
vec.push_back(10);
1
2
3
4
5
6
7
8
9
輸出：
vec size: 1
vec capacity: 3
vec size: 2
vec capacity: 3
vec size: 3
vec capacity: 3
vec size: 4
vec capacity: 6

可以再次發現，若元素長度大於預先設置的空間大小，capacity() 依舊以 兩倍的方式增大 。

使用 shrink_to_fit() 將未使用的空間釋放

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
vector<int> vec;
// 使用 shrink 前
cout << "---使用 shrink 前---\n";
vec.reserve(10);
cout << "size: " << vec.size() << "\n";
cout << "capacity: " << vec.capacity() << "\n";
vec.push_back(1);
vec.push_back(1);
cout << "size: " << vec.size() << "\n";
cout << "capacity: " << vec.capacity() << "\n";
// 使用 shrink 後
cout << "---使用 shrink 後---\n";
vec.shrink_to_fit();
cout << "size: " << vec.size() << "\n";
cout << "capacity: " << vec.capacity() << "\n";
1
2
3
4
5
6
7
8
9
輸出：
---使用 shrink 前---
size: 0
capacity: 10
size: 2
capacity: 10
---使用 shrink 後---
size: 2
capacity: 2

resize() 配置大小，並將新的空間設為 0

1
2
3
4
5
vector<int> vec;
vec.resize(10);
for (auto &v : vec) {
    cout << v << " ";
}
1
2
輸出：
0 0 0 0 0 0 0 0 0 0

可以發現原本空的 vector 使用 size() 後，預設為 0，但如果不想預設為 0，可以這樣做。

1
2
3
4
5
vector<int> vec;
vec.resize(10, 5);
for (auto &v : vec) {
    cout << v << " ";
}
1
2
輸出：
5 5 5 5 5 5 5 5 5 5

課堂小考

對空的整數型態 vector 使用 resize(10.5, 3.3) 後，capacity() 變為多少，且元素設定為多少。
A. capacity: 11，且元素皆為 4
B. capacity: 11，且元素皆為 3
C. capacity: 10，且元素皆為 3
D. capacity: 10，且元素皆為 4
E. Run Time Error

解答

選項 C

發布於 更新於 分類於 ， 文章字數： 456 所需閱讀時間 ≈ 2 分鐘

基本介紹

當我們需要存取一堆數據或資料時，總不能直接建立千個或上萬個變數吧！若這些數據具有相關性、型態一樣，可以使用 Array 來存取。陣列具有連續的記憶體位址，所以我們可以從頭走到尾來讀取 Array 中的數據。既可以減少變數的命名，還可以讓程式變得精簡、提高可讀性。

如何宣告

先引入標頭檔 #include <array>

基礎宣告

基礎宣告範例
1
array<int, 10> arr;

從上方範例可知 arr 是一個長度為 10 的整數陣列

在任何程式語言裡，陣列的第一項編號必為 0（編號我們通常稱之 index 索引）。所以若有一個長度為 10 的陣列，內容物的索引範圍為 0~9。

設定初始值

設定初始值範例
1
2
arr<int, 5> arr_A{2, 5, 8, 3, 1};
arr<int, 5> arr_B{};  // 表示初始化 arr_B 元素皆為 0

注意！若陣列未做初始值，其中元素可能為亂數。

基礎使用

array 函式 功能
begin(), end(), cbegin(), cend() 提供正向跌代器
rbegin(), rend(), crbegin(), crend() 提供反向跌代器
size() 返回陣列大小
max_size() 返回陣列最大大小（由於 array 為固定序列，故返回值與 size() 一樣）
at(), operator[] 取得元素
front() 返回第一個元素
back() 返回最後一個元素
data() 返回元素的指標
fill() 填滿陣列
swap() 交換兩個陣列元素

查看更多可參考 cplusplus 官網

各種遍歷

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 正向遍歷
for (int i = 0; i < 10; i++) {
    cout << data[i] << "\n";
}
for (auto i : data) {
    cout << i << "\n";
}
for (auto iter = data.begin(); iter != data.end(); ++iter) {
    cout << *iter << "\n";
}
// 反向遍歷
for (int i = 9; i <= 0; i--) {
    cout << data[i] << "\n";
}
for (auto iter = data.rbegin(); iter != data.rend(); ++iter) {
    cout << *iter << "\n";
}