README.md

APCS 2020/07/04 by cthbst

pA

• 用 std::map 或是一個範圍至少有 100 的陣列，記錄每一種數字的出現次數
• time: O(100 * T + length)

pB

• 用 struct 儲存每一面目前的點數
• 每次修改操作直接呼叫對應的修改函式
• time: O(n + m)

pC

• 對於每個查詢 qi, 先把 qi mod 環狀陣列的總和，最後用 binary search 找到下一個開始的位置
• time: O(n + m log n)

pD

• 每一個位數是獨立的，因此可以把 1 個字串長度為 m 的問題想成 m 個字串長度都是 1 的問題
• 使用樹形動態規劃(Dynamic Programming)
  • 定義狀態 dp(u, i) = 以 u 為根的子樹中，根的字母是 i 的答案
  • 狀態轉移 dp(u, i) = \sum{ dp(v, j) + (i!=j) : v 是 u 的小孩 }
• time: O(n * m * 26 * 26)

pA.cpp

#include <bits/stdc++.h>
using namespace std;

int solve(int a, int b) {
    int cnt[105] = {0};
    int x;
    while (cin >> x) {
        if (x == 0) {
            break;
        } else if (x > 0) {
            cnt[x]++;
        } else if (x < 0) {
            cnt[-x]--;
        }
    }
    if (cnt[a] > 0 && cnt[b] > 0) {
        return 1;
    } else {
        return 0;
    }
}

int main() {
    int a, b;
    cin >> a >> b;

    int T;
    cin >> T;
    int ans = 0;
    for (int cs = 1; cs <= T; cs++) {
        ans += solve(a, b);
    }
    cout << ans;
}

pB.cpp

#include <bits/stdc++.h>
using namespace std;

struct Dice {
    vector<int> f;  // face
    Dice() {
        //     [4]
        // [3] [0] [1] [2]
        //     [5]
        f = {1, 2, 6, 5, 3, 4};
    }
    void rotateToFront() {
        //     [4]                 [2]
        // [3] [0] [1] [2] =>  [3] [4] [1] [5]
        //     [5]                 [0]
        f = {f[4], f[1], f[5], f[3], f[2], f[0]};
    }
    void rotateToRight() {
        //     [4]                 [4]
        // [3] [0] [1] [2] =>  [2] [3] [0] [1]
        //     [5]                 [5]
        f = {f[3], f[0], f[1], f[2], f[4], f[5]};
    }
};

int main() {
    int n, m;
    cin >> n >> m;
    vector<Dice> dice(n + 1);
    for (int cs = 1; cs <= m; cs++) {
        int a, b;
        cin >> a >> b;
        if (b == -1) {
            dice[a].rotateToFront();
        } else if (b == -2) {
            dice[a].rotateToRight();
        } else {
            swap(dice[a], dice[b]);
        }
    }
    for (int i = 1; i <= n; i++) {
        cout << dice[i].f[0] << (i == n ? '\n' : ' ');
    }
}

pC.cpp

#include <bits/stdc++.h>
using namespace std;

int n, m;
vector<long long> a, S;

void init() {
    cin >> n >> m;
    a.resize(2 * n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        a[i + n] = a[i];
    }
    S.resize(2 * n);
    long long sum = 0;
    for (int i = 0; i < 2 * n; i++) {
        sum += a[i];
        S[i] = sum;
    }
}

int next_pos(int pos, long long target) {
    target += S[pos] - a[pos];
    int L = pos;
    int R = pos + n;
    pos = lower_bound(S.begin() + L, S.begin() + R, target) - S.begin();
    return (pos + 1) % n;
}

int main() {
    init();
    int pos = 0;
    for (int cs = 1; cs <= m; cs++) {
        int target;
        cin >> target;
        pos = next_pos(pos, target);
    }
    cout << pos << endl;
}

pD.cpp

#include <bits/stdc++.h>
using namespace std;

const int INF = 1e7;

int n, m;
vector<vector<int>> G;
vector<string> strs;
vector<char> c;
// dp(u, i) : 以 u 為根的子樹, 且根的字母為 i 的最小漢明距離
vector<array<int, 26>> dp;

void solve(int u, int par) {
    fill(dp[u].begin(), dp[u].end(), INF);
    for (int i = 0; i < 26; i++) {
        if (c[u] != '@' && c[u] != 'A' + i) continue;
        dp[u][i] = 0;
    }
    for (int vi = 0; vi < (int)G[u].size(); vi++) {
        int v = G[u][vi];
        if (v == par) continue;
        solve(v, u);
        for (int i = 0; i < 26; i++) {
            if (c[u] != '@' && c[u] != 'A' + i) continue;
            int mi = INF;
            for (int j = 0; j < 26; j++) {
                mi = min(mi, dp[v][j] + (i != j));
            }
            dp[u][i] += mi;
        }
    }
}

int main() {
    cin >> n >> m;
    G.resize(n);
    strs.resize(n);
    for (int i = 0; i < n; i++) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        G[u].push_back(v);
        G[v].push_back(u);
        cin >> strs[i];
    }
    int ans = 0;
    c.resize(n);
    for (int d = 0; d < m; d++) {
        for (int i = 0; i < n; i++) {
            c[i] = strs[i][d];
        }
        dp = vector<array<int, 26>>(n);
        solve(0, 0);
        ans += *min_element(dp[0].begin(), dp[0].end());
    }
    cout << ans << endl;
}

/*
2 3
1 1 ABB
1 2 A@@
*/