APCS 2021-01 題解

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

p1. 購買力

Solution

把價格 sort 然後照題目條件判斷一下。

AC code

signed main() {
    hyper;
    int n, d, a[3];
    int cnt = 0, sum = 0;
    cin >> n >> d;
    rep(i,0,n) {
        rep(j,0,3) cin >> a[j];
        sort(a, a+3);
        if(a[2] - a[0] >= d) {
            ++cnt;
            sum += (a[0] + a[1] + a[2]) / 3;
        }
    }
    cout << cnt << ' ' << sum << '\n';
}

p2. 流量

題目連結

Solution

對於每個方案先開一個陣列把流量算好，然後算價格取最小值。

AC code

signed main() {
    hyper;
    int n, m, k;
    int q[MN][MN], c[MN];
    cin >> n >> m >> k;
    rep(i,0,n) rep(j,0,m) cin >> q[i][j];
    int mn = INF;
    rep(x,0,k) {
        rep(i,0,n) cin >> c[i];
        int f[MN][MN];
        rr(f,0);
        rep(i,0,n) rep(j,0,m) f[c[i]][j] += q[i][j];
        int sum = 0;
        rep(i,0,m) rep(j,0,m) {
            if(i == j) sum += f[i][j];
            else sum += min(f[i][j], 1000) * 3 + max(f[i][j] - 1000, 0) * 2;
        }
        mn = min(mn, sum);
    }
    cout << mn << '\n';
}

p3. 切割費用

題目連結

Solution

感覺是要考平衡樹，但 C++ 太方便了，直接用 set 的功能就可以做到。對切割的順序排序完從頭掃一次，維護一個 set 是之前切過的所有點，再把目前要切的點丟進 set 並用 set.find() 找到位置，他的前後位置就是要切的棒子的端點。時間複雜度 $O(n \log n)$。

AC code

signed main() {
    hyper;
    int n, L;
    cin >> n >> L;
    vi a(n);
    rep(i,0,n) {
        int x, y;
        cin >> x >> y;
        a[y-1] = x;
    }

    int ans = 0;
    set<int> cut;
    cut.insert(0);
    cut.insert(L);
    rep(i,0,n) {
        cut.insert(a[i]);
        auto it = cut.find(a[i]);
        int l = *prev(it), r = *next(it);
        ans += r-l;
    }
    cout << ans << '\n';
}

p4. 低地距離

題目連結

Solution

老題目了，先對 x 再對 y 排序就變成 y 座標的 LIS 問題了。dp 解時間複雜度是 $O(n^2)$，用二分搜可以變成 $O(n \log n)$ 才會過。注意這題是非嚴格遞增的 LIS，沒注意吃了好幾個 WA QQ。

AC code

signed main() {
    hyper;
    int n;
    cin >> n;
    vector<pii> a(n);
    rep(i,0,n) cin >> a[i].fi >> a[i].se;
    sort(a.begin(), a.end());

    vector<int> lis;
    for(auto [x, y]: a) {
        if(lis.empty() || y >= lis.back()) lis.push_back(y);
        else *upper_bound(lis.begin(), lis.end(), y) = y;
    }
    cout << lis.size() << '\n';
}