APCS 2020-07 題解

💡Hint：程式碼省略最前面巨集部分，可以在 About 頁面找到。

p1. 購物車

Solution

對於每個客人都去紀錄商品 $a$ 跟 $b$ 的增減狀況就好，其他商品可以直接丟掉不管。

AC code

signed main() {
    hyper;
    int a, b, n, cnt = 0;
    cin >> a >> b >> n;
    rep(i,0,n) {
        int x, af = 0, bf = 0;
        while(cin >> x && x != 0) {
            if(abs(x) == a) af += x;
            else if(abs(x) == b) bf += x;
        }
        if(af > 0 && bf > 0) ++cnt;
    }
    cout << cnt << '\n';
}

p2. 骰子

題目連結

Solution

開個 struct 直接模擬就好。

AC code

struct Dice {
    int f, b, l, r, u, d;
    Dice(): f(4), b(3), l(5), r(2), u(1), d(6) {}
    void rollF() { int t=f; f=u; u=b; b=d; d=t; }
    void rollR() { int t=r; r=u; u=l; l=d; d=t; }
};

signed main() {
    hyper;
    int n, m, x, y;
    Dice a[21];
    cin >> n >> m;
    while(m--) {
        cin >> x >> y;
        if(y == -1) a[x].rollF();
        else if(y == -2) a[x].rollR();
        else swap(a[x], a[y]);
    }
    rep1(i,1,n) cout << a[i].u << ' ';
    cout << '\n';
}

p3. 圓環出口

題目連結

Solution

這題要快速的找到下一個停留的位置，所以直接模擬肯定會 TLE。下一個停留的位置其實就是要從目前位置開始的前綴和找 $\ge q$ 的最小值，直接做二分搜就可以了。另外，因為他是環狀的，一種簡單的處理方式是把陣列複製一份接在後面，變成總長度 $2n$ 的新陣列，再對這個新陣列做一樣的事情，這樣可以確保在 wrap 回 index 0 的時候還是可以處理好連續的資訊（前綴和）。時間複雜度 $O(m \log n)$

AC code

int search(int a[], int l, int r, int t, int pos) {
    while(l < r) {
        int m = (l+r)/2;
        if(a[m]-a[pos-1] < t) l = m+1;
        else r = m;
    }
    return l;
}

signed main() {
    hyper;
    int n, m, p[MN];
    cin >> n >> m;
    rep(i,0,n) cin >> p[i];
    
    int ps[MN*2]; ps[0] = 0;
    rep1(i,1,n) ps[i] = ps[i-1] + p[i-1];
    rep1(i,1,n) ps[n+i] = ps[n+i-1] + p[i-1];
    
    int pos = 1;
    while(m--) {
        int q; cin >> q;
        int r = search(ps, pos, n*2, q, pos);
        pos = r % n + 1;
    }
    cout << pos-1 << '\n';
}

p4. 病毒演化

題目連結

Solution

這題看起來一臉樹上 dp，想一下會發現字串的每個位置其實是獨立的，所以可以分開做，只要一次處理一個字元。定義狀態 $dp(i, j)$ 表示節點 $i$ 是字元 $j \in \{A, U, C, G\}$ 時，以 $i$ 為根的子樹的答案。轉移的時候固定 $j$，從每個小孩四個可能字元挑最小的加總（為了方便，如果字元是固定的就把其他不可能的字元答案設成 $\infty$ 這樣就一定不會選到）。時間複雜度 $O(mn)$。

AC code

int dp[MN][4], mpn[128];
vector<int> e[MN];
string s[MN];

void dfs(int u, int t) {
    rep(i,0,4) dp[u][i] = 0;
    if(s[u][t] != '@') {
        rep(i,0,4) {
            if(mpn[s[u][t]] == i) continue;
            dp[u][i] = INF;
        }
    }
    if(e[u].size() == 0) return;
    for(int v: e[u]) {
        dfs(v, t);
        rep(i,0,4) {
            int mn = INF;
            rep(j,0,4) mn = min(mn, dp[v][j] + (i!=j));
            dp[u][i] += mn;
        }
    }
}

signed main() {
    hyper;
    mpn['A'] = 0, mpn['U'] = 1, mpn['C'] = 2, mpn['G'] = 3;
    int n, m, u, v, root, ans = 0;
    cin >> n >> m;
    rep(i,0,n) {
        cin >> u >> v;
        if(u == v) root = u;
        else e[v].push_back(u);
        cin >> s[u];
    }
    rep(i,0,m) {
        dfs(root, i);
        ans += min({dp[root][0], dp[root][1], dp[root][2], dp[root][3]});
    }
    cout << ans << '\n';
}