Editorial for 轉盤得分 (APCS 2025-06 中級)


簡潔題意

\(m\) 個輪盤、每個 \(n\) 格,每格一個小寫字母(每個輪盤就是一條長度 \(n\) 的字串)。共 \(k\) 回合,每回合每個輪盤各轉一個距離 \(d\):\(d > 0\) 順時針轉 \(d\) 格(字串向右循環位移)、\(d < 0\) 逆時針轉 \(-d\) 格、\(0\) 不動;可能超過一圈,而且每回合接著上一回合的狀態繼續轉。轉完後對每個位置計分:\(m\) 個輪盤在這個位置對齊的字元裡,出現最多次的那個字母出現了幾次就是幾分;回合分數=\(n\) 個位置加總。輸出 \(k\) 回合的總分(\(1 \le m, n, k \le 30\)、\(-100 \le d \le 100\))。

依正確通過的測試資料筆數給分,其中:

  • 子題組 1(\(60\) 分):\(m = 3\)。
  • 子題組 2(\(40\) 分):無額外限制。

先拿下子題組 1(60 分):三個輪盤,同不同直接用 if 問

轉動。 順時針轉 \(d\) 格=字串向右循環位移 \(d\) 格=最後 \(d\) 個字元搬到最前面w.substr(n - d) + w.substr(0, n - d)10.8substr+串接)。要先把 \(d\) 化成 \(0 \sim n - 1\):轉 \(n\) 格回到原狀,所以先對 \(n\) 取餘;但 C++ 的 % 對負數會得到負的餘數(上冊 2.6),逆時針 \(4\) 格的 -4 % 6-4——再加 \(n\) 取一次餘 ((d % n) + n) % n,負的就變成等價的正數(逆時針 \(4\) 格=順時針 \(2\) 格)。轉完直接存回 w[j],下一回合從這裡繼續,不回到初始字串。

計分。 三個輪盤時每個位置只有三個字元,「出現最多的字母出現幾次」用 if 問就好:三個全同 \(3\) 分、任兩個相同 \(2\) 分、否則 \(1\) 分(上冊 3.3&&||)。三條字串用 string 陣列裝(10.7)。

#include <iostream>
#include <string>
using namespace std;

int main() {
    int m, n, k;
    cin >> m >> n >> k;             // 子題組 1 保證 m = 3:剛好三個輪盤
    string w[3];
    for (int j = 0; j < 3; j++) cin >> w[j];

    int total = 0;
    for (int round = 0; round < k; round++) {
        for (int j = 0; j < 3; j++) {
            int d;
            cin >> d;
            d = ((d % n) + n) % n;                      // 轉幾圈都一樣、負的轉成等價的正數:0 ~ n-1
            w[j] = w[j].substr(n - d) + w[j].substr(0, n - d);   // 順時針轉 d 格=最後 d 個字元搬到最前面
        }
        for (int i = 0; i < n; i++) {                   // 三個輪盤對齊的字元:全同 3 分、兩個同 2 分、否則 1 分
            if (w[0][i] == w[1][i] && w[1][i] == w[2][i]) {
                total += 3;
            } else if (w[0][i] == w[1][i] || w[1][i] == w[2][i] || w[0][i] == w[2][i]) {
                total += 2;
            } else {
                total += 1;
            }
        }
    }
    cout << total << '\n';
    return 0;
}

拿範例 1 對一次:第一回合 eapcsitaiwandaicpe 得 \(10\) 分、第二回合 \(7\) 分,總分 \(17\)。這份程式交上去,範例 2(四個輪盤)和子題組 2 會 WA——這是正常的,逐筆給分之下子題組 1 的 \(60\) 分穩穩到手。

從 60 分到 100 分:m 個輪盤,用計數陣列找最多的字母

輪盤變成 \(m\) 個,轉動的程式一字不改,只有計分不能再用 if 枚舉——改成計數陣列(上冊 6.7):對每個位置開 int count[26] = {},把 \(m\) 個輪盤在這個位置的字元用 ch - 'a' 換成 \(0 \sim 25\)(8.3)去計數,再打擂台找最大值(上冊 3.9)——那就是這個位置的分數。輪盤改用 vector<string> 裝(10.3)。

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main() {
    int m, n, k;
    cin >> m >> n >> k;
    vector<string> w(m);                                // m 個輪盤,每個是一條長度 n 的字串
    for (int j = 0; j < m; j++) cin >> w[j];

    int total = 0;
    for (int round = 0; round < k; round++) {
        for (int j = 0; j < m; j++) {
            int d;
            cin >> d;
            d = ((d % n) + n) % n;                      // 轉幾圈都一樣、負的轉成等價的正數:0 ~ n-1
            w[j] = w[j].substr(n - d) + w[j].substr(0, n - d);   // 順時針轉 d 格=最後 d 個字元搬到最前面
        }
        for (int i = 0; i < n; i++) {
            int count[26] = {};                         // 這個位置上 a~z 各出現幾次
            for (int j = 0; j < m; j++) count[w[j][i] - 'a']++;
            int best = 0;
            for (int c = 0; c < 26; c++) {
                if (count[c] > best) best = count[c];   // 出現最多次的那個字母出現了幾次
            }
            total += best;
        }
    }
    cout << total << '\n';
    return 0;
}

運算量:每回合轉 \(m\) 個輪盤(各抄一次 \(n\) 個字元)、計分 \(n\) 個位置各看 \(m\) 個字元加掃 \(26\) 格,\(30 \times 30 \times 30\) 再乘個常數,遠在一秒之內。

測過再交:範例沒有「全部相同」,也沒有只轉整圈的回合

兩個範例都有順轉、逆轉、超過一圈,也有跨回合接續。沒測到的是:某個位置 \(m\) 個全同(分數等於 \(m\))、轉的距離剛好是 \(n\) 的倍數、\(n = 1\)、只有一個輪盤。

輸入 正確輸出 這一筆在測什麼
1 4 2abcd3-3 8 只有一個輪盤:每個位置都是 \(1\) 分,每回合 \(n\) 分
3 1 3aba100 -100 70 0 0-1 1 -1 6 \(n = 1\) 怎麼轉都不動(\(\pm 100\) 取餘後是 \(0\));a b a 每回合 \(2\) 分
3 4 1abcdabcdabcd4 -4 8 12 轉整圈(\(4\)、\(-4\)、\(8\))=不動;三個全同,每個位置 \(3\) 分
4 2 1abababab1 1 1 1 8 四個全同:每個位置 \(4\) 分——子題組 1 版那種「三個同 \(3\) 分、兩個同 \(2\) 分」的 if 在 \(m = 4\) 就不夠用了
3 3 2abcbcacab0 1 21 1 1 18 第一回合轉完三個都變 abc(\(9\) 分),第二回合三個同步再轉一格、還是全同(\(9\) 分)。每回合從初始字串重新轉的程式印 12

五筆都親眼看過正確,這題就穩了。

常犯錯誤
  • 轉的方向反了(寫成 substr(d) + substr(0, d),變成向左位移):範例 1 印 16(該印 17)。
  • 負數取餘沒處理(只寫 d % n):範例 1 第一回合的 \(-4\) 讓 substr 的起點超出字串,程式直接當掉;把負號拿掉當正數轉的程式印 14
  • 每回合從初始字串重新轉:範例 1 印 20;自測表第 5 列印 12
  • 位置分數算成「不同字母的種類數」:範例 1 印 31
  • 只算最後一回合:範例 1 印 7
  • 沒有任何兩個相同時算 \(0\) 分(以為最大出現次數至少要 \(2\) 才計):三個都不同也是 \(1\) 分——範例 1 印 9