# 2025/06/15 APCS

## 前言

最後一次舊制APCS，因為我APCS還在 4 4
所以想說再來考一下 (上次沒蹭到觀念5級 真的too bad)

## 題目

### pA. [跳柵遊戲](https://zerojudge.tw/ShowProblem?problemid=q836)

題目大概是在講
一開始每次可以走 $N$ 步
假如你走到一個整數點為 $A$ 的倍數的點，那麼你的可以走的步數會 $-B$
假如你走到一個整數點為 $C$ 的倍數的點，那麼你的可以走的步數會 $-D$
問你最後會停在哪個點

解法大概是
`while` 炸過去，我猜複雜度是好的

#include <iostream>
using namespace std;
int main() {
    int n; cin >> n;
    int a, b, c, d; cin >> a >> b >> c >> d;
    int now = 0;
    while(n > 0) {
        now += n;
        if(now%a == 0) n -= b;
        if(now%c == 0) n -= d;
    }
    cout << now << '\n';
}

### pB. [轉盤得分](https://zerojudge.tw/ShowProblem?problemid=q837)

題目講
你有 $M$ 個有 $N$ 個刻度的轉盤
每個轉盤上的每個刻度有各自的字母
今天要你模擬轉轉盤，且過程中會獲得分數
分數就是當你轉完 $M$ 個轉盤時，你會依照每個 $1 \sim N$ 的刻度上字母出現最大頻率來給分

反正就是實作題，但取模要取好
阿不可能真的對字串轉轉轉，所以用一個陣列 `it` 紀錄每個轉盤目前的開始刻度

#include <iostream>
#include <vector>
using namespace std;
int main() {
    int m, n, k; cin >> m >> n >> k;
    vector<string> v(m);
    for(int i = 0; i < m; i++) cin >> v[i];
    vector<int> it(m);
    int ans = 0;
    while(k--) {
        for(int i = 0; i < m; i++) {
            int a; cin >> a;
            it[i] = ((it[i] - a)%n+n)%n;
        }
        for(int i = 0; i < n; i++) {
            vector<int> arr(26);
            int mx = 0;
            for(int j = 0; j < m; j++)
                mx = max(mx, ++arr[v[j][(it[j] + i)%n]-'a']);
            ans += mx;
        }
    }
    cout << ans << '\n';
}

### pC. [貪心闖關](https://zerojudge.tw/ShowProblem?problemid=q838)

題目大概就是
有很多沙袋排成一排
每一格都有很多個沙袋
每次你要從最少沙袋的那格把沙袋往後面有沙袋丟
假如在最後就直接丟掉
你在過程中會獲得你搬的沙袋數量的分數
假如你搬不動沙袋 ($\text{沙袋數量} > T$)，或者沒得搬了
程式就停止了

我第一直覺是類似柯朵莉樹(ODT)的 set 亂做
大概 $O(N \lg N)$ 複雜度，加一些常數，感覺很穩

#include <iostream>
#include <set>
using namespace std;
int main() {
    int n, t; cin >> n >> t;
    set<pair<long long, long long> > se1, se2;
    for(int i = 0; i < n; i++) {
        int a; cin >> a;
        se1.insert({i, a});
        se2.insert({a, i});
    }
    long long ans = 0;
    while(se2.size()) {
        auto it = se2.begin();
        auto [a, b] = *it;
        if(a > t) break;
        auto lb = se1.lower_bound(make_pair(b, a));
        ans += a;
        if(next(lb) == se1.end()) {
            se1.erase(lb);
            se2.erase({a, b});
            continue;
        }
        auto [c, d] = *next(lb);
        se1.erase(lb);
        se1.erase({c, d});
        se1.insert({c, d+a});
        se2.erase({a, b});
        se2.erase({d, c});
        se2.insert({d+a, c});
    }
    cout << ans << '\n';
}

### pD. [最遠分組](https://zerojudge.tw/ShowProblem?problemid=q839)

題目就是說有 $N$ 個數字
你要把他們分成 $K$ 組
每個不同的數字間會有距離
你要很會分組，分出來，讓不同組之間的數字的最小距離最大化

看到題目感覺好難，不知道要怎麼下手
因為怎麼看都不像 DP or Graph
感覺連演算法都牽扯不上
然後想到的 DSU 又不在考綱中
但真的沒想到其他做法，所以唬爛一個 DSU 出來

#include <iostream>
#include <vector>
#include <algorithm>
#include <array>
using namespace std;
struct DSU {
    vector<int> p;
    int com;
    DSU(int x) : p(x, -1), com(x) {}
    int fp(int id) {return p[id] < 0 ? id : p[id] = fp(p[id]);}
    void upd(int a, int b) {
        int ar = fp(a), br = fp(b);
        if(ar != br) {
            if(p[ar] > p[br]) swap(ar, br);
            p[ar] += p[br];
            p[br] = ar;
            com--;
        }
    }
    bool same(int a, int b) {return fp(a) == fp(b);}
};
int main() {
    int n, k; cin >> n >> k;
    vector<vector<int> > dis(n, vector<int> (n));
    vector<array<int, 3> > v;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            cin >> dis[i][j];
            if(j > i) v.push_back({dis[i][j], i, j});
        }
    }
    sort(v.begin(), v.end());
    DSU dsu(n);
    for(auto &[a, b, c] : v) {
        if(dsu.com == k) break;
        if(!dsu.same(b, c))
            dsu.upd(b, c);
    }
    int ans = 1e9;
    for(int i = 0; i < n; i++) {
        for(int j = i+1; j < n; j++) if(!dsu.same(i, j))
            ans = min(ans, dis[i][j]);
    }
    cout << ans << '\n';
}

## 心得

這次 APCS 感覺放很多水
實作題簡單到讓我懷疑我的想法出錯了
花了一個多小時在寫對拍 ~~然後最後沒事做提早出場~~

觀念題是我第一次靜下心來仔細寫，感覺蠻有收穫的

然後 APCS 果然有一大堆國中國小生來考
我考試座位旁邊有一個暴躁老哥
摔滑鼠 + 扭來扭去 + 打嗝
很躁