[APCS] 20200704 程式實作題

這次 $APCS$ 的實作題，

難度約如下：

$P1$	$P2$	$P3$	$P4$
★	★	★★★	★★★★★

$P1, \ P2$ 十分簡單，

$P3$ 看似簡單，

但爆力解只有 $20\%$ 的分數，

$P4$ 題敘很長，

需要的演算法也很難想。

< $P1.$ 購物分析 >

題意：

第一行有兩個數 $a, \ b$，

代表兩個物品。

第二行有一個數 $T$，

代表以下有 $T$ 行資料。

每行資料輸入有多個數 $X_i$ (以 $0$ 結尾)，

若 $X_i$ 為正數則放入購物籃，

反之則拿出購物籃。

判斷 $T$ 行中有多少行皆放入 $a, \ b$ 兩物品。

範圍：

$1 ≤ a, \ b, \ X_i ≤ 100, \ 1 ≤ T ≤ 100$。

範例輸入 $1.$：

1 8
5
1 8 0
5 6 0
2 7 0
8 1 0
33 22 0

範例輸出 $1.$：

2

程式碼參考：

C++：

#include <bits/stdc++.h>
#define _ ios::sync_with_stdio(false), cin.tie(nullptr);
#define endl '\n'
using namespace std;
 
int main() { _
    int a, b, T, x, ans = 0;
    cin >> a >> b >> T;
    while (T--) {
        map<int, int> mp;
        while (cin >> x, x) {
            if (x > 0)
                mp[x] += 1;
            else
                mp[-x] -= 1;
        }
        if (mp[a] > 0 && mp[b] > 0)
            ans += 1;
    }
    cout << ans << endl;
}

< $P2.$ 骰子 >

題意：

第一行有兩個數 $n, \ m$，

代表有 $n$ 個骰子和 $m$ 筆操作。

每個骰子上、下、左、右、前、後依序為 $1, \ 6, \ 5, \ 2, \ 4, \ 3$。

接著有 $m$ 行操作，

每行有兩個數 $a, \ b$，

其中 $1 ≤ a ≤ n, \ 1 ≤ b ≤ n$ 或 $b = -1$ 或 $b = -2$，

若 $b > 0$ 則 $a, \ b$ 兩顆骰子位置交換。

若 $b = -1$ 則骰子 $a$ 向前翻轉。

若 $b = -2$ 則骰子 $a$ 向右翻轉。

範圍：

$1 ≤ n ≤ 100, 1 ≤ m ≤ 100$。

範例輸入 1.：

1 2
1 -2
1 -1

範例輸出 1.：

3

範例輸入 2.：

3 3
2 -1
3 -2
3 1

範例輸出 2.：

5 3 1

程式碼參考：

C++：

#include <bits/stdc++.h>
#define _ ios::sync_with_stdio(false), cin.tie(nullptr);
#define endl '\n'
using namespace std;
 
struct s {
    int up, down, left, right, front, back;
 
    void ffn() {
        // front_rotate function
        // 向前翻轉
        int tmp;
        front = up, up = back, back = down, down = tmp;
    }
 
    void rfn() {
        // right_rotate function
        // 向右翻轉
        int tmp;
        up = left, left = down, down = right, right = tmp;
    }
 
    s(): up(1), down(6), left(5), right(2), front(4), back(3) {}
};
 
int main() { _
    int n, m, a, b;
    cin >> n >> m;
    vector<s> v(n + 1);
    while (m--) {
        cin >> a >> b;
        if (b > 0)
            swap(v[a], v[b]);
        else if (b == -1)
            v[a].ffn();
        else
            v[a].rfn();
    }
    for (int i = 1; i <= n; i++)
        cout << v[i].up << " \n"[i == n];
}

< $P3.$ 圓環迷宮 >

題意：

第一行有兩個數 $n, \ m$，

代表一個環狀迷宮有 $n$ 個房間(編號 $0, \ 1, \ 2, \ ..., \ n - 1)$，

接下來一行有 $n$ 個數，

代表著 $i$ 號房間有的點數 $P_i$。

接著一行有 $m$ 個數，

代表著第 $i$ 把鑰匙需要的點數 $Q_i$。

環狀迷宮走的順序為 $0, \ 1, \ 2, \ ..., \ n - 1, \ 0, \ 1, \ 2, \ ...$。

每次離開 $i$ 號房可以得到 $P_i$ 點數，

當點數達到 $Q_i$ 時即可兌換鑰匙(需要依序蒐集 $Q_0, \ Q_1, \ Q_2, \ ...$)，

兌換時清會清空所有點數。

當蒐集完 $m$ 把鑰匙時，

試問準備進入哪一號房間。

範圍：

$1 ≤ n ≤ 2 × 10^5, 1 ≤ m ≤ 2 × 10^4$，

所有點數和不超過 $10^9$。

範例輸入 1.：

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

範例輸出 1.：

3

演算法：

• $Prefix \ Sum$(前綴和)。
• $Binary \ Search$(二分搜尋法)。

解題策略：

用前綴和記錄點數累積表，

再利用二分搜尋法找到該個點數，

直接跳到下個點數的編號。

< $P4.$ 病毒傳播 >

題意：

第一行有兩個數 $n, \ m$，

有 $n$ 條病毒長度為 $m$ 的 $RNA$。

接著有 $n$ 行，

每行有 $i, \ j, \ S_i$，

代表自身編號($1$ ~ $n$)、親代編號、$RNA$ 序列。

$RNA$ 序列中有 $A, \ U, \ C, \ G, \ @$，

$@$ 可為 $A, \ U, \ C, \ G$ 其中一個，

但每個 $RNA$ 序列的 $@$ 不一定要一樣。

差距定義為兩相鄰節點之基因序列不同位置數量，

試問所有的親代和子代最小的差距總和。

範例輸入 1.：

2 3
1 1 AAC
2 1 A@@

範例輸出 1.：

0

範例輸入 2.：

6 1
1 1 @
2 1 @
3 1 C
4 1 C
5 2 A
6 2 A

範例輸出 2.：

1

範圍：

$1 ≤ n ≤ 1000, 1 ≤ m ≤ 80$。

演算法：

• $DFS$(深度優先搜尋)。
• $DP$(動態規劃)。

以上，

若有更好的想法歡迎提出哦！