Kuo's Blog

競程筆記｜個人網站

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

題目連結

j605. 1. 程式考試

我的想法

APCS 第一題純水題

參考解答

j605
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
#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;

    int data[n][2];
    int max_num = -1;
    int max_num_time = -1;
    int error_times = 0;
    for (int i = 0; i < n; i++) {
        cin >> data[i][0] >> data[i][1];
        if (data[i][1] > max_num) {
            max_num_time = data[i][0];
            max_num = data[i][1];
        }
        if (data[i][1] == -1) {
            error_times++;
        }
    }

    int total = max_num - n - (error_times * 2);

    cout << ((total < 0) ? 0 : total) << " " << max_num_time << endl;

    return 0;
}

發布於 更新於 分類於 ， 文章字數： 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;
}