APCS 2024 1 月場

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

說明

第 4 題還在研究~

1. 遊戲選角

展開程式碼

 
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
#include <bits/stdc++.h>
#define ouo ios_base::sync_with_stdio(false), cin.tie(0)
#define ll long long
#define db double
using namespace std;

int n;

struct p {
    int a;
    int d;
    int ability;
};

bool cmp(p a, p b) {
    return a.ability > b.ability;
}

int main() {
    ouo;

    cin >> n;
    p player[n];
    for (int i = 0; i < n; i++) {
        cin >> player[i].a >> player[i].d;
        player[i].ability = player[i].a * player[i].a + player[i].d * player[i].d;
    }
    sort(player, player + n, cmp);
    cout << player[1].a << " " << player[1].d;

    return 0;
}

2. 蜜蜂觀察

展開程式碼

 
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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <bits/stdc++.h>
#define ouo ios_base::sync_with_stdio(false), cin.tie(0)
#define ll long long
#define db double
using namespace std;

int m, n, k;
int amount = 0;

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

    string arr[m];
    for (int i = 0; i < m; i++) {
        cin >> arr[i];
    }

    int p_x = m - 1, p_y = 0;

    bool alpha[2][26] = {false};
    for (int t = 0; t < k; t++) {
        int d = -1;
        cin >> d;
        int d_x = 0, d_y = 0;
        switch (d) {
            case 0:
                d_x -= 1;
                break;
            case 1:
                d_y += 1;
                break;
            case 2:
                d_x += 1;
                d_y += 1;
                break;
            case 3:
                d_x += 1;
                break;
            case 4:
                d_y -= 1;
                break;
            case 5:
                d_x -= 1;
                d_y -= 1;
                break;
            default:
                break;
        }
        if (p_x + d_x < m && p_x + d_x >= 0 && p_y + d_y < n && p_y + d_y >= 0) {
            p_x += d_x;
            p_y += d_y;
        }
        cout << arr[p_x][p_y];

        if (arr[p_x][p_y] >= 'a' && arr[p_x][p_y] <= 'z') {
            alpha[0][arr[p_x][p_y] - 'a'] = true;
        } else if (arr[p_x][p_y] >= 'A' && arr[p_x][p_y] <= 'Z') {
            alpha[1][arr[p_x][p_y] - 'A'] = true;
        }
    }
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 26; j++) {
            if (alpha[i][j] == true) amount++;
        }
    }
    cout << "\n"
         << amount;
    return 0;
}

3. 邏輯電路

參考 @Youtong0826 的思路，原本只有做 DFS 的部分但會超時，所以改成用 DP 紀錄已經跑過的邏輯閘。

展開程式碼

 
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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include <bits/stdc++.h>
#define ouo ios_base::sync_with_stdio(false), cin.tie(0)
#define ll long long
#define db double
using namespace std;

struct node {
    int type;  // 1: AND, 2: OR, 3: XOR, 4: NOT
    int result;
};

int p, q, r, m;
vector<node> vc;
vector<bool> visited;
vector<int> ans;
vector<vector<int>> g;
vector<pair<int, int>> dp;

// pair<int, int> = {result, delay}
pair<int, int> dfs(int idx) {
    if (idx <= p) {
        visited[idx] = true;
        return dp[idx] = {vc[idx].result, 0};
    }

    // 輸出節點必只有一個輸入端
    if (idx > p + q && idx <= p + q + r) return dfs(g[idx][0]);

    if (visited[idx]) return dp[idx];

    // do
    visited[idx] = true;
    auto a = dfs(g[idx][0]);  // 先取得第一個輸入端

    if (vc[idx].type == 4) return dp[idx] = {!a.first, a.second + 1};

    auto b = dfs(g[idx][1]);

    if (vc[idx].type == 1) return dp[idx] = {(a.first && b.first), max(a.second, b.second) + 1};
    if (vc[idx].type == 2) return dp[idx] = {(a.first || b.first), max(a.second, b.second) + 1};
    if (vc[idx].type == 3) return dp[idx] = {(a.first != b.first), max(a.second, b.second) + 1};
    return {vc[idx].result, 0};
}

int main() {
    ouo;
    cin >> p >> q >> r >> m;

    // init
    vc.resize(p + q + r + 1);
    visited.assign(p + q + r + 1, false);
    g.assign(p + q + r + 1, {});
    dp.resize(p + q + r + 1);
    for (int i = 1; i <= p + q; i++) {
        vc[i].result = 0;
        vc[i].type = -1;
    }

    // in
    for (int i = 1; i <= p; i++) {
        cin >> vc[i].result;
    }

    // logic
    for (int i = 1; i <= q; i++) {
        cin >> vc[p + i].type;
    }

    // graph
    for (int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;
        g[b].push_back(a);
    }

    int delay = -1;
    for (int i = p + q + 1; i <= p + q + r; i++) {
        auto f = dfs(i);
        ans.push_back(f.first);
        delay = max(delay, f.second);
    }

    cout << delay << "\n";
    for (auto i : ans) cout << i << " ";
}