BestCoder Round #81 Div.2 題解：A/B/C 三題完整分析

比賽背景

BestCoder Round #81 Div.2，三道入門級題目，考察進制轉換、二維數組模擬、雙指針/滑動窗口。本文提供思路解析與參考代碼。

A 題：Machine（三進制規律）

題意

有三種顏色 R/G/B 循環，第 $k$ 台機器的顏色遵循三進制規律。給定 $n$（機器總數）和 $k$（查詢編號），輸出前 $n$ 台機器顏色序列中第 $k$ 台的顏色。

核心觀察

序列本質是自然數的三進制表示，映射：0→R, 1→G, 2→B。第 $k$ 台（0-indexed）即 $k$ 的三進制最低位。

但題目要求輸出前 $n$ 位，若 $n$ 較大需生成前綴。實際可直接將 $k$ 轉三進制，取最低位對應顏色；若需前 $n$ 位，生成 $0\sim n-1$ 的三進制最低位即可。

參考代碼

#include 
using namespace std;
int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    long long T; cin >> T;
    while (T--) {
        long long n, k; cin >> n >> k;
        string ternary;
        while (k) {
            ternary.push_back('0' + k % 3);
            k /= 3;
        }
        reverse(ternary.begin(), ternary.end());
        // 輸出前 n 位：若 ternary 長度 < n，前面補 '0'(R)
        string ans;
        if ((long long)ternary.size() >= n) {
            ans = ternary.substr(ternary.size() - n);
        } else {
            ans = string(n - ternary.size(), '0') + ternary;
        }
        for (char c : ans) {
            if (c == '0') cout << 'R';
            else if (c == '1') cout << 'G';
            else cout << 'B';
        }
        cout << '\n';
    }
}

B 題：二維數組操作模擬

題意

$n \times m$ 矩陣，支持四種操作：

1. 交換兩行
2. 交換兩列
3. 某行所有元素加 $v$
4. 某列所有元素加 $v$

最終輸出矩陣。$n,m \le 1000$，操作數 $\le 10^5$。

關鍵優化：行列映射 + 延遲加法

• 維護 row[i] = 當前第 $i$ 行對應的原始行號，col[j] 同理。交換操作只交換映射數組，$O(1)$。
• 維護 addRow[i]、addCol[j] 記錄行/列累積加值。查詢最終值：a[row[i]][col[j]] + addRow[i] + addCol[j]。

參考代碼

#include 
using namespace std;
const int MAXN = 1005;
int a[MAXN][MAXN];
int row[MAXN], col[MAXN];
long long addRow[MAXN], addCol[MAXN];

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int T; cin >> T;
    while (T--) {
        int n, m, q; cin >> n >> m >> q;
        for (int i=1;i<=n;++i) for (int j=1;j<=m;++j) cin >> a[i][j];
        iota(row+1, row+n+1, 1);
        iota(col+1, col+m+1, 1);
        fill(addRow+1, addRow+n+1, 0);
        fill(addCol+1, addCol+m+1, 0);
        
        while (q--) {
            int op, x, y; cin >> op >> x >> y;
            if (op == 1) swap(row[x], row[y]);
            else if (op == 2) swap(col[x], col[y]);
            else if (op == 3) addRow[x] += y;
            else if (op == 4) addCol[x] += y;
        }
        
        for (int i=1;i<=n;++i) {
            for (int j=1;j<=m;++j) {
                long long val = a[row[i]][col[j]] + addRow[i] + addCol[j];
                cout << val << (j==m?'\n':' ');
            }
        }
    }
}

C 題：子串包含至少 K 種字符的個數（滑動窗口 / 尺取法）

題意

給定字符串 $s$（長度 $\le 10^6$，小寫字母）和整數 $k$，求包含至少 $k$ 種不同字符的子串個數。

滑動窗口思路

• 維護窗口 [L, R)，cnt[26] 記錄字符頻次，types 為當前窗口不同字符數。
• 擴展 $R$ 直到 types >= k，此時以 $L$ 為左端點的合法子串有 n - R + 1 個（因為再往右擴展仍合法）。
• 收縮 $L$：移除 $s[L]$，若其計數歸零則 types--，繼續尋找下一個合法 $L$。

時間 $O(n)$，空間 $O(1)$。

關鍵優化：數組代替 map

字符集固定 26 個小寫字母，用 int cnt[26] 直接索引 c - 'a'，比 unordered_map 快 4-5 倍（避免哈希開銷）。

參考代碼

#include 
using namespace std;
const int MAXN = 1000005;
char s[MAXN];
int cnt[26];

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int T; cin >> T;
    while (T--) {
        cin >> s;
        int k; cin >> k;
        int n = strlen(s);
        fill(cnt, cnt+26, 0);
        long long ans = 0;
        int types = 0, R = 0;
        for (int L = 0; L < n; ++L) {
            while (R < n && types < k) {
                if (++cnt[s[R]-'a'] == 1) ++types;
                ++R;
            }
            if (types < k) break; // 後續 L 也不可能合法
            ans += n - R + 1;
            if (--cnt[s[L]-'a'] == 0) --types;
        }
        cout << ans << '\n';
    }
}

總結與心得

三題均屬基礎算法應用，關鍵在於識別模型（進制、映射分離、雙指針）並寫出無 Bug 的工程化代碼。比賽中 40 分鐘完成三題，屬於正常 Div.2 節奏。